溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例為大家分享了C語言非遞歸后序遍歷二叉樹的具體代碼，供大家參考，具體內容如下
法一：實現思路：一個棧 先按 根->右子樹->左子樹的順序訪問二叉樹。訪問時不輸出。另一個棧存入前一個棧只進棧的結點。
最后輸出后一個棧的結點數據。
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
char element;
struct TreeNode *left,*right;
}Tree,*BTree;
typedef struct StackNode{
BTree data;
struct StackNode *next;
}Stack,*PStack;
typedef struct{
PStack top;
}LinkStack,*PLinkStack;
//初始化空棧
PLinkStack Init_Stack(void){
PLinkStack S;
S=(PLinkStack)malloc(sizeof(LinkStack));
if(S){
S->top=NULL;
}
return S;
}
//壓棧
void Push_Stack(PLinkStack S,BTree T){
PStack p;
p=(PStack)malloc(sizeof(Stack));
p->data=T;
p->next=S->top;
S->top=p;
}
//判空
int empty_Stack(PLinkStack S){
if(S->top){
return 0;
}else{
return 1;
}
}
//出棧
PStack Pop_Stack(PLinkStack S){
PStack q;
if(empty_Stack(S)){
return S->top;
}else{
q=S->top;
S->top=S->top->next;
}
return q;
}
//銷毀棧
void DestroyStack(PLinkStack S){
PStack del;
while(S->top!=NULL){
del=S->top;
S->top=S->top->next;
free(del);
}
free(S);
}
BTree BuildTree(void){
char ch;
BTree node;
ch=getchar();
if(ch=='#'){
node=NULL;
}else{
node=(BTree)malloc(sizeof(Tree));
node->element=ch;
node->left=BuildTree();
node->right=BuildTree();
}
return node;
}
void NotRecursionPostOrder(BTree T){
PLinkStack S,CS;
S=Init_Stack();
CS=Init_Stack();
while(T || !empty_Stack(S)){
if(T){
Push_Stack(S,T);
Push_Stack(CS,T);
T=T->right;
}else{
T=Pop_Stack(S)->data;
T=T->left;
}
}
while(CS->top!=NULL){
printf("%c",CS->top->data->element);
CS->top=CS->top->next;
}
DestroyStack(CS);
}
int main(void){
BTree T;
T=BuildTree();
NotRecursionPostOrder(T);
return 0;
}
法二：實現思路。按先序遍歷訪問每一個結點。存入棧中，當為空時，就出立即棧（第一次出棧）。出棧后應該立即進棧，去訪問進棧結點的右結點，這樣可以保證先輸出左、右結點，再輸出根結點。二次進棧利用flag標記。
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
char element;
int flag;
struct TreeNode *left, *right;
}Tree, *BTree;
typedef struct StackNode {
BTree data;
struct StackNode *next;
}Stack, *PStack;
typedef struct {
PStack top;
}LinkStack, *PLinkStack;
//初始化空棧
PLinkStack Init_Stack(void) {
PLinkStack S = (PLinkStack)malloc(sizeof(LinkStack));
if (S) {
S->top = NULL;
}
return S;
}
//壓棧
void Push_Stack(PLinkStack S, BTree T) {
PStack p;
p = (PStack)malloc(sizeof(Stack));
p->data = T;
p->next = S->top;
S->top = p;
}
//判空
int empty_Stack(PLinkStack S) {
if (S->top) {
return 0;
}
else {
return 1;
}
}
//出棧
PStack Pop_Stack(PLinkStack S) {
PStack q = S->top;
S->top = S->top->next;
return q;
}
BTree BuildTree(void) {
BTree t;
char ch;
ch = getchar();
if (ch == '#') {
t = NULL;
}
else {
t = (BTree)malloc(sizeof(Tree));
t->element = ch;
t->left = BuildTree();
t->right = BuildTree();
}
return t;
}
void DestroyStack(PLinkStack S){
PStack p;
while(S->top){
p=S->top;
free(p);
S->top=S->top->next;
}
}
void NotRecursionPostOrder(BTree T) {
PLinkStack S;
S = Init_Stack();
while (T || !empty_Stack(S)) {
if (T) {
T->flag = 0;
Push_Stack(S, T);
T = T->left;
}
else {
T = Pop_Stack(S)->data;
if (T->flag == 0) {
T->flag = 1;
Push_Stack(S, T);
T = T->right;
}
else {
if (T->flag == 1) {
printf("%c", T->element);
T = NULL;
}
}
}
}
DestroyStack(S);//銷毀棧
}
int main(void) {
BTree T;
T = BuildTree();
NotRecursionPostOrder(T);
return 0;
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
