【无标题】二叉树的学习

1.二叉树的基本认识

二叉树是一种特殊的树。在二叉树中，每个结点最多有两个后继，这样的存储结构更容易实现。
在一颗非空的二叉树中，每个结点最多有两棵子树，分别成为左子树和右子树，且左右子树的顺序不能交换，二叉树是特殊的有序树。

2.二叉树的形态
由三个结点所构成的二叉树是有五种形态的（不考虑结点值的差异）

3.二叉树的性质
**性质一:**在二叉树的第i层上至多有2的（i－1）次方个结点
**性质二:**深度为h的二叉树中至多有2点h次方减1个结点
**性质三:**对任意一课二叉树G,如果其叶子结点为m,度为2的结点数为n，则有m＝n＋1
4.满二叉树
满二叉树就是每个结点的度为二或者度为零，一棵深度为h，且有2的h次方-1个结点的树称为满二叉树。
5.完全二叉树
满二叉树是完全二叉树的特例，除最后一层外，其他层都是满的，并且最后一层或者是满的，或者缺少右边连续的若干个结点。
6.二叉树的存储
**顺序存储结构:**顺序存储一棵二叉树时，先对改二叉树进行编号，然后以各结点的编号为下标，把各结点的值存在一维数组中。
其编号过程为:首先，把树的根结点编号定为一,然后按照层次从上到下，从左到右的顺序对每一结点进行编号。当一个结点的双亲结点的编号为i时，若他是左孩子，则编号为2i,若他是右孩子，则他的编号为2i＋1。
**链式存储结构:**链表的每个节点包含两个指针，分别指向该节点的左孩子，右孩子。
其中data为数据域，存放数据的结点信息 ，lchild为左孩子指针域，存放该结点的左子树的存储地址，rchild为右指针域，存放该节点的右子树的存储地址。当左子树或右子树不存在时，相应指针域为空。
7.二叉树的遍历
二叉树的遍历是指按照某种顺序访问二叉树中的所有结点，使得每个结点且被访问一次。
一般限定先左后右的次序，有三种遍历方式，先序遍历，中序遍历 ，后序遍历。
**先序遍历:**先序遍历二叉树就是先访问根节点在访问左子树最后访问右子树。
若二叉树为空遍历结束。否则依次执行以下 *** 作：
访问根节点printf("%c",T->data);
先序递归遍历根节点的左子树PreOrder(T->lchild);
先序递归遍历根节点的右子树PreOrder(T->rchild);
**中序遍历:**中序遍历二叉树若二叉树为空遍历结束。否则依次执行以下 *** 作：
中序递归遍历根节点的左子PostOrder(T->lchild);
中序遍历根节点printf("%c",T->data);
中序递归遍历根节点的右子树InOrder(T->rchild);
后序遍历后序遍历二叉树若二叉树为空遍历结束。否则依次执行以下 *** 作：
后序递归遍历根节点的左树PostOrder(T->lchild);
后序递归遍历根节点的右树PostOrder(T->rchild);
后序遍历根节点 printf("%c",T->data);
层次遍历
哈夫曼树是一种特殊的二叉树，这种树的所有叶子结点都带权值