?? postorder.cpp
字號:
#include <stdio.h>//后續遍歷
typedef struct T{//定義二叉樹節點
struct T *l;
struct T *r;
int value;
}TREE;
TREE *I(TREE *head,int q)//插入節點
{
TREE *p, *parent;
bool i;
TREE *newnode=new TREE;
p=NULL;
newnode->value=q;
newnode->l=NULL;
newnode->r=NULL;
if(!head) return newnode;
p=head;
i=true;
while(p){
parent=p;
if(p->value>q)
{
p=p->l;
i=true;
}
else
{
p=p->r;
i=false;
}
}
if(i)
parent->l=newnode;
else
parent->r=newnode;
return head;
}
TREE *CREATE(TREE *head,int a[], int n)//建一棵二叉樹
{
int i;
for(i=1;i<=n;i++)
head=I(head,a[i]);
return head;
}
typedef struct NODE{//定義棧的元素
TREE *data;
NODE *next;
}NODE;
typedef struct STACK{//定義用來存放二叉樹節點指針的棧
NODE *top;
int length;
}STACK;
void INI(STACK &stack){//棧的初始化
stack.top=NULL;
stack.length=0;
}
bool Empty(STACK &stack){//判斷棧空函數
return(stack.length==0);
}
void PUSH(STACK &stack,TREE *p){//壓棧函數
NODE *newnode=new NODE;
newnode->data=p;
newnode->next=stack.top;
stack.top=newnode;
stack.length++;
}
TREE *POP(STACK &stack){//彈棧函數
TREE *value;
NODE *p;
if(Empty(stack)) return NULL;
value=stack.top->data;
p=stack.top->next;
delete stack.top;
stack.top=p;
stack.length--;
return value;
}
int b[20];
void X(TREE *head, int n,STACK &stack)//按照根節點->右節點->左節點的順序把各個節點值賦給棧b,經過彈棧輸出后即為后續遍歷
{
TREE *p=head;
int i=0;
while((p!=NULL)||!Empty(stack))
{
if(p!=NULL)
{
i++;
b[i]=p->value;
PUSH(stack,p);
p=p->r;
}
else{
p=POP(stack);
p=p->l;
}
}
}
void main()
{
int i,n;
TREE *head=NULL;
STACK stack;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&b[i]);
INI(stack);
head=CREATE(head,b,n);
X(head,n,stack);
for(i=n;i>0;i--)
printf("%d ",b[i]);
return;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -