赞
踩
二叉树的遍历是指按照一定规律对二叉树中的每个结点进行访问且仅访问一次。其中的访问可知计算二叉树中结点的数据信息,打印该结点的信息们也包括对结点进行任何其他操作。
输出二叉树的遍历结果
用户输入二叉树的广义表形式,程序输出二叉树和遍历结果。
设计创建和输出二叉树的函数以及三种遍历的函数,然后再主函数中调用这几个函数来实现操作。
建立二叉树并输出二叉树的代码,之前写过了
创建并输出二叉树
下面来看看遍历的操作
因为采用了递归方法,故三种方式都差不多,只用改变一下visit的顺序即可。
//中序遍历 void Inorder(BiTree *bt) { if(bt!=NULL) { Inorder(bt->lc); printf("%c ",bt->data); Inorder(bt->rc); } } //先序遍历 void Preorder(BiTree *bt) { if(bt!=NULL) { printf("%c ",bt->data); Preorder(bt->lc); Preorder(bt->rc); } } //后序遍历 void Postorder(BiTree *bt) { if(bt!=NULL) { Postorder(bt->lc); Postorder(bt->rc); printf("%c ",bt->data); } }
主函数部分,把程序功能打印出来,并对用户做一个引导。
int main()//(A(B(D,),C(,E))) (A(B(D,E),C(F,G))) ((((A),B)),(((),D),(E,F)))这个不是树 //来个波兰表达式的例子 (-(+(a,*(b,c)),/(d,e))) { BiTree *bt; char *gyb,str[MAXSIZE]; int j=1; printf("-------------------------------------------------------"); printf("\n 程序功能"); printf("\n 1.将按照输入的二叉广义表表示字符串 "); printf("\n · 生成对应的二叉树链式结构。"); printf("\n 2.输出二叉树的凹入法表示形式。"); printf("\n · G--根 L--左孩子 R--右孩子"); printf("\n 3.树状打印二叉树。"); printf("\n · 逆时针旋转90度显示二叉树"); printf("\n 4.打印出先序、中序和后续遍历的结果。"); printf("\n * 输入示例:(A(B(D,),C(,E)))或(-(+(a,*(b,c)),/(d,e)))"); printf("\n-------------------------------------------------------\n"); printf("请输入二叉树的广义表形式:\n"); gyb=str; scanf("%s",str); bt =CreatBiTreepre(gyb); printf("二叉树建立成功!\n"); printf("此二叉树的凹入法表示为:\n"); OutBiTree(bt); printf("树状打印二叉树:\n"); PrintTree(bt,1); printf("先序遍历序列为:\n"); Preorder(bt); printf("\n中序遍历序列为:\n"); Inorder(bt); printf("\n后序遍历序列为:\n"); Postorder(bt); return 0; }
设二叉树有n个结点,对每个结点都要进行一次入栈和出栈的操作,即入栈和出栈各执行n次,对结点的访问也是n次。这些二叉树递归遍历算法的时间复杂度为 O ( n ) O(n) O(n)。
实验结果很不错,所有操作都能正常执行,用波兰表达式做例子得到了正确的输出。
这是上面分析的例子的程序给出的输出。
下面这个例子大家也可以看看。
有了前面工作的铺垫,递归遍历就很简单了,多多重复,百炼成钢!
最后附上完整的代码
#include<stdio.h> #include<stdlib.h> #define MAXSIZE 255 //定义二叉树的链式存储结构,有三个域:数据域,左孩子域,右孩子域 typedef struct BiNode { char data; struct BiNode *lc; struct BiNode *rc; }BiTree; //以广义表的形式创建二叉树 BiTree *CreatBiTreepre(char *str) { BiTree *bt,*stack[MAXSIZE],*p=NULL; int top=-1,k,j=0; char ch; bt=NULL; ch=str[j]; while(ch!='\0') { switch(ch) { case '(': { top++; stack[top]=p; k=1; break; } case ')': { top--; break; } case ',': { k=2; break; } default: { p=(BiTree *)malloc(sizeof(BiTree)); p->data=ch; p->lc=p->rc=NULL; if(bt==NULL) { bt=p; } else { switch(k) { case 1: { stack[top]->lc=p; break; } case 2: { stack[top]->rc=p; break; } } } } } j++; ch=str[j]; } return bt;//链式存储只用知道一个,后面顺藤摸瓜就都知道了 } //采用凹入法输出二叉树 void OutBiTree(BiTree *bt) { BiTree *stack[MAXSIZE],*p; int feature[MAXSIZE][2],top,n,i,width=4; char type; if(bt!=NULL) { top=1; stack[top]=bt; feature[top][0]=width; feature[top][1]=2; while(top>0) { p=stack[top]; n=feature[top][0]; switch(feature[top][1]) { case 0: { type='l'; break; } case 1: { type='R'; break; } case 2: { type='G'; break; } } for(i=1;i<=n;i++) printf(" "); printf("%c(%c)\n",p->data,type); top--; if(p->lc!=NULL) { top++; stack[top]=p->lc; feature[top][0]=n+width; feature[top][1]=0; } if(p->rc!=NULL) { top++; stack[top]=p->rc; feature[top][0]=n+width; feature[top][1]=1; } } } } void PrintTree(BiTree *bt,int nLayer) { if(bt==NULL) return ; PrintTree(bt->rc,nLayer+1); for(int i=0;i<nLayer;i++) printf(" "); printf("%c\n",bt->data); PrintTree(bt->lc,nLayer+1); } //中序遍历 void Inorder(BiTree *bt) { if(bt!=NULL) { Inorder(bt->lc); printf("%c ",bt->data); Inorder(bt->rc); } } //先序遍历 void Preorder(BiTree *bt) { if(bt!=NULL) { printf("%c ",bt->data); Preorder(bt->lc); Preorder(bt->rc); } } //后序遍历 void Postorder(BiTree *bt) { if(bt!=NULL) { Postorder(bt->lc); Postorder(bt->rc); printf("%c ",bt->data); } } int main()//(A(B(D,),C(,E))) (A(B(D,E),C(F,G))) ((((A),B)),(((),D),(E,F)))这个不是树 //来个波兰表达式的例子 (-(+(a,*(b,c)),/(d,e))) { BiTree *bt; char *gyb,str[MAXSIZE]; int j=1; printf("-------------------------------------------------------"); printf("\n 程序功能"); printf("\n 1.将按照输入的二叉广义表表示字符串 "); printf("\n · 生成对应的二叉树链式结构。"); printf("\n 2.输出二叉树的凹入法表示形式。"); printf("\n · G--根 L--左孩子 R--右孩子"); printf("\n 3.树状打印二叉树。"); printf("\n · 逆时针旋转90度显示二叉树"); printf("\n 4.打印出先序、中序和后续遍历的结果。"); printf("\n * 输入示例:(A(B(D,),C(,E)))或(-(+(a,*(b,c)),/(d,e)))"); printf("\n-------------------------------------------------------\n"); printf("请输入二叉树的广义表形式:\n"); gyb=str; scanf("%s",str); bt =CreatBiTreepre(gyb); printf("二叉树建立成功!\n"); printf("此二叉树的凹入法表示为:\n"); OutBiTree(bt); printf("树状打印二叉树:\n"); PrintTree(bt,1); printf("先序遍历序列为:\n"); Preorder(bt); printf("\n中序遍历序列为:\n"); Inorder(bt); printf("\n后序遍历序列为:\n"); Postorder(bt); return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。