Question

数据结构之二叉树

Answer 1

二叉树的分类
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。
完全二叉树：除了最下面一层，其他层结点都是饱满的，并且最下层上的结点都集中在该层最左边的若干位置上。（满二叉树也是完全二叉树）
非完全二叉树：既不是满二叉树，也非完全二叉树。

二叉树的遍历
前序遍历（先根遍历）：根左右。
后序遍历（后根遍历）：左右根。
中序遍历（中根遍历）：左跟右。
层次遍历：一层一层自左向右。

图中前序遍历结果是：1,2,4,5,7,8,3,6；
图中中序遍历结果是：4,2,7,8,5,1,3,6；
图中后序遍历结果是：4,8,7,5,2,6,3,1；
图中层次遍历结果是：1,2,3,4,5,6,7,8；

树和二叉树的转换
将树的孩子结点转成二叉树的左子结点，树的兄弟结点转成二叉树的右子结点。

二叉树的一些重要特性
1、在二叉树的第i层上最多有2^(n-1)个结点（i>=1）；
例：
以图1为例：任一图中第2层，最多只能有2个结点。验证正确！
2、深度为k的二叉树最多有2^k - 1个结点（K>=1）；
例：
以图1为例：图中所有二叉树深度为3，因此，该些二叉树最多有2^3 -1 = 7个结点，验证正确！
3、对任何一颗二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1；
例：
以图1为例：看最后一个非完全二叉树，图中所示，叶子结点n0 = 2；度为2的结点n2 = 1(结点2)；则2 = 1 + 1。验证正确！
4、如果对一颗有n个结点的完全二叉树的结点按层序编号（从第1层到⌊log2n⌋ + 1层，每层从左到右），则对任一结点i(1<=i<=n)，（⌊⌋向下取整符号） 有：
如果i=1，则结点i无父节点，是二叉树的根；如果i>1，则父节点是⌊i/2⌋ ；
例：
以图1左侧的完全二叉树为例：若i = 3，则i > 1，⌊3/2⌋ = 1，3的根结点为1。验证正确！
如果2i>n，则结点i为叶子结点，无左子结点；否则，其左子结点是结点2i；
例：
以图1左侧的完全二叉树为例：若i = 3，因 n = 5，则2i>n，由此推出3为叶子结点。若i = 2，因 n = 5，则2i<n，由此推出2的左子结点为4。验证正确！
如果2i+1>n，则结点i无右子结点，否则，其右子结点是结点2i + 1。
例：
以图1左侧的完全二叉树为例：上一条否命题求出了左子树结点，而这条正好求出了右子树结点。结点i=2的右子树结点为5，验证正确！