数据结构学习之二叉树递归和非递归遍历算法

秒速五厘米 2021-11-10 16:10 236阅读 0赞

# 数据结构学习之二叉树递归和非递归遍历算法 #

## 0x1 前言 ##

虽然自己很失败,但是自己还是做出来,虽然是在赶作业,但是我对自己能认真去写也感到很开心了,这里留下个坑点,关于这个后序非递归我还不是特别理解。

## 0x2 题目要求 ##

用非递归遍历算法遍历二叉树

## 0x3 code ##

#include <cstdio> #include <cstdlib> #include <algorithm> #include <queue> #define MaxSize 100+7 using namespace std; typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; }BTNode; //二叉树基本操作 void CreateBTree(BTNode *&b, ElemType str); //创建二叉树 void DestroyBTree(BTNode *&b); //销毁二叉树 BTNode *FindNode(BTNode *b, ElemType x); //返回值为x的指针 int BTHight(BTNode *b); //求高度 BTNode *LchildNode(BTNode *b); // BTNode *RchildNode(BTNode *b); // void DispTree(BTNode *b); //输出二叉树 //递归遍历操作 void PreOrder(BTNode *); void InOrder(BTNode *); void PostOrder(BTNode *); // 非递归遍历操作 void PreOrder1(BTNode *p); void InOrder1(BTNode *p); void PostOrder1(BTNode *p); void LevelOrder(BTNode *); typedef struct { int top; BTNode *dt[MaxSize]; }SqStack; void CreateBTree(BTNode *&b, char *str) { BTNode *St[MaxSize],*p; //建立一个顺序栈 int top=-1; b=NULL; int j=0,k; char ch=str[j]; while(ch!='\0') { switch(ch) { case '(':St[++top]=p,k=1;break; case ')':top--;break; case ',':k=2;break; default: p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch; p->lchild=NULL; p->rchild=NULL; if(b==NULL) b=p; else { if(k==1) St[top]->lchild=p; else if(k==2) St[top]->rchild=p; } } j++; ch=str[j]; } } void DispTree(BTNode *b) { if(b!=NULL) { printf("%c",b->data); if(b->lchild!=NULL || b->rchild!=NULL) { printf("("); DispTree(b->lchild); if(b->rchild!=NULL) printf(","); DispTree(b->rchild); printf(")"); } } } /** error void BTHight(BTNode *b,int n) { if(b==NULL) return n; int h=max(BTHight(r->lchild,n+1),BTHight(b->rchild,n+1)); } */ // 做一步就+1 最后就是高度了。 int BTHight(BTNode *b) { if(b==NULL) return(0); else { int lhight=BTHight(b->lchild); int rhight=BTHight(b->rchild); return max(lhight,rhight)+1; //回溯过程 } } void DestroyTree(BTNode *b) { /** 先遍历才能销毁 if(b!=NULL) { free(b); return; }else { DestroyTree(b->lchild); DestroyTree(b->rchild); } **/ if(b!=NULL) { DestroyTree(b->lchild); DestroyTree(b->rchild); free(b); } } BTNode * FindNode(BTNode *b,ElemType x) { BTNode *p; if(b==NULL) { return NULL; } else if(b->data==x) return b; p=FindNode(b->lchild,x); if(p!=NULL) return p; else return FindNode(b->rchild,x); } void PreOrder(BTNode *p) { if(p!=NULL) { printf("%c",p->data); PreOrder(p->lchild); PreOrder(p->rchild); } } void InOrder(BTNode *p) { if(p!=NULL) { InOrder(p->lchild); printf("%c",p->data); InOrder(p->rchild); } } void PostOrder(BTNode *p) { if(p!=NULL) { PostOrder(p->lchild); PostOrder(p->rchild); printf("%c",p->data); } } void GradOrder(BTNode *p,char *a,int i) { if(p->lchild!=NULL) { GradOrder(p->lchild,a,2*i); }else { GradOrder(p->rchild,a,2*i+1); } *(a+i)=p->data; } void PreOrder1(BTNode *b) { SqStack st; BTNode *p=b; //初始化栈 st.top=-1; // printf("%d",st.top); if(p!=NULL) { st.dt[++st.top]=p; //printf("%c",st.dt[st.top]->data); while(st.top!=-1) { p=st.dt[st.top]; printf("%c",st.dt[st.top--]->data); //printf("%d",st.top); //右孩子 if(p->rchild!=NULL) st.dt[++st.top]=p->rchild; // 左孩子 if(p->lchild!=NULL) st.dt[++st.top]=p->lchild; } } printf("\n"); //销毁栈 free(&st); } void InOrder1(BTNode *b) { //printf("%c",b->lchild->lchild->lchild); SqStack st; st.top=-1; BTNode *p=b; if(p!=NULL) { while(st.top!=-1 || p!=NULL) { while(p!=NULL) { st.dt[++st.top]=p; p=p->lchild; } if(st.top!=-1) { p = st.dt[st.top--]; printf("%c",p->data); p=p->rchild; } } } printf("\n"); free(&st); } // 到时候去理解 void PostOrder1(BTNode *b) { SqStack st; st.top=-1; bool flag; BTNode *p,*r; p=b; do { while(p!=NULL) { st.dt[++st.top]=p; p=p->lchild; } r=NULL; flag=true; while(st.top!=-1 && flag) { p=st.dt[st.top]; if(p->rchild==r) { printf("%c",p->data); r = st.dt[st.top--]; }else { p=p->rchild; flag=false; } } } while(st.top!=-1); printf("\n"); free(&st); } void LevelOrder(BTNode *b) { BTNode *p; queue<BTNode *> qu; qu.push(b); //printf("%c",b->data); while(!qu.empty()) { p=qu.front(); qu.pop(); printf("%c",p->data); if(p->lchild !=NULL) qu.push(p->lchild); if(p->rchild !=NULL) qu.push(p->rchild); }; } int main() { char *str="A(B(D(,G)),C(E,F))"; BTNode *T,*p; CreateBTree(T,str); DispTree(T); int n=BTHight(T); printf("\n"); printf("tree height:%d\n",n); p=FindNode(T,'A'); printf("%c\n",p->data); // 递归遍历二叉树 PreOrder(T); printf("\n"); InOrder(T); printf("\n"); PostOrder(T); printf("\n"); // 非递归遍历二叉树 printf("非递归遍历二叉树: \n"); PreOrder1(T); InOrder1(T); PostOrder1(T); LevelOrder(T); DestroyTree(T); }

## 0x4 结果 ##

![image-20190522180848350][]

转载于:https://www.cnblogs.com/xq17dog/p/10907664.html

[image-20190522180848350]: /images/20211109/e0c0c5a10a0048a7b4c1cbfa89527fe4.png