用AI赚第一桶💰低成本搭建一套AI赚钱工具,源码可二开。 广告
# 二叉树的遍历算法 ## 递归算法 ```C // 二叉树先序遍历、中序遍历、后序遍历的 void PreOrder(BTNode *b) { if(b!=NULL){ // 遍历的顺序取决于输出语句的位置 printf("%c", b->data); PreOrder(b->lchild); PreOrder(b->rchild); } } ``` ## 非递归算法 ### 二叉树先序遍历的非递归算法 ```C void PreOrder(BTNode *b) { BTNode *St[MaxSize], *p; int top = -1; if(b!=NULL){ top++; St[top] = b; while(top>-1){ p = St[top]; top--; printf("%c", p->data); if(p->rchild!=NULL){ top++; St[top] = p->rchild; } if(p->lchild!=NULL){ top++; St[top] = p->lchild; } } printf("\n"); } } ``` ### 二叉树中序遍历的非递归算法 ```C void InOrder(BTNode *b) { BTNode *St[MaxSize], *p; int top = -1; if(b!=NULL){ p = b; while(p!=NULL || top>-1){ while(p!=NULL){ top++; St[top] = p; p = p->lchild; } if(top>-1){ p = St[top]; top--; printf("%c", p->data); p = p->rchild; } } printf("\n"); } } ``` ### 二叉树后序遍历的非递归算法 ```C void PostOrder(BtNode *b){ BTNode *St[Maxsize], *p; int top = -1, flag; if(b!=NULL){ do{ while(b!=NULL){ top++; St[top] = b; b = b->lchild; } p = NULL; flag = 1;//访问栈顶元素 while(top>-1 && falg){ b = St[top]; //b 的右孩子已经访问过或不存在有孩子,输出之 if(b->rchild==p){ printf("%c", b->data); top--; p = b; }else{ flag = 0; b = b->rchild; } } }while(top>-1); printf("\n"); } } ``` ## 二叉树层次遍历 ```C void LevelOrder(BTNode *b) { BTNode *Qu[Maxsize], *p; int front = -1, rear = -1; if(b!=NULL){ rear++; Qu[rear] = b; while(rear!=front){ front = (front+1)%MaxSize; p = Qu[front]; printf("%c", p->data); if(p->lchild!=NULL){ rear = (rear+1)%MaxSize; Qu[rear] = p->lchild; } if(p->rchild!=NULL){ rear = (rear+1)%MaxSize; Qu[rear] = p->rchild; } } printf("\n"); } } ``` ## 二叉树构造 由先序和中序序列构造二叉树 ```C BTNode *CreateBT(char *pre, char *in, int n) { BTNode *b; char *p; int k; if(n<=0) return NULL; b=(BTNode *)malloc(sizeof(BTNode)); b->data=*pre; for(p=in;p<in+n;p++) if(*p==*pre)break; k=p-in; b->lchild=CreateBT(pre+1, in, k); b->rchild=CreateBT(pre+k+1,p+1,n-k-1); return b; } ``` 由后序和中序序列构造二叉树 ```C BTNode *CreateBT(char *post, char *in, int n) { BTNode *b; char r, *p; int k; if(n<=0)return NULL; r=*(post+n-1); b=(BTNode *)malloc(sizeof(BTNode)); b->data=r; for(p=in;p<in+n;p++) if(*p=r)break; k=p-in; b->lchild=CreateBT(post, in, k); b->rchild=CreateBT(post+k, p+1, n-k-1); return b; } ``` ####