二叉树的遍历操作(含非递归)
作者:
小熊不开心
,
2021-12-09 08:17:51
,
所有人可见
,
阅读 291
#include<iostream>
using namespace std;
#define MAX_SIZE 100010
typedef struct BiTNode{
char data; //数据域
struct BiTNode *lchild, *rchild; //指针域
}BiTNode,*BiTree;
typedef struct Node{
BiTree bitnode;
bool isfirst;
}node,*bitree;
//创建二叉树
BiTree Creat(){
BiTree bt;
char ch;
cin >> ch;
if(ch == '#') bt = nullptr;
else{
bt = new BiTNode();
bt->data = ch;
bt->lchild = Creat();
bt->rchild = Creat();
}
return bt;
}
//销毁二叉树
void Release(BiTree bt){
if (bt == nullptr) return;
else{
Release(bt->lchild);
Release(bt->rchild);
delete bt;
}
cout << "delete" << endl;
}
//前序递归遍历
void PreOrder(BiTree bt){
if(bt == nullptr) return;
cout << bt->data << "\t";
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
//前序非递归遍历
void PreOrder2(BiTree bt){
BiTree p = bt, stk[MAX_SIZE];
int tt = 0;
while(p != nullptr || tt > 0){
if(p != nullptr){
//入栈访问
stk[++tt] = p;
cout << p->data << "\t";
//遍历左子树
p = p->lchild;
}else{
//出栈遍历右子树
p = stk[tt--];
p = p->rchild;
}
}
return ;
}
//中序遍历
void InOrder(BiTree bt){
if(bt == nullptr) return;
InOrder(bt->lchild);
cout << bt->data << "\t";
InOrder(bt->rchild);
}
//中序非递归遍历
void InOrder2(BiTree bt){
BiTree p = bt, stk[MAX_SIZE];
int tt = 0;
//根结点(这里的根不一定是整个树的根结点)不为空或栈不为空
while(p != nullptr || tt > 0){
//(子节点的)根结点不为空
if(p != nullptr){
//root入栈
stk[++tt] = p;
//遍历左子树
p = p->lchild;
}else{
//p的根结点出栈并访问 p = proot
p = stk[tt--];
cout << p->data << "\t";
//遍历右子树
p = p->rchild;
}
}
return ;
}
//后序遍历
void PostOrder(BiTree bt){
if(bt == nullptr) return;
PostOrder(bt->lchild);
PostOrder(bt->rchild);
cout << bt->data << "\t";
}
/*
第一种思路:对于任一结点P,将其入栈,然后沿其左子树一直往下搜索,
直到搜索到没有左孩结点,此时该结点出现在栈顶,但是此时不能将其出栈并访问,
因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理,
当访问完其右孩子时,该结点又出现在栈顶,此时可以将其出栈并访问。
这样就保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出现在栈顶,
只有第二次出现在栈顶时,才能访问它。
因此需要多设置一个变量标识该结点是 否是第一次出现在栈顶。
*/
void PostOrder2(BiTree bt){
BiTree p = bt;
//带有标识变量的树 类似双栈
bitree btn, q, stk[MAX_SIZE];
int tt = 0;
while(p != nullptr || tt > 0){
if(p != nullptr){
btn = new node();
btn->bitnode = p;
btn->isfirst = true;
stk[++tt] = btn;
p = p->lchild;
}else{
q = stk[tt--];
/*
p为null 出栈/还是遍历右子树 根据标识判断
若栈顶标识为true 则刚刚的p为左子树,则现在将标识置false,遍历右子树
若栈顶标识为false 则刚刚的p为右子树,将p置空,栈顶出栈并访问
*/
if(q->isfirst == true){
q->isfirst = false;
stk[++tt] = q;
p = q->bitnode->rchild;
}else{
cout << q->bitnode->data << "\t";
p = nullptr;
}
}
}
return ;
}
/*
第二种思路:
要保证根结点在左子树在右子树访问之后才能访问,因此对于任一结点P,先将其入栈。
如果P不存在左子树在右子树,则可以直接访问它;
或者P存在左子树在右子树,但是其左子树在右子树都已被访问过了,
则同样可以直接访问该结点。
若非上述两种情况,则将P的右孩子和左孩子依次入栈,
这样就保证了 每次取栈顶元素的时候,左子树在右子树前面被访问,
左子树和右子树都在根结点前面被访问。
*/
void PostOrder3(BiTree bt){
if(bt == nullptr) return ;
//pre: 已访问的结点 cur:当前结点
BiTree cur = bt, pre = nullptr, stk[MAX_SIZE];
int tt = 0;
stk[++tt] = cur;
while(tt > 0){
cur = stk[tt];
if(
(cur->lchild == nullptr && cur->rchild == nullptr) ||
//只要pre等于cur任意一个子树 则说明else分支已经走完=左右子树已遍历完
((pre == cur->lchild || pre == cur->rchild) && pre != nullptr)
){
cout << cur->data << "\t";
pre = stk[tt--];//等价于 pre = cur tt--;
}else{
//这里入栈顺序不能改变 一定是右子树在左子树之前入栈
//才能保证出栈访问时 左子树先于右子树被访问
if(cur->rchild != nullptr) stk[++tt] = cur->rchild;
if(cur->lchild != nullptr) stk[++tt] = cur->lchild;
}
}
return ;
}
//层序遍历
void LevelOrder(BiTree bt){
BiTree queue[MAX_SIZE], q = nullptr;
int head = 0,tail = -1;
if(bt == nullptr) return;
//root入队
queue[++tail] = bt;
//队列不为空
while(tail >= head){
//先取值后出队
q = queue[head++];
cout << q->data << "\t";
if(q->lchild != nullptr) queue[++tail] = q->lchild;
if(q->rchild != nullptr) queue[++tail] = q->rchild;
}
}
int main(){
BiTree root = Creat();
cout << "Pre: ";
PreOrder2(root);
cout << endl << "In: ";
InOrder(root);
cout << endl << "Post: ";
PostOrder3(root);
cout << endl << "Level:";
LevelOrder(root);
Release(root);
return 0;
}