数据结构（C++）上课笔记——树和二叉树的基本概念(2020-5-6).doc

"数据结构（C++）上课笔记——树和二叉树的基本概念" 树是一种非线性数据结构，它由节点和边组成。树的定义和术语包括： 1. 自由树：是一棵自由树 Tf 可定义为一个二元组 Tf = (V, E)，其中 V 是由 n (n＞0) 个元素组成的有限非空集合，称为顶点（vertex）集合。E 是 n-1 个序对的集合，称为边集合，E 中的元素 (vi, vj）称为边（edge）或分支。 2. 有根树：是一棵有根树 T，简称为树，它是 n (n≥0) 个结点的有限集合。当 n = 0 时，T 称为空树；否则，T 是非空树，记作其中，r 是一个特定的称为根(root)的结点，它没有直接前驱；根以外的其他结点划分为 m (m ≥0) 个互不相交的有限集合 T1, T2, …, Tm，每个集合又是一棵树，并且称之为根的子树。 3. 相关术语： - 子女：若结点的子树非空，结点子树的根即为该结点的子女。 - 双亲：若结点有子女，该结点是子女双亲。 - 兄弟：同一结点的子女互称为兄弟。 - 度：结点的子女个数即为该结点的度；树中各个结点的度的最大值称为树的度。 - 分支结点：度不为 0 的结点即为分支结点，亦称为非终端结点。 - 叶结点：度为 0 的结点即为叶结点，亦称为终端结点。 - 祖先：某结点到根结点的路径上的各个结点都是该结点的祖先。 - 子孙：某结点的所有下属结点，都是该结点的子孙。 - 结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。以此类推。 - 深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。 - 高度：规定叶结点的高度为 1，其双亲结点的高度等于它的高度加一。树的高度：等于根结点的高度，即根结点所有子女高度的最大值加一。 二叉树是一种特殊的树，它的每个结点最多有两个子女，即左子女和右子女。二叉树的性质包括： 1. 若二叉树结点的层次从 1 开始，则在二叉树的第 i (i≥1)层最多有 2i-1 个结点。 2. 深度为 k (k≥0) 的二叉树最少有 k 个结点，最多有 2k-1 个结点。 3. 对任何一棵二叉树，如果其叶结点有 n0 个，度为 2 的非叶结点有 n2 个，则有 n0＝n2＋1 定义 1 满二叉树 (Full Binary Tree) ：深度为 k 的满二叉树是有 2k-1 个结点的二叉树。 定义 2 完全二叉树 (Complete Binary Tree)：若设二叉树的深度为 k，则共有 k 层。除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大 在 C++ 中，可以使用 template 来实现树和二叉树的抽象数据类型： ```cpp template <class T> class Tree { public: Tree (); ~Tree (); position Root(); BuildRoot (const T& value); position FirstChild(position p); position NextSibling(position p); position Parent(position p); T getData(position p); bool InsertChild(const position p, const T& value); bool DeleteChild(position p, int i); void DeleteSubTree (position t); bool IsEmpty (); void Traversal (void (*visit)(position p)); }; ``` 这个抽象数据类型提供了树和二叉树的基本操作，包括建立树的根结点，插入和删除结点，遍历树等。