首页 > 代码库 > 二叉树的前中后以及层次遍历
二叉树的前中后以及层次遍历
#include "stdio.h" #include "malloc.h" #define datatype char typedef struct bT { datatypedata; struct bT *lt,*rt; }* bitree,BiNode; void preExCreate(bitree bt); /*递归实现*/ void FprePost(bitree bt) { if(bt) { printf("%c",bt->data); FprePost(bt->lt); FprePost(bt->rt); } } void FinPost(bitree bt) { if(bt) { FinPost(bt->lt); printf("%c",bt->data); FinPost(bt->rt); } } void FlaPost(bitree bt) { if(bt) { FlaPost(bt->lt); FlaPost(bt->rt); printf("%c",bt->data); } } /* 非递归实现 */ void prePost(bitree bt) { BiNode* stack[100]; int top=0; BiNode* p = bt; int q=0; while(top>0 || p != NULL) { while(p!=NULL) { if(p->lt ==NULL && p->rt==NULL)q++; printf("%c",p->data); stack[top++] = p; p = p->lt; } //左子树全部入栈 p = stack[--top]; p = p->rt; } } void inPost(bitree bt) { BiNode* stack[100]; int top=0; BiNode* p = bt; int q = 0; while(top>0 || p != NULL) { while(p!=NULL) { stack[top++] = p; p = p->lt; } //左子树全部入栈 p = stack[--top]; printf("%c",p->data); p = p->rt; } } void laPost(bitree bt) { BiNode* stack[100]; BiNode* Visted= NULL; int top=0; BiNode* p = bt; while(top>0 || p != NULL) { while(p!=NULL)// while 不是if { stack[top++] = p; p = p->lt; } //左子树全部入栈 p = stack[top-1];//取栈顶 if(p->rt == Visted || p->rt == NULL)//右子树不空或是被访问过 { printf("%c",p->data); Visted = p;//标记p被访问 --top;//栈顶出 p = NULL;//继续 右 } else { p = p->rt; } } } void Excreate (bitree* bt) { char c = getchar(); if( c == ‘.‘) (*bt) = NULL; else { (*bt) = (bitree)malloc(sizeof(BiNode)); (*bt)->data = c; Excreate(&(*bt)->lt); Excreate(&(*bt)->rt); } } void PrintTree(bitree bt,int nLayer) /* 按竖向树状打印的二叉树*/ { if(bt == NULL) return; PrintTree(bt->rt,nLayer+1); for(int i=0;i<nLayer;i++) printf(" "); printf("%c\n",bt->data); PrintTree(bt->lt,nLayer+1); } int DepthOfTree(bitree bt) { int Ld,Rd,max; if(bt != NULL) { Ld = DepthOfTree( bt->lt ); Rd = DepthOfTree( bt->rt ); max = Ld>Rd? Ld:Rd; return max+1; } else return 0; } void CCPost(bitree bt)//层次遍历 { bitree que[100]; int front=-1,rear=0; que[rear] = bt; while( front != rear) { front++;//出队 printf("%c",que[front]->data); if(que[front]->lt != NULL) { rear++; que[rear] = que[front]->lt ; //入队 } if(que[front]->rt != NULL) { rear++; que[rear] = que[front]->rt; } } } void main() { bitree bt,pre; Excreate(&bt); pre = bt; //前序遍历 printf("前序遍历:\n"); FprePost(bt); //中序 printf("\n中序遍历:\n"); FinPost(bt); printf("\n后序遍历:\n"); //后序 FlaPost(bt); printf("\n层次遍历:\n"); //层次 CCPost(bt); //横向打印二叉树 printf("\n横向打印二叉树:\n"); PrintTree(bt,DepthOfTree(bt)); //计算二叉树深度 printf("\n二叉树深度%d\n",DepthOfTree(bt)); }
/* http://black4yl.blog.51cto.com */
本文出自 “black4yL” 博客,请务必保留此出处http://black4yl.blog.51cto.com/4222963/1580284
二叉树的前中后以及层次遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。