資料結構
網路
關係型資料庫管理系統
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 程式以非遞迴後序遍歷特定的二叉樹
如果以非遞迴後序遍歷二叉樹，則先遍歷左子樹，然後遍歷右子樹，最後遍歷根。這是一個用於以非遞迴方式進行後序樹遍歷的 C++ 程式。我們在此程式中使用堆疊來實現。
演算法
對於後序遍歷
Begin Declare postorder_traversal(struct node*t,struct tree**top) if(t==NULL) then print “Empty Tree”. Return. Print “Postorder Data Using Stack :”. Call push(t,top) function to insert values. Declare a pointer store against tree structure. Initialize struct tree*store=NULL. while(t!=NULL) store=*top; if(store->v==0) then if(t->r!=NULL) then (store->v)++ push(t->r,top) if(t->l!=NULL) then (store->v)++ push(t->l,top) if(store->v==0) then cout<d t=NULL pop(top) else cout<d t=NULL pop(top) if(*top!=NULL) then t=(*top)->link End
示例
#include<iostream>
#include<stdlib.h>
using namespace std;
struct node {
int d;
struct node *l,*r;
};
struct tree {
int v;
struct node*link;
struct tree*n;
};
struct node*create_node(int);
struct node*create_node(int value) {
struct node*new_node=(struct node*)malloc(sizeof(struct node));
if(new_node!=NULL) {
new_node->d=value;
new_node->l=new_node->r=NULL;
return new_node;
} else {
printf("\n Memory overflow.");
return NULL;
}
}
void push(struct node*,struct tree*);
void push(struct node*node,struct tree**top) {
struct tree*new_node=(struct tree*)malloc(sizeof(struct tree));
if(new_node!=NULL) {
new_node->link=node;
new_node->n=*top;
new_node->v=0;
*top=new_node;
} else {
cout<<"\n Memory overflow.";
return ;
}
}
void pop(struct tree**);
void pop(struct tree**top) {
if(*top!=NULL) {
struct tree*remove=*top;
*top=(*top)->n;
remove->link=NULL;
remove->n=NULL;
remove=NULL;
}
}
void postorder_traversal(struct node*,struct tree**);
void postorder_traversal(struct node*t,struct tree**top) {
if(t==NULL) {
cout<<"\n Empty Tree";
return;
}
cout<<"\n Postorder Data Using Stack :";
push(t,top);
struct tree*store=NULL;
while(t!=NULL) {
store=*top;
if(store->v==0) {
if(t->r!=NULL) {
(store->v)++;
push(t->r,top);
}
if(t->l!=NULL) {
(store->v)++;
push(t->l,top);
}
if(store->v==0) {
cout<<t->d;
t=NULL;
pop(top);
}
}
else {
cout<<t->d;
t=NULL;
pop(top);
}
if(*top!=NULL)
t=(*top)->link;
}
}
int main(){
struct node*root=NULL;
struct tree*top=NULL;
root = create_node(20);
root->l = create_node(10);
root->r = create_node(30);
root->r->r = create_node(7);
root->l->l = create_node(25);
root->l->r = create_node(35);
root->l->r->r = create_node(40);
root->l->l->r = create_node(26);
postorder_traversal(root,&top);
return 0;
}輸出
Postorder Data Using Stack :26 25 40 35 10 7 30 20
更新於：2019 年 7 月 30 日
483 次瀏覽
廣告