二叉树小专题和BST算法导论，有哪些深入探讨的细节？

本文共计2727个文字，预计阅读时间需要11分钟。

数据结构课上，老师已讲解过二叉树，以下简要总结：二叉树的前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）的算法；以及根据前序（后序）和中序（前序）遍历结果重建二叉树的方法。此外，二叉树具有以下性质：1、每个节点最多有两个子节点；2、二叉树的子树之间没有交集。

数据结构上老师已经专门讲过二叉树了，这里做一下小结，以及根据前（后），中序列求后（前）中序列的算法；

当然，二叉树概念就不引入了，这里再次提炼一下二叉树的性质：

1、满足本身是有序树。
2、树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2。
3、二叉树具有以下几个性质：
a:二叉树中，第 i 层最多有 2的i-1次方个结点。
b:如果二叉树的深度为 K，那么此二叉树最多有 2的k次方-1 个结点。
c：二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。
这里也有完美二叉树：

1.满二叉树中第 i 层的节点数为 2的i-1 次方个。
2.深度为 k 的满二叉树必有 2k次方-1 个节点 ，叶子数为 2的k-1次方。
3.满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4.具有 n 个节点的满二叉树的深度为 log2(n+1)。