树形结构介绍

1.与树型结构有关的概念：

图1

结点的度->结点拥有的子树，度为零的结点称为叶子节点，例如图中A的度为3，C的度为1，F的度为0。

树的度->树内各结点的度的最大值，例如上图中树的度为3。

树的深度（高度）->树中结点的最大层次，也是树的最大结点度数+1，例如上图中树的深度为4。

2.二叉树

满二叉树图 完全二叉树图

（1）与二叉树有关的性质：

二叉树从0层开始，第i层最多有2i（2的i次方）个结点（i >= 0 ）；

深度为K的二叉树至多有2k-1（2的k次方减1）个节点（K >= 1）;

任何一颗二叉树，其终端结点数n0与其度为2的结点数n2之间满足：n0 = n2+1;（ 解释：  有n个结点的二叉树，其边数n-1 = 0*n0+1*n1+2*n2,又有n = n0+n1+n2，解这两式，就会得到上述性质）；

具有n个结点的完全二叉树的深度为(log2n)+1;

（2）代码实现

1、定义二叉树：

（1）二叉树结构体的定义：

图4

（2）购买结点，释放结点

图5

（3）遍历二叉树，前序遍历（根左右），中序遍历（左根右），后序遍历（左右根），分别有递归的和非递归（用栈实现）的。层次遍历用队列实现，只有非递归的；

图6 图7 图8 图9 图10

（4）求树的结点的个数，树的深度

图11

（5）一般化创建树

图12 图13 图14

（6）在二叉树中寻找特定的值，寻找特定值的父节点，在中序遍历序列中找一个数的下标

图15 图16

（7）通过前序中序创建树，通过中序后序创建树

图17 图18

（8）中序遍历、后序遍历、层次遍历的另一种实现

图19 图20 图21 图22

（9）销毁树

图23