后序遍历二叉树的非递归算法Word文件下载.docx
- 文档编号:4392191
- 上传时间:2023-05-03
- 格式:DOCX
- 页数:17
- 大小:18.42KB
后序遍历二叉树的非递归算法Word文件下载.docx
《后序遍历二叉树的非递归算法Word文件下载.docx》由会员分享,可在线阅读,更多相关《后序遍历二叉树的非递归算法Word文件下载.docx(17页珍藏版)》请在冰点文库上搜索。
1.输入扩展先序遍历序列并建立对应的二叉树.\n"
2.打印当前的二叉树的扩展先序遍历序列.\n"
3.后序遍历当前的二叉树并打印遍历序列.\n"
4.按其它任意键退出.\n"
请选择你要的操作:
"
scanf("
%d"
&
sel);
getchar();
Selection(sel,root);
voidSelection(intsel,BiTree*root){
//根据用户输入决定下一步骤
switch(sel){
case1:
ReadExPreOrder(root);
break;
case2:
PrintExPreOrder(*root);
case3:
PostOrderTraverse(*root);
default:
exit(0);
voidReadExPreOrder(BiTree*root){
//先序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针
charch;
ch=getchar();
if(ch=='
.'
)
*root=NULL;
else{
(*root)=(BiTree)malloc(sizeof(BiTNode));
(*root)->
data=ch;
ReadExPreOrder(&
((*root)->
lchild));
rchild));
voidPrintExPreOrder(BiTreeroot){
if(root!
=NULL){
ch=root->
data;
%c"
ch);
PrintExPreOrder(root->
lchild);
rchild);
else
."
voidPostOrderTraverse(BiTreeT){
BiTreestack[MAX_TREE_SIZE],p;
inttag[MAX_TREE_SIZE],top=0;
p=T;
while(p||top!
=0){
while(p){
top++;
stack[top]=p;
tag[top]=0;
p=p->
lchild;
//从根开始,左结点依次入栈
}
if(top>
0){
if(tag[top]==1){//表示是从该结点的右子树返回,则访问该结//点
p=stack[top];
printf("
p->
data);
top--;
p=NULL;
//将p指向NULL,则下次进入while循环时,不做左子//树入栈操作
}
else{//表明是从该结点左子树返回,应继续访问其右子树
if(top>
p=p->
rchild;
tag[top]=1;
//表明该结点的右子树已访问
}
}//endofelse
}//endofif
}//endofwhile
方法二(顺序栈):
#include<
iostream>
usingnamespacestd;
typedefstructnode
{
charch;
structnode*lchild;
structnode*rchild;
}node;
typedefstructbinarytree
node*head;
//指向根结点
}bt;
intn=0;
voidini(bt*&
b)
b=newbt;
b->
head=NULL;
voidprecreate(node*&
t)//先序递归建立二叉树
cout<
<
\n\n请输入结点数据,以'
代表空:
;
charc;
cin>
>
c;
if(c=='
)t=NULL;
else
n++;
t=newnode;
t->
ch=c;
precreate(t->
//--------------------------------------------------
//非递归算法需要栈
typedefstructstack{
node**base;
node**top;
intstacksize;
}stack;
voidini(stack&
s){
s.base=newnode*[100];
s.top=s.base;
s.stacksize=100;
voidpush(stack&
s,node*elem){
(*s.top++)=elem;
voidpop(stack&
s,node*&
elem){
elem=*(--s.top);
intisempty(stack&
if(s.base==s.top)return1;
elsereturn0;
voidgettop(stack&
s,node*&
t){
t=*(s.top-1);
voidafttraverse(node*t){//后序遍历非递归算法
stacks;
ini(s);
node*lastvist=NULL;
while(NULL!
=t||!
isempty(s)){
while(NULL!
=t){
push(s,t);
t=t->
gettop(s,t);
if(NULL==t->
rchild||lastvist==t->
rchild){
cout<
"
ch;
pop(s,lastvist);
t=NULL;
else
t=t->
intmain(){
bt*b;
ini(b);
precreate(b->
head);
//构造二叉树
\n\n后序遍历:
afttraverse(b->
\n\n"
方法三(链栈):
charitem;
structBiTNode*lchild,*rchild;
}BiTNode,*Tree;
typedefstructStack{
Treem;
structStack*next;
}Stack,*st;
TreeCreateTree()
TreeB;
ch=getchar();
if(ch=='
returnNULL;
{
B=(Tree)malloc(sizeof(BiTNode));
B->
item=ch;
lchild=CreateTree();
rchild=CreateTree();
returnB;
voidPostOrder(TreeT)
Treep,q;
sts,top;
intop;
p=T;
top=NULL;
do{
while(p!
=NULL)
{
s=(st)malloc(sizeof(Stack));
//使用链表形式存储栈,即//链栈
s->
m=p;
next=top;
top=s;
p=p->
op=1;
//该标志用于控制进入下面的while循环
q=NULL;
while(top!
=NULL&
&
op==1)
{
if(top->
m->
rchild==q)//若当前栈顶结点的右孩子是上次访问的结点,则打印该结点
printf("
top->
item);
//第一次时打印最左下边结点
q=top->
m;
//q记录上次访问的结点
top=top->
next;
//栈指针后移,即将该结点从栈中弹出
else//若当前栈顶结点的右孩子不是上次访问的结点,则先访问其右孩//子
p=top->
op=0;
//op用来控制往右走一步后跳出当前while循环,进入下//一次外层的while循环
}while(top!
=NULL);
intmain()
TreeT;
pleaseenterthechars:
\n"
T=CreateTree();
PostOrder(T);
return0;
方法四:
structTREE//二叉树结点结构
{
chardata;
structTREE*lsubtree;
structTREE*Rsubtree;
};
structTREE*tree;
voidcreatetree(structTREE*&
p)//先序创建二叉树
ch=getchar();
if(ch=='
\n'
)
p=NULL;
elseif(ch=='
else
p=(structTREE*)malloc(sizeof(structTREE));
//分配//结点空间
p->
createtree(p->
lsubtree);
//递归创建左子树
Rsubtree);
//递归创建右子树
}
voidlastorder(structTREE*tree)//非递归后序遍历
structTREE*p;
structTREE*s[100];
//用一个指针数组来用作栈
inttop=-1;
//下标
intmack[100];
//标志数组
p=tree;
do{
while(((p->
lsubtree)!
=NULL)&
(mack[top+1]!
=2))//循环//直到让p向左滑到最左子树,并且该结点非第二次入栈
{
top=top+1;
s[top]=p;
//每循环一次,当前结点入栈
mack[top]=1;
//结点第一次入栈时,标志为1
lsubtree;
//找最左子树
}//叶子结点无须入栈
%c\n"
p->
//输出末节点
p=s[top];
//出栈顶元素
top=top-1;
//每出一个栈顶元素,下标就后退一位
if(mack[top+1]==1)//若结点是第一次出栈,则再入栈
mack[top]=2;
//结点第二次入栈时,标志为2
Rsubtree;
//访问右子树
}
}while(top!
=-1);
//top==-1时,说明根结点刚访问完,跳出循环后//打印
s[0]->
//最后把根输出
intmain(){
printf("
请输入二叉树数据\n"
createtree(tree);
后序遍历结果:
lastorder(tree);
getchar();
方法五:
#definemaxsize50
#defineOK1
typedefstructBnode//声明二叉树的数据结构
structBnode*lchild,*rchild;
}bnode,*btree;
typedefstructtype
btreenode;
intflag;
}datatype,*pdatatype;
typedefstruct{//声明栈的数据结构
datatypedata[maxsize];
inttop;
}seqstack,*pseqstack;
btreecreatbtree()//创建二叉树
inti=0;
btreet;
c=getchar();
#'
{t=NULL;
i++;
}
t=(btree)malloc(sizeof(bnode));
data=c;
lchild=creatbtree();
rchild=creatbtree();
returnt;
intprintelem(/*ElemType*/chare)
e);
returnOK;
voidpostorder(btreet)//二叉树的后序遍历(非递归)
{//与教材p.131的中序遍历方法类似
pseqstackp;
p=(pseqstack)malloc(sizeof(seqstack));
top=0;
while(t||!
(p->
top==0))
if(t)
data[p->
top].node=t;
top].flag=0;
top)++;
t=t->
if(p->
top-1].flag==0)
{//若该结点右孩子没有被访问,则先访问其右孩子,并置标志为//1
top-1].flag=1;
t=p->
top-1].node->
//t=t->
{//否则直接访问该结点
printf("
ch);
(p->
top)--;
intmain()
t=creatbtree();
\n后序遍历:
postorder(t);
return0;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遍历 二叉 递归 算法