首页 > 代码库 > 二叉树的存储方式以及递归和非递归的三种遍历方式
二叉树的存储方式以及递归和非递归的三种遍历方式
树的定义和基本术语
树(Tree)是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：
(1)有且仅有一个特定的称为根(Root)的结点；
(2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3…Tm，其中每个子集又是一棵树，并称其为子树(Subtree)。
树形结构应用实例：
1、日常生活：家族谱、行政组织结构；书的目录
2、计算机：资源管理器的文件夹；
编译程序：用树表示源程序的语法结构；
数据库系统：用树组织信息；
分析算法：用树来描述其执行过程；
3、表达式表示 ( 如 a * b + (c – d / e) * f )
专业术语
1、结点的度(degree)：某结点的子树的分支个数
叶子(leaf)（终端结点），分支结点（非终端结点），内部结点（B、C、D、E、H），树的度（3）
2、结点的孩子(child)
双亲(parent)（D为H、I、J的双亲）
兄弟(sibling)(H、I、J互为兄弟)
祖先，子孙(B的子孙为E、K、L、F)
3、结点的层次
根结点为第一层。某结点在第 i 层，其孩子在第 i+1 层。
树的深度(depth)就是从跟开始往下数
堂兄弟：双亲在同一层的结点，互为堂兄弟
4、有序树和无序树
有序树：
无序树：
5、森林(forest)是 m (m≥0) 棵互不相交的树的集合。
对比树型结构和线性结构的结构特点
线性结构：第一个元素无前驱，最后一个元素无后继，其它数据元素一个前驱、一个后继。（唯一头结点，唯一尾节点；中间结点有唯一前驱，唯一后继）
树形结构：根节点无前驱，多个叶子节点无后继，其它元素一个前驱，多个后继。（唯一根结点；多个叶结点；中间结点有唯一前驱，多个后继）
二叉树
把满足以下两个条件的树型结构叫做二叉树（Binary Tree）：
（1）每个结点的度都不大于2；
（2）每个结点的孩子结点次序不能任意颠倒。即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。
二叉树一共有5种形态
二叉树的性质
性质1： 在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。
采用归纳法证明此性质。
（1）当i=1时，2^( i-1)=2^0 =1,命题成立。
（2）假定i=k时命题成立，即第k层最多有2^(k-1)个结点；
（3）由归纳假设可知，由于二叉树每个结点的度最大为2，故在第k+1层上最大结点数为第k层上最大结点数的2倍，
即2×2^(k-1)＝2^k=2^(k+1)-1
命题得到证明。
性质2 ：深度为 k 的二叉树至多有 2^k-1个结点(k≥1)。
证明：由性质1可见，深度为k的二叉树的最大结点数为
性质3： 对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。
证明：设二叉树上结点总数 n = n0 + n1 + n2 （1）
又二叉树上分支总数 b = n1+2n2 （2）
而除根结点外，其余结点都有分支进入，即 b = n-1
将（1）（2）式代入，得 n0 = n2 + 1 。
两类特殊的二叉树：满二叉树和完全二叉树
满二叉树：一棵深度为k且有2^k-1个结点的二叉树。
完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。（编号的规则为，由上到下，从左到右。）
性质4：具有n个结点的完全二叉树的深度为[log2 n]＋1。
证明：假设此二叉树的深度为k，则根据性质2及完全二叉树的定义得到：
2^(k-1)－1<n<=2^k-1 或 2^(k-1)<=n<2^k
取对数得到：k－1 <= log2 n < k 因为k是整数。所以有：k＝【log2n】＋1。
性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第【log2n】+1层，每层从左到右),则对任一结点i（1<=i<=n),有：
1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点【i/2】。
2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。
3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。
所示为完全二叉树上结点及其左右孩子结点之间的关系。
二叉树的存储结构
1）顺序存储结构
完全二叉树：用一组连续的存储单元依次自上而下、自左至右存储各结点元素。即将完全二叉树上编号为i 的结点的值存储在下标为 i-1 的数组元素中。结点间的关系可由公式计算得到。
一般情形的二叉树：增添一些空结点使变成完全二叉树形态，再按上述方法存储。
如图完全二叉树的存储
单只二叉树的存储
总结：
1、完全二叉树用顺序存储既节约空间，存取也方便；
2、一般二叉树用顺序存储，空间较浪费，最坏情况为右单支二叉树。（一个深度为K且只有K个节点的单支树却需要长度为2^k-1的一维数组）
2）二叉树的链式存储方式
常用的有二叉链表和三叉链表存储结构结点的左右孩子或双亲靠指针来指示
有时也可用数组的下标来模拟指针,即开辟三个一维数组Data ,lchild,rchild 分别存储结点的元素及其左,右指针域;下面是链式存储的二叉树表示：
typedef struct BiNode{ int data;//数据域
BiNode *lchild, *rchild;//左右孩子指针} BiNode, *BiTree;二叉树链表表示的示例：
遍历二叉树和线索二叉树
任何一个非空的二叉树都由三部分构成
树的遍历是访问树中每个结点仅一次的过程。遍历可以被认为是把所有的结点放在一条线上，或者将一棵树进行线性化的处理。
先序遍历
DLR根左右：访问根结点、先序遍历左子树、先序遍历右子树
若二叉树非空
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树；
若二叉树为空，结束——基本项（也叫终止项）
若二叉树非空——递归项
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树；
主要过程就是递归调用，也可以用栈来实现。
对于先序遍历来说，蓝色剪头第一次经过的结点，就是遍历的序列，以后再次经历就不算进去了。
typedef struct BiNode{ int data;//数据域
BiNode *lchild, *rchild;//左右孩子指针} BiNode, *BiTree;void preorder(BiNode *root){ if (root != NULL) { //访问根节点
cout << "先序遍历" << root->data;
preorder(root->lchild);
preorder(root->rchild);
}// end of if}
非递归的先序遍历
根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：
对于任一结点P：
1)访问结点P，并将结点P入栈;
2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空，则遍历结束。
//关键在于何时访问的语句的位置void preorder(BiTree root){ //初始化栈
stack<BiTree> nodes;
BiNode *p = root; while (p != NULL || !nodes.empty()) { while (p != NULL) { //根左右的顺序遍历
cout << p->data; //进栈 nodes.push(p); //继续移动
p = p->lchild;
} //p == null
if (!nodes.empty()) { //对 p 重新指向
p = nodes.top(); //出栈 nodes.pop(); //转到右子树
p = p->rchild;
}
}
}
中序遍历、后序遍历和先序遍历思想基本类似，对于中序遍历来说，蓝色剪头第二次经过的结点，就是遍历的序列，之前的和以后的再次经历就不算进序列里去了。对于后序遍历来说，蓝色剪头第三次经过的结点，就是遍历的序列，之前经历的就不算进去了。
LDR左跟右：中序遍历左子树、访问根结点、中序遍历右子树
若二叉树非空
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树；
若二叉树为空，结束——基本项（也叫终止项）
若二叉树非空——递归项
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树；
中序递归遍历算法
void inOrder(BiNode *root){ if (root != NULL) {
inOrder(root->lchild);
cout << "先序遍历" << root->data;
inOrder(root->rchild);
}// end of if}
中序的非递归遍历，使用栈
//非递归的中序遍历二叉树void inOrder(BiTree root){ //非递归中序遍历（左跟右）
stack<BiTree> nodes;//初始化栈 //指示指针
BiNode *p = root; //遍历二叉树的循环语句
while (p != NULL || !nodes.empty()) { while (p != NULL) { //不为空就入栈 nodes.push(p); //一直向做走，直到为 kong
p = p->lchild;
} // 需要判断空否，因为需要出栈操作
if (!nodes.empty()) { //令 p 重新指向 栈顶结点
p = nodes.top(); //访问根节点（栈顶结点）
cout << p->data << " "; //使用完毕，弹出 nodes.pop(); //向右遍历
p = p->rchild;
}
}// end of while}
LRD左右跟：后序遍历左子树、后序遍历右子树、访问根结点
后序遍历序列:BDFGECA
//递归后续遍历二叉树void lastOrder(BiTree root){ if (root != NULL) {
lastOrder(root->lchild);
lastOrder(root->rchild);
cout << root->data;
}
}
同理有非递归的后续遍历二叉树
在后序遍历中，要保证左孩子和右孩子都已被访问，并且左孩子在右孩子访问之后才能访问根结点。因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
void postOrder3(BiTree root) //非递归后序遍历{
stack<BiTree> nodes; //当前结点
BiNode *cur; //前一次访问的结点
BiNode *pre = NULL; //根节点入栈 nodes.push(root); //依次遍历左右子树
while(!nodes.empty())
{
cur = nodes.top(); //判断 cur 结点的左右孩子子树的情况
if((cur->lchild == NULL && cur->rchild == NULL) ||
(pre != NULL && (pre == cur->lchild || pre == cur->rchild)))
{ //如果当前结点没有孩子结点或者孩子节点都已被访问过
cout << cur->data; //出栈 nodes.pop(); //前一次访问的结点， pre标记已经访问的结点
pre = cur;
} else
{ //左右跟的访问顺序，关键还是访问语句的位置！！！一定是先写右子树，再写左子树，顺序不能错 //如果当前结点的右子树不为空
if(cur->rchild != NULL){
nodes.push(cur->rchild);
} //如果当前结点的左子树不为空
if(cur->lchild != NULL){
nodes.push(cur->lchild);
}
}
}
}
二叉树遍历的总结：
无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根节点出发，逆时针延二叉树外缘移动，对每个节点均途经三次。
先序遍历：第一次经过节点时访问。（ABCD）
中序遍历：第二次经过节点时访问。（BADC）
后序遍历：第三次经过节点时访问。（BDCA）
二叉树的存储方式以及递归和非递归的三种遍历方式