[Data Structure]使用非遞回的方法對二叉樹進行先序、中序、后續遍歷
#include<bits/stdc++.h>
using namespace std;
typedef struct tree//構建一棵樹的結點
{
int data;//這里的data其實用來放編號了，結點里并沒有存資料
tree *left;//指向子樹的指標
tree *right;
}tree;
void LRD(tree* p,int n)//后序遍歷函式
{
int*flag=(int*)malloc(sizeof(int)*n);//標記陣列
stack<tree*> wood;
tree*node1;
tree*node2;
while(1)
{
while(p)
{
node1=p;
*(flag+(node1->data))=1;//讀到后進行標記再入堆疊
wood.push(node1);
p=p->left;//指向左子樹（LRD）
}
if(wood.empty())break;
node2=wood.top();//取出堆疊頂元素
wood.pop();
if(*(flag+(node2->data)))//如果已經標記過
{
*(flag+(node2->data))=0;//回溯
p=node2->right;//指向右子樹，并將node2入堆疊
wood.push(node2);
}
else
{
cout<<node2->data<<" ";
p=NULL;
}
}
cout<<endl;
}
void LDR(tree* p)//中序遍歷函式
{
stack<tree*> wood;//設定堆疊來儲存已經遍歷到但是不該輸出的
tree* node = p;
while(1)
{
while(p)//將P的左子樹入堆疊
{
wood.push(p);
p=p->left;
}
if(wood.empty())break;//處理結束整個堆疊后完成
p=wood.top();//將堆疊頂元素取出
wood.pop();
cout<<p->data<<" ";//輸出堆疊頂元素
p=p->right;//將指標指向右子樹
}
cout<<endl;
}
void DLR(tree* p)//先序遍歷函式（基本和中序遍歷一樣，不詳細注釋）
{
stack<tree*> wood;
tree* node = p;
while(1)
{
while(p)
{
cout<<p->data<<" ";
wood.push(p);
p=p->left;
}
if(wood.empty())break;
p=wood.top();
wood.pop();
p=p->right;
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout<<"Input the number of tree node"<<endl;//輸入整棵樹的結點個數
int n;cin>>n;
tree*p=(tree*)malloc(sizeof(tree)*n);//分配等同于結點個數的結點空間
for(int i=0;i<n;i++)//這個回圈在構建一棵樹，這里的data輸入的是樹上的編號
{
(p+i)->data=i;
if(i*2+1<n)
(p+i)->left=p+(i*2+1);
else
(p+i)->left=NULL;
if(i*2+2<n)
(p+i)->right=p+(i*2+2);
else
(p+i)->right=NULL;
}
cout<<"先序遍歷"<<endl;
DLR(p);
cout<<"中序遍歷"<<endl;
LDR(p);
cout<<"后序遍歷"<<endl;
LRD(p,n);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/237097.html
標籤：其他
上一篇：promise
下一篇：Android ——之流式布局