二叉树存储结构及遍历方式
二叉树
tree
二叉树是树的一种特殊结构，有以下特征：
- 每个结点最多有两颗子树，结点的度最大为2。
- 左子树和右子树是有顺序的，次序不能颠倒。
- 即使某结点只有一个子树，也要区分左右子树。
定义
简单来说，满足如下定义的就可以称为二叉树：
- 本身是有序树；
- 树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；
如下是二叉树与非二叉树
二叉树与非二叉树
性质
二叉树的性质
-
非空二叉树第 i 层最多
个结点 （i >= 1）
-
深度为 k 的二叉树最多
个结点 （k >= 1）
-
度为 0 的结点数为
，度为 2 的结点数为
，则
-
有 n 个结点的完全二叉树深度
-
对于含 n 个结点的完全二叉树中编号为 i （1 <= i <= n） 的结点
- 若 i = 1，为根，否则双亲为 ⌊ i / 2 ⌋
-
若 2i > n，则 i 结点没有左孩子，否则孩子编号为 2i
-
若 2i + 1 > n，则 i 结点没有右孩子，否则孩子编号为 2i + 1
性质3计算方法：
可以由两个方程联立解得，假设度为0、1、2的节点个数分别为
,总节点数为
方程一(从节点个数看):
方程二(从节点连线数看):
假设分支连线数为
,那么由于每增加一个节点就会增加一条连线，而二叉树节点为1的时候是没有连线的，所以它们的关系是：
,而
最后得到第二个方程，即：
分支连线数示意图
联立方程一和方程二可以得到：
特别的二叉树
斜树
斜树
满二叉树
image-20200422230518546
完全二叉树
定义：对一棵具有n个结点的二叉树按层序排号，如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同，就是完全二叉树。
完全二叉树
完全二叉树性质：
- 具有
个结点的完全二叉树的深度为
- 如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有：
- 如果i=1，则节点是二叉树的根，无双亲，如果i>1，则其双亲节点为[i/2]，向下取整
- 如果2i>n那么节点i没有左孩子，否则其左孩子为2i(没有左孩子的话肯定没有右孩子)
- 如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1
二叉树的数据结构
链式存储结构
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
存储结构示意图如下：
存储结构示意图
在某些实际场景中，可能会做 "查找某节点的父节点" 的操作，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点，如图 4 所示：
自定义二叉树链式存储结构
顺序存储结构
需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。
普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可：
普通二叉树的转换
按照层次遍历的顺序一层一层的假如到顺序存储结构中去存储，可以使用数组或者STL中的vector，如下：
顺序存储
二叉树的遍历
二叉树遍历：从树的根节点出发，按照某种次序依次访问二叉树中所有的结点，使得每个结点被访问仅且一次。
这里有两个关键词：访问和次序。
深度遍历（类似DFS）
遍历的三种方式：
-
前序遍历：先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右。
-
中序遍历：先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右。
-
后序遍历：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。
二叉树遍历方法
递归方法
递归**的前序遍历、中序遍历以及后续遍历都可以使用下面的框架
void traverse(TreeNode root) {
// 前序遍历
traverse(root.left)
// 中序遍历
traverse(root.right)
// 后序遍历
}
非递归方法
前序遍历
处理过程
对于任一结点P：
-
访问结点P，并将结点P入栈;
-
判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1;若不为空，则将P的左孩子置为当前的结点P;
-
直到P为NULL并且栈为空，则遍历结束。
代码如下：
void preOrder2(BinTree *root) //非递归前序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->data<<"";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
中序遍历
处理过程
对于任一结点P，
-
若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
-
若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
-
直到P为NULL并且栈为空则遍历结束
代码如下：
void inOrder2(BinTree *root) //非递归中序遍历
{
stack<BinTree*> s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<<p->data<<"";
s.pop();
p=p->rchild;
}
}
}
后续遍历
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。
下面提供一种思路：
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈(因为是栈，后进先出)，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
代码如下：
void postOrder3(BinTree *root) //非递归后序遍历
{
stack<BinTree*> s;
BinTree *cur; //当前结点
BinTree *pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<""; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
}
层次遍历（类似BFS）
借助于队列可以实现层次遍历，按照树从上往下一层一层的遍历
处理过程
- 首先建立一个队列q，将根节点push进去
- 当队列q非空的时候，取出q最前面的元素front()，然后pop(),访问该元素的指，并且将该元素的左右节点push进去队列q(NULL节点除外)
- 直到q全空
代码相对比较简单，就不贴了。。。
参考：
