前言：
现时我们对“森林的后序遍历序列”大体比较关切，姐妹们都想要了解一些“森林的后序遍历序列”的相关知识。那么小编也在网上搜集了一些对于“森林的后序遍历序列””的相关内容，希望兄弟们能喜欢，咱们快快来学习一下吧！树
1.概念
树结构是一种描述非线性层次关系的数据结构
在一个数结构中，有且仅有一个结点没有直接前驱，这个结点就是树的结点。
除根结点外，其余每个结点有且仅有一个直接前驱。
每个结点可以有任意多个直接后继。
2.树的术语
根：有且仅有一个无直接前驱结点的结点
结点的度：结点拥有的子数的数量叫做结点的度
树的度：树内结点的度的最大值
叶子：终端结点
结点的层：从根算起。根为第一层，往下则+1层
树的深度：树的最大层数
森林：去掉根结点所得子数的个数
这里给大家分享一份二叉树与红黑树电子书籍及视频学习，需要的朋友可以后台私信【二叉树】获取
3.二叉树
什么是二叉树
结点最多只有两个儿子，叫做二叉树
二叉树的重要性质
第i层上最多有2^(i-1)个结点
深度为k的的二叉树最多有2^k - 1个结点
N0表示叶结点个数，N2表示度为2的非叶结点个数，那么N0=N2+1
二叉数的存储
顺序存储：一般通过结构数组进行存储
链式存储：存储结构包含结点元素及分别指向左子树和右子树的引用
//链式存储
typedef struct treeNode
{
void* NodeData; // 元素数据
struct treeNode* LtreeNode; //左子树结点引用
struct treeNode* RtreeNode; // 右子树结点引用
}TreeNode_T;
二叉树的遍历
先序遍历：1.访问根结点 2.访问椰子树 3.访问右子树
中序遍历：1.访问左子树 2.访问根结点 3.访问右子树
后序遍历：1.访问左子树 2.访问右子树 3.访问根结点
层次遍历：从根结点开始，向下一层一层访问，每层从左到右访问每个结点
如何具体实现？首先需要分析，二叉树遍历的核心问题，需要存储结构保存暂时不访问的结点，可以借助其他数据结构完成，如队列、堆栈
二叉树的先、中、后序递归遍历
核心思想：使用堆栈，先进后出
二叉树的层次遍历
核心思想：使用队列，先进先出，首先根结点入队，当结点出队，访问该结点、将其左右儿子入队
伪代码实现如下
先序遍历的递归实现
void PreOrderTraversal( BinTree BT)
{
if( BT ){
printf("%d",BT->Data);
PreOrderTraversal( BT->left);
PreOrderTraversal( BT->right);
}
}
先序遍历的非递归实现
void InOrderTraversal(BinTree BT)
{
BinTree T=BT;
Stack S = CreatStack(MaxSize);
while(T || !IsEmpty(S) ){
while(T){ //向左一直压栈
printf("%d",T->Data); //访问
Push(S,T);
T = T->Left;
}
if( !IsEmpty(s) ){
T=Pop(s); //结点弹出堆栈
T = T->Righr; //转向右结点
}
}
}
中序遍历的递归实现
void PreOrderTraversal( BinTree BT)
{
if( BT ){
PreOrderTraversal( BT->left);
printf("%d",BT->Data);
PreOrderTraversal( BT->right);
}
}
中序遍历的非递归实现
void InOrderTraversal(BinTree BT)
{
BinTree T=BT;
Stack S = CreatStack(MaxSize);
while(T || !IsEmpty(S) ){
while(T){ //向左一直压栈
Push(S,T);
T = T->Left;
}
if( !IsEmpty(s) ){
T=Pop(s); //结点弹出堆栈
printf("%d",T->Data); //访问
T = T->Righr; //转向右结点
}
}
}
后序遍历的递归实现
void PreOrderTraversal( BinTree BT)
{
if( BT ){
PreOrderTraversal( BT->left);
PreOrderTraversal( BT->right);
printf("%d",BT->Data);
}
}
标签： #森林的后序遍历序列
