数据结构二叉树实现

"数据结构二叉树实现" 在计算机科学中，树是一种基本的数据结构，它是一种特殊的图形结构，具有节点和边的组成部分。树的定义是递归的，用树来定义树。因此，树（以及二叉树）的许多算法都使用了递归。 树的定义：树(Tree)简记为 T，是一个二元组，T = (D, R) 其中：D 是结点的有限集合； R 是结点之间关系的有限集合。 树的相关术语： 1. 结点(Node)：表示树中的数据元素，由数据项和数据元素之间的关系组成。 2. 结点的度(Degree of Node)：结点所拥有的子树的个数。 3. 树的度(Degree of Tree)：树中各结点度的最大值。 4. 叶子结点(Leaf Node)：度为 0 的结点，也叫终端结点。 5. 分支结点(Branch Node)：度不为 0 的结点，也叫非终端结点或内部结点。 6. 孩子(Child)：结点子树的根。 7. 双亲(Parent)：结点的上层结点叫该结点的双亲。 8. 祖先(Ancestor)：从根到该结点所经分支上的所有结点。 9. 子孙(Descendant)：以某结点为根的子树中的任一结点。 10. 兄弟(Brother)：同一双亲的孩子。 11. 结点的层次(Level of Node)：从根结点到树中某结点所经路径上的分支数称为该结点的层次。 12. 堂兄弟(Sibling)：同一层的双亲不同的结点。 13. 树的深度(Depth of Tree)：树中结点的最大层次数。 14. 无序树(Unordered Tree)：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。 15. 有序树(Ordered Tree)：树中任意一个结点的各孩子结点有严格排列次序的树。 二叉树是有序树，因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。 树的根本操作： 1. Root()：求树的根结点，如果树非空，返回根结点，否则返回空； 2. Parent(t)：求结点 t 的双亲结点。如果 t 的双亲结点存在，返回双亲结点，否则返回空； 3. Child(t,i)：求结点 t 的第 i 个子结点。如果存在，返回第 i 个子结点，否则返回空； 4. RightSibling(t)：求结点 t 第一个右边兄弟结点。如果存在，返回第一个右边兄弟结点，否则返回空； 5. Insert(s,t,i)：把树 s 插入到树中作为结点 t 的第 i 棵子树。成功返回 true，否则返回 false； 6. Delete(t,i)：删除结点 t 的第 i 棵子树。成功返回第 i 棵子树的根结点，否则返回空； 7. Traverse(TraverseType)：按某种方式遍历树； 8. Clear()：清空树； 9. IsEmpty()：判断树是否为空树。如果是空树，返回 true，否则返回 false； 10. GetDepth()：求树的深度。如果树不为空，返回树的层次，否则返回 0。 二叉树的定义：二叉树(Binary Tree)是 n(n≥0)个相同类型的结点的有限集合。n=0 的二叉树称为空二叉树(Empty Binary Tree)；对于 n＞0 的任意非空二叉树有：（1）有且仅有一个特殊的结点称为树的根(Root)结点，根没有前驱结点；（2）若 n＞1，则除根结点外，其余结点被分成了 m(m＞0)个互不相交的集合T1，T2，…，Tm，其中每一个集合 Ti(1≤i≤m)本身又是一棵树。