二叉树遍历演示
四、 遍历二叉树 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施 操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就 是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比 较、更新、查看元素内容等等各种操作。
二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按 层次访问。下面我们将分别进行讨论。
1、 按根、左子树和右子树三部分进行遍历 遍历二叉树的顺序存在下面6种可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列二叉树的两种遍历方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列
（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。 由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。（1）先序遍历递归算法
void PreOrder(BTree BT) {
if (BT) { Visit(BT);
PreOrder(BT-》Lchild);
PreOrder(BT-》Rchild);
}（2）中序遍历递归算法
void InOrder(BTree BT) {
if (BT) {
InOrder(BT-》Lchild);
Visit(BT);
InOrder(BT-》Rchild);
}
}（3）后序遍历递归算法
void PostOrder(BTree BT) {
if (BT) {
PostOrder(BT-》Lchild);
PostOrder(BT-》Rchild);
Visit(BT);
}
} 2 、按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。
void LevelOreder(QBTree BT) {
for (i=1;i《=BT.n;i++)
if (BT.elem[i]!=’#’) Visite(BT.elem[i]);
}二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。 在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作； 而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；void LevelOrder(BTree *BT) {
if (!BT) exit;
InitQueue(Q); p=BT; //初始化
Visite(p); EnQueue(&Q,p); //访问根结点，并将根结点入队
while (!QueueEmpty(Q)) { //当队非空时重复执行下列操作
DeQueue(&Q,&p); //出队
if (!p-》Lchild) {Visite(p-》Lchild);EnQueue(&Q,p-》Lchild); //处理左孩子《br》 if (!p-》Rchild) {Visite(p-》Rchild);EnQueue(&Q,p-》Rchild); //处理右孩子《br》 }
}
五、典型二叉树的操作算法 1、 输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉 树的位置上填补一个特殊的字符，比如，’#’。在算法中，需要对每个输入的字符进行判 断，如果对应的字符是’#’，则在相应的位置上构造一棵空二叉树；否则，创建一个新结 点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针 参数在递归调用返回时完成。算法：BTree Pre_Create_BT( ) {
getch(ch);
if (ch==’#’) return NULL; //构造空树
else { BT=(BTree)malloc(sizeof(BTLinklist)); //构造新结点
BT-》data=ch;
BT-》lchild =Pre_Create_BT( ); //构造左子树
BT-》rchild =Pre_Create_BT( ); //构造右子树
return BT;
}
} 2、 计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否 为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。算法：void Leaf(BTree BT,int *count) {
if (BT) {
Leaf(BT-》child,&count); //计算左子树的叶子结点个数
if (BT-》lchild==NULL&&BT-》rchild==NULL) (*count)++;
Leaf(BT-》rchild,&count); //计算右子树的叶子结点个数
}
} 3、 交换二叉树的左右子树 许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一 些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。算法：void change_left_right(BTree BT) {
if (BT) {
change_left_right(BT-》lchild);
change_left_right(BT-》rchild);
BT-》lchild《-》BT-》rchild;
}
} 4 、求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树 的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。算法：int hight(BTree BT) { //h1和h2分别是以BT为根的左右子树的高度
if (BT==NULL) return 0;
else {
h1=hight(BT-》lchild);
h2=hight(BT-》right);
return max{h1,h2}+1;
}
} 六、树、森林与二叉树的转换 1、 树、森林转换成二叉树 将一棵树转换成二叉树的方法： 将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。 特点：一棵树转换成二叉树后，根结点没有右孩子。 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根 结点看作兄弟关系，并对其中的每棵树依依地进行转换。 2 、二叉树还原成树或森林 这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。
第 3 节 哈夫曼树及其应用 1、哈夫曼树的定义及特点
在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼树的一个重要特点是：没有度为1的结点。
2、构造哈夫曼树的过程：
（1）将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。 例如： 假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。
它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定树 在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着 程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为 这个程序很简单，并且很快就可以用下列形式编写出来：if (socre《60) printf(“bad“);
else if (socre《70) printf(“pass“);
else if (score《80) printf(“general“);
else if (score《90) printf(“good“);
esle printf(“very good“); 在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：
4．前缀编码 在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两 个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
（1）等长编码 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位 数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。（2）不等长编码 在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符，每个字符的使用频率分别为{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，现以此为例设计哈夫曼编码。
哈夫曼编码设计过程为：
（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到{5,29,7,8,14,23,3,11}；
（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5-27所示；
（3）由此哈夫曼树生成哈夫曼编码，如图5-28所示。
最后得出每个字符的编码为：比如，发送一段编码：0000011011010010， 接收方可以准确地通过译码得到：⑥⑥⑦⑤②⑧。
完全二叉树的叶子节点数公式是什么
完全二叉树的叶子节点数公式为：设叶子节点数为n0, 度为1的节点数为n1，度为2的节点数为n2，总节点为n。
1、当n为奇数时（即度为1的节点为0个），n0= (n+1)/2。
2、当n为偶数（即度为1的节点为1个）， n0= n/2。
n1，n2，都可以求。
完全二叉树的特点：
1.叶子结点只可能在层次最大的两层上出现。
2.对任一结点，若其由分支下的子孙的最大层次为l，则其左分支下的子孙的最大层次必为l或l+1。
完全二叉树的性质：
1.具有n个结点的完全二叉树的深度为logn+1。
2.如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i，有：
（1）如果i=1，则结点i是二叉树的根节点，无双亲；如果i》1，则其双亲是结点⌊i/2⌋。
（2）如果2i》n，则结点i无左孩子；否则其左孩子是结点2i。
（3）如果2i+1》n，则结点i无右孩子；否则其右孩子是结点2i+1。
完全二叉树的叶子节点数公式是什么
完全二叉树的叶子节点数公式为：
设叶子节点数为n0, 度为1的节点数为n1，度为2的节点数为n2，总节点为n。
1、当n为奇数时（即度为1的节点为0个），n0= (n+1)/2。
2、当n为偶数（即度为1的节点为1个）， n0= n/2。
n1，n2，都可以求。
特殊类型：
1、满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
2、完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。
3、完全二叉树的特点是叶子结点只可能出现在层序最大的两层上，并且某个结点的左分支下子孙的最大层序与右分支下子孙的最大层序相等或大1。
相关术语：
1、结点：包含一个数据元素及若干指向子树分支的信息。
2、结点的度：一个结点拥有子树的数目称为结点的度。
3、叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。
4、结点的层次：从根结点开始，假设根结点为第1层，根结点的子节点为第2层，依此类推，如果某一个结点位于第L层，则其子节点位于第L+1层。
5、树的深度：也称为树的高度，树中所有结点的层次最大值称为树的深度。
以上内容参考 百度百科-二叉树
