非递归遍历二叉树---c++写法
2023-09-14 09:13:37 时间
前序遍历的非递归算法
#include<iostream>
using namespace std;
#include<stack>
struct node
{
char data;
node* lchild;
node* rchild;
};
//树的建立---前序建立
void creatTree(char ch[10],node*& root)
{
static int i = 0;
if (ch[i] == '#')
{
i++;
root = NULL;
return;
}
else
{
root = new node;
root->data = ch[i];
i++;
creatTree(ch, root->lchild);
creatTree(ch, root->rchild);
}
}
//非递归遍历
void display(node* root)
{
stack<node*> s;
node* p = root;
//当p为空,栈也为空的时候退出循环
while (p != NULL || !s.empty())
{
while (p!=NULL)
{
cout << p->data << endl;
s.push(p);
p = p->lchild;
}
//当发现一个根的左子树为空,那么弹出栈顶元素,走其右子树
if (!s.empty())
{
p = s.top();
s.pop();
p = p->rchild;
}
}
}
//测试---------------------
void test()
{
node* root=NULL;
char ch[10] = "AB#D##C##";
creatTree(ch,root);
display(root);
}
int main()
{
test();
system("pause");
return 0;
}
中序遍历的非递归算法
#include<iostream>
using namespace std;
#include<stack>
struct node
{
char data;
node* lchild;
node* rchild;
};
//树的建立---前序建立
void creatTree(char ch[10],node*& root)
{
static int i = 0;
if (ch[i] == '#')
{
i++;
root = NULL;
return;
}
else
{
root = new node;
root->data = ch[i];
i++;
creatTree(ch, root->lchild);
creatTree(ch, root->rchild);
}
}
//非递归遍历
void display(node* root)
{
stack<node*> s;
node* p = root;
//当p为空,栈也为空的时候退出循环
while (p != NULL || !s.empty())
{
while (p != NULL)
{
s.push(p);
//先找到左子树最左下的节点,为中序的第一个节点
p = p->lchild;
}
//当发现一个根的左子树为空,那么弹出栈顶元素,走其右子树
if (!s.empty())
{
//当找到最下面的左子树时,会先弹出最下面左子树的节点然后进行输出
//因为当前左子树为叶子节点,没有左右孩子,所以上面的while循环会直接跳过,当再次来到if语句里面时,会弹出最后左子树的根节点,然后进行输出,再进行一次上面的循环输出右孩子
p = s.top();
cout << p->data << endl;
s.pop();
p = p->rchild;
}
}
}
//测试---------------------
void test()
{
node* root=NULL;
char ch[10] = "AB#D##C##";
creatTree(ch,root);
display(root);
}
int main()
{
test();
system("pause");
return 0;
}
后序遍历的非递归算法
#include<iostream>
using namespace std;
#include<stack>
struct node
{
char data;
node* lchild;
node* rchild;
};
struct element
{
node* ptr;
int flag; //1:第一次出栈 2:第二次出栈
};
//树的建立---前序建立
void creatTree(char ch[10],node*& root)
{
static int i = 0;
if (ch[i] == '#')
{
i++;
root = NULL;
return;
}
else
{
root = new node;
root->data = ch[i];
i++;
creatTree(ch, root->lchild);
creatTree(ch, root->rchild);
}
}
//非递归遍历
void display(node* root)
{
stack<element> s;
node* p = root;
element ele;
while (p||!s.empty())
{
if (p != NULL)//第一次入栈,访问左子树
{
ele.ptr = p; //用来保存节点,然后压入栈中
ele.flag = 1; //表明要访问左子树
s.push(ele);//将当前保存节点数据压入到栈中
p = p->lchild; //访问左孩子
}
else
{
ele = s.top();//获得即将出栈元素的节点数据
s.pop();//出栈
p = ele.ptr; //p指向当前要处理的节点
if (ele.flag == 1) //只访问过左子树还需要继续访问右子树
{
ele.flag = 2;//表示即将访问右孩子
s.push(ele);//第二次入栈
p = p->rchild;
}
else
{
//表明左右子树都访问过了
cout << p->data << endl;
p = NULL;//确保下次循环继续出栈
}
}
}
}
//测试---------------------
void test()
{
node* root=NULL;
char ch[10] = "AB#D##C##";
creatTree(ch,root);
display(root);
}
int main()
{
test();
system("pause");
return 0;
}
相关文章
- C++学习——c++逗号操作符说明(附加全部运算符优先级)
- c++中map遍历_怎么遍历map集合
- c++语言截取字符串,详解C++ string常用截取字符串方法
- C++实现二叉树层序遍历
- c++获取子类窗口句柄位置_C++中各种获取窗口句柄的方法「建议收藏」
- c# 字典树_c++树的遍历
- C++精通之路:map和set的介绍和有关oj题
- c++二叉树的先序,中序,后序遍历_二叉树的构造
- C++ map遍历(简单易记忆)[通俗易懂]
- C++基本概念_c语言 c++区别
- C++11学习笔记3
- C/C++ Qt 常用数据结构
- c++的链表-C++链表
- c++的链表-链表入门(C++)
- C/C++ 内存遍历与KMP特征搜索
- C/C++ BeaEngine 反汇编引擎
- C/C++ 遍历窗口标题类名
- C 和C++语言的标准
- 让 Python 拥有 C/C++ 一样的速度,编译神器 Codon 发布!
- Python 调用 C++详解编程语言
- C++友元函数和友元类(C++ friend)详解
- C++ &&、||、!逻辑运算符用法详解
- C++ return:使函数立即结束
- C++ auto(类型推导)精讲
- C++防止头文件被重复引入的3种方法(详解版)
- C/C++中利用空指针简化代码,提高效率
- c++中string类成员函数c_str()的用法
- c++中vector<int>和vector<int*>的用法区别
- c++获取进程信息列表和进程所调用的dll列表
- C++实现二叉树遍历序列的求解方法
- C++中重载、重写(覆盖)和隐藏的区别实例分析