二叉树的前序,中序,后序非递归遍历(C&C++)
程序员文章站
2024-01-15 19:47:46
...
前序遍历示意:
中序遍历示意:
后序遍历示意:
实现:
void Visit(int n)
{
cout << n;
}
void NRPreOrder(BiTree bt)
{
BiTree S[MAXSIZE], p = bt;
int top = -1;
if (bt == NULL) return;
while (!(!p && top == -1))//p与栈均不空时继续循环
{
while (p)
{
Visit(p->data); //入栈时访问
S[++top] = p;
p = p->lchird;
} //循环访问左子树并入栈
if (top == -1) return; //栈空时返回
else
{
p = S[top--]; //出栈,该节点使用完毕,不会再经过该节点
p = p->rchird; //p指向右子树
}
}
cout << endl;
}
void NRInOrder(BiTree bt)
{
BiTree S[MAXSIZE], p = bt;
int top = -1;
if (bt == NULL) return;
while (!(!p && top == -1)) //p与栈均不空时继续循环
{
while (p)
{
S[++top] = p;
p = p->lchird; //循环访问左子树并入栈
}
if (top == -1) return; //栈空时返回
else
{
p = S[top--];
Visit(p->data); //出栈并访问,该节点使用完毕,不会再经过该节点
p = p->rchird; //p指向右子树
}
}
cout << endl;
}
void NRPostOrder1(BiTree bt)
{
BiTree S[MAXSIZE], antiPre[MAXSIZE], p = bt;
int top = -1, cnt = -1;
if (bt == NULL) return;
while (!(!p && top == -1))
{
while (p)
{
antiPre[++cnt] = p; //不访问,入栈时同时入逆前置栈
S[++top] = p;
p = p->rchird; //注意,这里首先遍历右子树
}
if (top == -1) return;
else
{
p = S[top--];
p = p->lchird; //p指向左子树
}
}
for (int i = cnt; i >= 0; i--)
Visit(antiPre[i]->data); //出逆前置栈,同时访问节点;
cout << endl;
}
void NRPostOrder2(BiTree bt)
{
BiTree S[MAXSIZE], p = bt;
int flag[MAXSIZE] = { 0 }; //构建标志量
int top = -1;
if (bt == NULL) return;
while (!(!p && top == -1))
{
while (p)
{
S[++top] = p;
flag[top] = 1; //第一次经过该节点,标志量置1
p = p->lchird;
} //循环访问左子树并入栈
if (top == -1) return;
p = S[top];
if (flag[top] == 1)
{
flag[top] = 2; //第二次经过该节点,标志量置2
p = p->rchird;
}
else
{ // 节点已被经过两次,第三次经过该节点时,出栈并访问
p = S[top--];
Visit(p->data);
p = NULL; //重置p指针
}
}
cout << endl;
}
void NRPostOrder3(BiTree bt)
{
BiTree S[MAXSIZE], p = bt, Pre = NULL; //构建记忆树
int top = -1;
if (bt == NULL) return;
while (!(!p && top == -1))
{
while (p)
{
S[++top] = p;
p = p->lchird;
}
if (top == -1) return;
//栈顶节点右孩子为空或右子树已被遍历过,则栈顶节点出栈并访问
if (S[top]->rchird == NULL || S[top]->rchird == Pre)
{
p = S[top--];
Visit(p->data);
Pre = p; //Pre指向刚刚被遍历过的节点
p = NULL;
}
else
{
p = S[top]->rchird;
}
}
cout << endl;
}
测试结果:
推荐阅读
-
二叉树的前序,中序,后序非递归遍历(C&C++)
-
二叉树模板 先中后序遍历,非递归算法,层次遍历,叶子结点数,深度
-
leetcode 106. 从中序与后序遍历序列构造二叉树 105. 从前序与中序遍历序列构造二叉树思考分析
-
Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】
-
Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】
-
Python实现二叉树前序、中序、后序及层次遍历示例代码
-
Python利用前序和中序遍历结果重建二叉树的方法
-
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
[PHP] 算法-根据前序和中序遍历结果重建二叉树的PHP实现