数据结构自学之二叉树
自己整理的笔记，可能不适合大家阅读，还请见谅
基本术语和基础知识
树的定义
树（tree）是包含n（n>0）个结点的有穷集，其中：
（1）每个元素称为结点（node）；
（2）有一个特定的结点被称为根结点或树根（root）。
（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。
树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
我们可以形式地给出树的递归定义如下:
单个结点是一棵树，树根就是该结点本身。
设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。
空集合也是树，称为空树。空树中没有结点。
节点的度和树的度（degree）
结点的度和树的度。结点的度即结点有几个分支，比如节点A有两个分支B和C，那么结点A的度就是2，树的度即为一棵树中结点的最大度数。
有序树和无序树
有序树和无序树。如果将树中结点的子树看成是从左至右依次有序且不能交换，则称该树为有序树，否则称为无序树。
叶节点或终端节点
度为0的节点称为叶节点
非终端节点或分支节点
度不为0的节点
双亲节点或父节点
若一个节点含有子节点，则这个节点称为其子节点的父节点
孩子节点或子节点
一个节点含有的子树的根节点称为该节点的子节点
兄弟节点
具有相同父节点的节点互称为兄弟节点
二叉树
二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构。
二叉树的定义：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒（也就是说，二叉树是有序树）。
节点的层次
从根开始定义起，根为第1层，根的子节点为第2层，以此类推
树的高度或深度
树中节点的最大层次
堂兄弟节点
双亲在同一层的节点互为堂兄弟
节点的祖先
从根到该节点所经分支上的所有节点
子孙
以某节点为根的子树中任一节点都称为该节点的子孙
森林
由m（m>=0）棵互不相交的树的集合称为森林
二叉树
二叉树的一些性质
l 二叉树的第i层至多有2i-1个结点（i从1开始，根节点所在的层为第一层）；
l 深度为k的二叉树至多有2k-1个结点（实际上就是个等比数列求和）；
l 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
对于这个结果的理解：可以把一个二叉树的所有节点分为三类：节点的度为1的节点，节点的度为2的节点，节点度为0的节点（也就是叶子节点），它们的数量分别由n0、n1、n2表示，总的节点数用n表示，这样n = n0+n1+n2，从另一个角度看n = 2*n2+1*n1+1，也就是总节点数=度为2的节点的孩子节点个数+度为1的节点的孩子节点个数+根节点，这样在一联立，就得出n0=n2+1。
满二叉树和完全二叉树
满二叉树：
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。
满二叉树的性质：
l 一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;
l 第k层的结点数是：2k-1;
l 总结点数是：2k-1，且总节点数一定是奇数。
完全二叉树：
若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。
完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
完全二叉树：叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
注：
完全二叉树是效率很高的数据结构，堆是一种完全二叉树或者近似完全二叉树，所以效率极高，像十分常用的排序算法、Dijkstra算法、Prim算法等都要用堆才能优化，二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全二叉树。
平衡二叉树
平衡二叉树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。 最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列，可以参考Fibonacci(斐波那契)数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量
二叉树的三种创建方法
首先明确一点：创建一棵二叉树，最关键的就是确定每个节点的位置！
二叉树的创建方法可以分为四种：交互式创建方法、根据先序序列创建、根据先序序列和中序序列创建、根据中序序列和后续序列创建。交互式创建方法就是采用询问的方式，确定每个节点的位置，这种方法在实际中并不常用，所以我们仅讨论后三种创建方法。
根据先序序列创建二叉树
首先明确一点，只有先序序列是不能还原二叉树的，也是就是说，如果只知道先序序列是不能确定各个节点的位置的。记得学数据结构的时候，经常有考题让根据先序序列+中序序列还原一棵二叉树，或者根据后续序列+中序序列还原二叉树，我们看到，其中都涉及了中序序列，单独的先序序列、中序序列和后续序列都不能还原整个二叉树，也只有上面两种组合方式可以还原一棵二叉树。我们这里所说的根据先序序列创建二叉树，实际上是是一种改造后的先序序列，或者说是对一棵改造后的二叉树的先序遍历。
比如说我们要创建一棵如图所示的二叉树
首先我们要对这棵二叉树进行必要的改造，或者叫生成该二叉树的扩展二叉树。所谓扩展二叉树，就是在现有二叉树的基础上增加空树叶形成的二叉树，扩展二叉树的先序序列可以叫做原二叉树的扩展先序序列。扩展二叉树是一个满二叉树。
由于单纯根据先序序列并不能确定一棵二叉树，但是扩展后的二叉树，由于是一个满树，且可以确定叶子节点，所以可以根据扩展先序序列来还原一棵二叉树。
下满该二叉树的扩展二叉树。
扩展的先序序列为：ABD##EF###CG#H###
编程思路
根据创建二叉链表的思维方式，我们可以采用递归的方法。显然当输入的是结点字符时，需要创建一个新结点，然后呢？递归创建左子树，递归创建右子树。若输入的是“#”，则表明该二叉树为空树，则只需将指针置为NULL即可。
代码在最后给出
根据先序序列和中序序列创建二叉树
根据先序序列和中序序列是可以还原一棵二叉树的，因此，如果知道了一个二叉树的先序序列和中序序列就可以创建这棵二叉树。
编程思路：
所有用递归方法创建二叉树，思路都有其共性，都是首先创建跟节点，再递归穿件左子树和右子树。现在的问题是，怎样根据两个序列确定根节点和左、右子树的问题。
- 找到根节点
在前序序列中找到根节点，就是当前前序序列的数组的首字符。 - 找到左子树和右子树
根据前序序列中找出的根节点，找到其在中序序列[1…n]中的位置pos，则，在前序序列中，左子树为[2,pos] ，右子树为[pos+1,n]
代码在最后面
根据后序序列和中序序列创建二叉树
思路同第二种方法：
- 找到根节点
在谦虚序列中找到根节点，就是当前后序序列的数组的尾字符。 - 找到左子树和右子树
根据后序序列中找出的根节点，找到其在中序序列[1…n]中的位置pos，则，在后序序列中，左子树为[1,pos-1] ，右子树为[pos,n-1]
二叉树的非递归创建方法
树的定义本身就是一种递归定义，所以用递归的方法创建树非常容易理解也非常简单。使用递归（Recursion）建立二叉树（Binary Tree）的非顺序存储结构（即二叉链表），可以简化算法编写的复杂程度，但是递归效率低，而且容易导致堆栈溢出，因而很有必要使用非递归算法。
我采用的是利用扩展二叉树的前序序列创建二叉树。
编程思路：
首先要创建一个数据结构，这个结构包含两个部分，一个是二叉树的节点，另一部分记录该节点当前的孩子个数（由于是扩展二叉树，也就是满二叉树，所以最终所有节点都会有两个孩子）
然后将前序序列的第一个节点入栈，并且将其孩子个数初始化为0
再然后用循环遍历前序序列，在循环中：
如果节点不为#则：
1、 创建新节点
2、 将节点挂在二叉树上（根据父节点孩子的个数决定挂在左边还是右边）
3、 将节点入栈
如果节点为#:
如果没有孩子：孩子个数加一
如果有一个孩子了：孩子个数加一然后进行出栈操作，知道孩子个数为1的节点。
代码在后面。
二叉树的三种遍历方法
二叉树的遍历方法有根据对跟节点的访问顺序，可以分为：先序遍历、中序遍历和后序遍历。所谓先序后续和中序指的是对跟节点的访问顺序，所以这三种方法又被叫做：先根序遍历，中根序遍历和后根序遍历。还要明白一点就是，经过一个节点，并不代表访问了这个节点！就像大禹治水，可以过三门而不入！
先序遍历（preorder traversal）
在先序遍历中，对节点的访问工作是在它的左右儿子被访问之前进行的。换言之，先序遍历访问节点的顺序是根节点-左儿子-右儿子。由于树可以通过递归来定义，所以树的常见操作用递归实现常常是方便清晰的。
另一种表示方法：
先访问根节点，再遍历左子树，最后遍历右子树；并且在遍历左右子树时，仍需先访问根节点，然后遍历左子树，最后遍历右子树。
代码在后面
中序遍历
遍历左子树、然后访问根节点，最后遍历右子树；并且在遍历左右子树的时候。仍然是先遍历左子树，然后访问根节点，最后遍历右子树。
代码在后面
后续遍历
先遍历左子树，然后遍历右子树，最后访问根节点；同样，在遍历左右子树的时候同样要先遍历左子树，然后遍历右子树，最后访问根节点。
代码在后面
二叉树的非递归遍历方法
由于树的定义是采用递归的形式，所以无论是创建一棵二叉树还是遍历一棵二叉树，使用递归的方法都非常容易理解，而且代码相当简练。但有些时候我们可能需要采用非递归的形式遍历二叉树（至于什么情况我暂时还不清楚，有人说，可能采用非递归的方式效率更高，因为函数递归会进行大量的入栈出栈，保存断点的工作，所以记得当时上数据结构的时候，肖国玺老师再三强调：“能递推不递归”，但是我觉得，采用非递归的遍历方法，也需要自己维护一个栈来记录经过的节点，所以也涉及大量的入栈和出栈工作，而采用递归函数的做法，相当于编译器为我们维护了出栈入栈操作。 可能是因为函数调用，除了保存断点、出栈、入栈操作还有类似形实结合等操作，所以相对于自己维护栈，函数调用的开销应该会更大，所以，应该是非递归的方式比递归函数的方式效率要高）
采用非递归的方式遍历二叉树，其实非常类似于卷面考试时，给我们一棵二叉树，然后让我们人工写出它的前序序列。因为我们人工写前序序列的时候，不会采用递归的形式（即使有也应该很少人吧）因为我们更习惯于递推。而非递归的遍历方式，其实就是将我们做题时的思路（方法）写成程序即可。非递归的遍历方法都需要程序员自己维护一个栈，用来记录节点的层次关系。三种遍历方法中，非递归的后序遍历方法相对另外两种较为复杂，
非递归的先序遍历
非递归的先序遍历需要借助一个栈，并且要再一个循环中完成，用指针p指向当前节点。循环结束的条件是，栈为空而且当前节点为NULL（这期间会出现一次栈为空的时候，就是访问根节点的时候，而这个时候右子树还没有被访问）。
先序遍历的编程思路是：
在循环中进行，循环结束条件为：栈为空而且当前节点为NULL。如果当前节点不为NULL，则访问当前节点，并将当前节点压入栈中，然后将当前节点指向其左孩子。如果当前节点为NULL，则将当前节点指向栈顶节点，然后将当前节点指向其右孩子，然后再出栈。代码在后面。
非递归的中序遍历
与先序遍历一样。非递归的中序遍历需要借助一个栈，并且要再一个循环中完成，用指针p指向当前节点。循环结束的条件是，栈为空而且当前节点为NULL（这期间会出现一次栈为空的时候，就是访问根节点的时候，而这个时候右子树还没有被访问）。代码与先序遍历也十分相似。仅仅是访问的位置不一样。代码在后面。
非递归的后序遍历
与前两种方法不同，后序遍历的循环结束条件只有一个栈为空即可，因为根节点位于栈底，而后序遍历总是最后访问根节点。后序遍历程序的思路是：
先将根节点压入栈中，然后进入循环，循环结束条件为栈空。
在循环中，当前节点总是位于栈顶的节点，如果当前节点没有左右孩子则对其进行访问，如果当前节点的左右孩子都被访问，则也对当前节点进行访问。当当前节点的孩子没有被访问时，依次将右孩子和左孩子压入栈中（栈为后进先出，这样的顺序才能保证最先访问左子树）。代码在后面。
二叉树的销毁
构造和使用二叉树后，将二叉树的释放，需要将存储二叉树节点的内存空间释放掉，最后将二叉树置NULL。
遍历是将节点数据元素找出来，同样利用便利的思想，也可以将节点指向的内存空间释放掉。这里需要注意的问题时，释放的先后问题，根节点必须在左子树和右子树的后面释放，因此，利用后续遍历的方法可以释放掉二叉树中多有节点的存储空间。
代码在后面
源代码
二叉树创建、遍历、销毁的代码
#include <stdio.h>
#define __USE_GNU
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct b_node{
intvalue;//节点的值
structb_node *l_tree;//左子树
structb_node *r_tree;//右子树
} BNode,*PBNode;
/**
* 分配一个节点
* */
PBNode allocate_node()
{
PBNodenode = NULL;
node= (PBNode)malloc(sizeof(struct b_node));
if(node== NULL)
returnNULL;
memset(node,0,sizeof(structb_node));
returnnode;
}
/**
* 设置一个节点的值
* */
void set_value(PBNode node,int value)
{
if(node== NULL)
return;
node->value= value;
node->l_tree= NULL;
node->r_tree= NULL;
}
/**
* 得到节点的值
* */
int get_value(PBNode node)
{
returnnode->value;
}
/**
* 根据扩展的先序序列创建一棵二叉树
* */
int preCreate(PBNode *node,char**preTraversal)
{
if(*preTraversal== NULL)
return-1;
if(**preTraversal== '\0')
{
//printf("应该不会执行到这里,如果执行到了，很可能说明先序序列给的有问题！！！\n");
printf("给定的扩展先序序列有问题！\n");
return-1;
}
if(**preTraversal== '#')
{
*node= NULL;
return0;
}
*node= allocate_node();//创建一个节点
if(*node== NULL)
return-1;
set_value(*node,**preTraversal);//设置节点的值
(*preTraversal)++;
if(preCreate(&((*node)->l_tree),preTraversal)!= 0)//第归创建左子树
return-1;
(*preTraversal)++;
if(preCreate(&((*node)->r_tree),preTraversal)!= 0)//第归创建右子树
return-1;
return0;
}
/**
* 根据中序序列和前序序列创建二叉树
*@para: 当前树的根结点，当前树的前序序列、中序序列和序列的长度（或者理解为节点的个树）
*@return:成功返回0，失败返回-1
* */
int pre_inCreate(PBNode *node,char*preTraversal,char *inTraversal,int length)
{
if(preTraversal== NULL || inTraversal == NULL)
return-1;
if(length== 0)
return0;
*node= allocate_node();
if(*node== NULL)
return-1;
(*node)->value= *preTraversal;//当前树的根节点赋值
(*node)->l_tree= NULL;
(*node)->r_tree= NULL;
//找到左、右子树的先序序列和中序序列
char*pos = NULL;
pos= (char *)memmem(inTraversal,length,preTraversal,1);
if(pos== NULL)
return-1;
intleft_len = pos - inTraversal;//左子树节点的个树
char*l_preTraversal = preTraversal + 1;//左子树前序序列的起始地址
char*l_inTraversal = inTraversal;//左子树中序序列的起始地址
if(pre_inCreate(&((*node)->l_tree),l_preTraversal,l_inTraversal,left_len)!= 0)//第归创建左子树
return-1;
intright_len = length - left_len - 1;//右子树节点的个树
char*r_preTraversal = preTraversal + left_len + 1;//右子树前序序列的起始地址
char*r_inTraversal = pos + 1;//右子树中序序列的起始地址
if(pre_inCreate(&((*node)->r_tree),r_preTraversal,r_inTraversal,right_len)!= 0)//第归创建右子树
return-1;
return0;
}
/**
* 根据中序序列和后序序列创建二叉树
*@para: 当前树的根结点，当前树的后序序列、中序序列和序列的长度（或者理解为节点的个树）
*@return:成功返回0，失败返回-1
* */
int post_inCreate(PBNode *node,char*postTraversal,char *inTraversal,int length)
{
if(postTraversal== NULL || inTraversal == NULL)
return-1;
if(length== 0)
return0;
*node= allocate_node();
if(*node== NULL)
return-1;
(*node)->value= postTraversal[length - 1];//当前树的根节点赋值
(*node)->l_tree= NULL;
(*node)->r_tree= NULL;
//找到左、右子树的先序序列和中序序列
char*pos = NULL;
pos= (char *)memmem(inTraversal,length,postTraversal + length - 1,1);
if(pos== NULL)
return-1;
intleft_len = pos - inTraversal;//左子树节点的个树
char*l_postTraversal = postTraversal;//左子树后序序列的起始地址
char*l_inTraversal = inTraversal;//左子树中序序列的起始地址
if(post_inCreate(&((*node)->l_tree),l_postTraversal,l_inTraversal,left_len)!= 0)//第归创建左子树
return-1;
intright_len = length - left_len - 1;//右子树节点的个树
char*r_postTraversal = postTraversal + left_len;//右子树后序序列的起始地址
char*r_inTraversal = pos + 1;//右子树中序序列的起始地址
if(post_inCreate(&((*node)->r_tree),r_postTraversal,r_inTraversal,right_len)!= 0)//第归创建右子树
return-1;
return0;
}
/**
* 先序遍历二叉树
* */
void pre_traversal(PBNode root)
{
if(root== NULL)
return;
printf("%c",root->value);
pre_traversal(root->l_tree);
pre_traversal(root->r_tree);
}
/**
* 中序遍历二叉树
* */
void in_traversal(PBNode root)
{
if(root== NULL)
return;
in_traversal(root->l_tree);
printf("%c",root->value);
in_traversal(root->r_tree);
}
/**
* 后续遍历二叉树
* */
voidpost_traversal(PBNode root)
{
if(root == NULL)
return;
post_traversal(root->l_tree);
post_traversal(root->r_tree);
printf("%c",root->value);
}
/**
* 释放节点空间
* */
void free_node(PBNode *node)
{
if(*node== NULL)
return;
free(*node);
*node= NULL;
}
/**
* 销毁二叉树
* */
void destory_tree(PBNode *root)
{
if(*root== NULL)
return;
destory_tree(&((*root)->l_tree));
destory_tree(&((*root)->r_tree));
free_node(root);
}
int main()
{
PBNoderoot = NULL;
/*
char*traversal = (char *)"ABD##EF###CG#H###";
if(preCreate(&root,&traversal)!= 0)
{
printf("创建失败！！\n");
}
printf("用扩展先序序列成功创建二叉树！！！\n");
*/
/*
if(pre_inCreate(&root,(char*)"ABDEFCGH",(char*)"DBFEAGHC",strlen("DBFEAGHC")) != 0)
{
printf("创建失败！！\n");
}
printf("用前序序列和中序序列成功创建二叉树！！！\n");
*/
if(post_inCreate(&root,(char*)"DFEBHGCA",(char*)"DBFEAGHC",strlen("DBFEAGHC")) != 0)
{
printf("创建失败！！\n");
}
printf("用后序序列和中序序列成功创建二叉树！！！\n");
printf("先序遍历的结果为:");
pre_traversal(root);
printf("\n");
printf("中序遍历的结果为:");
in_traversal(root);
printf("\n");
printf("后序遍历的结果为:");
post_traversal(root);
printf("\n");
//销毁二叉树
destory_tree(&root);
return0;
}
二叉树的非递归创建和非递归遍历
#include <iostream>
#include <stack>
#include <string.h>
using namespace std;
typedef struct b_node{
charvalue;//节点的值
structb_node *l_tree;//左子树
structb_node *r_tree;//右子树
} BNode,*PBNode;
/**
* 分配一个节点
* */
PBNode allocate_node()
{
PBNodenode = NULL;
node= new BNode();
if(node== NULL)
returnNULL;
memset(node,0,sizeof(structb_node));
returnnode;
}
/**
* 设置一个节点的值
* */
void set_value(PBNode node,int value)
{
if(node== NULL)
return;
node->value= value;
node->l_tree= NULL;
node->r_tree= NULL;
}
//包含节点状态的节点
typedef struct tag_node{
PBNodenode;
intc_num;//孩子节点的个数`
}*PTNode;
/**
* 根据扩展的先序序列创建一棵二叉树,非第归方式
* */
int preCreate(PBNode *root,char*preTraversal)
{
intlen = strlen(preTraversal);
if(len== 0)
return-1;
//创建根节点
*root= allocate_node();
set_value(*root,preTraversal[0]);
PTNodet_node = NULL;
t_node= new struct tag_node;
memset(t_node,0,sizeof(structtag_node));
t_node->node= *root;
t_node->c_num= 0;
stack<PTNode>s_node; //栈
s_node.push(t_node);
inti = 1;
for(;i< len;i++)
{
if(preTraversal[i]== '#')
{
PTNodet_node = s_node.top();
t_node->c_num++;
if(t_node->c_num== 1)
continue;
do{
delete(s_node.top());//这里要释放资源，否则会导致内存泄露
s_node.pop();
if(s_node.empty())
break;
t_node= s_node.top();
}while(t_node->c_num== 2);
}
else
{
//创建节点
PBNodenode = allocate_node();
set_value(node,preTraversal[i]);
//将节点挂到二叉树上
PTNodet_node = s_node.top();//得到父节点
PBNodef_node = t_node->node;
t_node->c_num++;
if(t_node->c_num== 1)
{
f_node->l_tree= node;
}
else
{
f_node->r_tree= node;
}
//入栈
PTNodett_node = NULL;
tt_node= new struct tag_node;
memset(tt_node,0,sizeof(structtag_node));
tt_node->node= node;
tt_node->c_num= 0;
s_node.push(tt_node);
}
}
return0;
}
/**
* 非第归方式，先根序遍历
* */
void pre_traversal(PBNode root)
{
if(root== NULL)
return;
stack<PBNode >s_node; //维护的栈
PBNodep = root;//用于循环
while(!s_node.empty()|| p != NULL)//循环到最后的结束条件就是：栈为空而且p指向NULL
{
if(p== NULL)
{
p= s_node.top();
s_node.pop();
p= p->r_tree;
}
else
{
cout<<p->value;
s_node.push(p);
p= p->l_tree;
}
}
}
/**
* 非第归方式，中序遍历
* */
void in_traversal(PBNode root)
{
if(root== NULL)
return;
stack<PBNode >s_node; //维护的栈
PBNodep = root;//用于循环
while(!s_node.empty()|| p != NULL)//循环到最后的结束条件就是：栈为空而且p指向NULL
{
if(p== NULL)
{
p= s_node.top();
s_node.pop();
cout<<p->value;
p= p->r_tree;
}
else
{
s_node.push(p);
p= p->l_tree;
}
}
}
/**
* 非第归方式，后序遍历
* */
void post_traversal(PBNode root)
{
if(root== NULL)
return;
stack<PBNode >s_node; //维护的栈
s_node.push(root);
PBNodep = root;//用于循环
PBNodelast_visit = NULL;//标记最后一次访问的节点
while(!s_node.empty())//由于时后序遍历，根节点被最后访问，所以当栈为空时循环结束
{
p= s_node.top();
//由于入栈顺序，一定可以保证左节点，先于右节点被访问，当只有一个左节点时last_visit==p->l_tree成立
//当只有一个右节点时，或者右两个节点时，last_visit==p->r_tree成立时，一定已经访问了左节点
if( (p->l_tree == NULL &&p->r_tree == NULL) || ((last_visit != NULL) && (last_visit ==p->l_tree || last_visit == p->r_tree)))
{
cout<<p->value;
last_visit= p;
s_node.pop();
}
else
{
if(p->r_tree!= NULL)
s_node.push(p->r_tree);
if(p->l_tree!= NULL)
s_node.push(p->l_tree);
}
}
}
/**
* 释放节点空间
* */
void free_node(PBNode *node)
{
if(*node== NULL)
return;
delete(*node);
*node= NULL;
}
/**
* 销毁二叉树
* */
void destory_tree(PBNode *root)
{
if(*root== NULL)
return;
destory_tree(&((*root)->l_tree));
destory_tree(&((*root)->r_tree));
free_node(root);
}
int main()
{
PBNoderoot = NULL;
if(preCreate(&root,(char*)"ABD##EF###CG#H###") != 0)
{
cout<<"创建失败！！"<<endl;
return-1;
}
cout<<"创建成功!!"<<endl;
cout<<"先序遍历为："<<endl;
pre_traversal(root);
cout<<endl;
cout<<"中序遍历为："<<endl;
in_traversal(root);
cout<<endl;
cout<<"后序遍历为："<<endl;
post_traversal(root);
cout<<endl;
//销毁二叉树
destory_tree(&root);
return0;
}
参考资料
http://www.cnblogs.com/llhthinker/p/4906631.html
http://www.cnblogs.com/bugking/p/3655200.html
http://www.cnblogs.com/mcgrady/archive/2013/09/05/3304545.html
http://www.cnblogs.com/wing011203/archive/2013/04/12/3016409.html
http://www.cnblogs.com/maybe2030/p/4732377.html
http://www.cnblogs.com/llhthinker/p/4747962.html
http://www.cnblogs.com/kaituorensheng/p/3788533.html
http://blog.csdn.net/chrisblogtk/article/details/51099878
https://wenku.baidu.com/view/100701a276eeaeaad0f33069.html
http://www.cnblogs.com/Romi/archive/2012/08/30/2664575.html
http://blog.csdn.net/zhangxiangdavaid/article/details/37115355
http://www.cnblogs.com/linzhehuang/p/6822847.html
百度百科相关词条