文档介绍：数据结构C描述树
哈夫曼树

二叉树
树的基本概念
退出
目录
树的基本概念
树的定义
1．树。
当一棵K叉树上的结点数达到时，称为满K叉树。
性质4 具有n个结点的k叉树的最小深度为logk(n(k-1)+1)。
（请注意，x 表示取不小于x的最小整数，或叫做对x上取整。）
证明：设具有n个结点的k叉树的深度为h，即在该树的前面h-1层都是满的，即每一层的结点数等于ki-1个(1≤i≤h-1)，第h层（即最后一层）的结点数可能满，也可能不满，这时，该树具有最小的深度。由性质3知道，结点数n应满足下面条件：
<n≤ ，通过转换为：kh-1<n(k-1)+1≤kh，再取以k为底的对数后，可以得到：
h-1<logk(n(k-1)+1)≤h，即有：logk(n(k-1)+1)≤h<logk(n(k-1)+1)+1，而h只能取整数，所以，该k叉树的最小深度为h=logk(n(k-1)+1) 。
二叉树
二叉树的定义
1．二叉树的定义
和树结构定义类似，二叉树的定义也可以递归形式给出：
二叉树是n（n≥0）个结点的有限集，它或者是空集（n=0），或者由一个根结点及两棵不相交的左子树和右子树组成。
二叉树的特点是每个结点最多有两个孩子，或者说，在二叉树中，不存在度大于2的结点，并且二叉树是有序树（树为无序树），其子树的顺序不能颠倒，因此，二叉树有五种不同的形态，参见图6-5 。
2．二叉树的基本运算
（1）inittree(&T)
二叉树的初始化。
（2）root(T)
求二叉树的根结点。
（3）parent(T,x)
求二叉树T中值为x的结点的双亲。
（4）lchild(T,x)
求二叉树T中值为x的结点的左孩子。
(5) rchild(T,x)
求二叉树T中值为x的结点的右孩子。
(6) lbrother(T,x)
求二叉树T中值为x的结点的左兄弟。
(7) rbrother(T,x)
求二叉树T中值为x的结点的右兄弟。
(8) traverse(T)
遍历二叉树T。
(9) createtree(&T)
建立一棵二叉树T。
(10) addlchild(&T,x,y)
在二叉树T中，将值为y的结点作为值为x的结点的左孩子插入。
(11) addrchild(&T,x,y)
在二叉树T中，将值为y的结点作为值为x的结点的右孩子插入。
(12) dellchild(&T,x)
在二叉树T中，删除值为x 的结点的左孩子。
(13) delrchild(&t,x)
在二叉树T中，删除值为x 的结点的右孩子。
二叉树的性质
性质1 若二叉树的层数从1开始，则二叉树的第k层结点数，最多为2k-1个（k>0）。
可以用数学归纳法证明之。
性质2 深度（高度）为k的二叉树最大结点数为2k-1（k>0）。
证明：深度为k的二叉树，若要求结点数最多，则必须每一层的结点数都为最多，由性质1可知，最大结点数应为每一层最大结点数之和。既为 20+21+…+2k-1=2k-1。
性质3 对任意一棵二叉树，如果叶子结点个数为n0，度为2的结点个数为n2，则有n0=n2+1。
证明：设二叉树中度为1的结点个数为n1，根据二叉树的定义可知，该二叉树的结点数n=n0+n1+n2。又因为在二叉树中，度为0的结点没有孩子，度为1的结点有1 个孩子，度为2的结点有2个结孩子，故该二叉树的孩子结点数为 n0*0+n1*1+n2*2 ，而一棵二叉树中，除根结点外所有都为孩子结点，故该二叉树的结点数应为孩子结点数加1即：n=n0*0+n1*1+n2*2+1因此,有 n=n0+n1+n2=n0*0+n2*1+n2*2+1，最后得到n0=n2+1。
为继续给出二叉树的其它性质，先定义两种特殊的二叉树。
满二叉树深度为k具有2k-1个结点的二叉树，称为满二叉树。
从上面满二叉树定义可知，必须是二叉树的每一层上的结点数都达到最大，否则就不是满二叉树。
完全二叉树如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~ n的结点一一对应，则称这棵二叉树为完全二叉树。
从完全二叉树定义可知，结点的排列顺序遵循从上到下、从左到右的规律。所谓从上到下，表示本层结点数达到最大后，才能放入下一层。从左到右