数据结构二叉树的生成和遍历

《数据结构二叉树的生成和遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、6、二叉树的生成建立一个二叉树是指在内存中建立二叉树的存储结构，这里讨论建立一个二叉链表的方式生成一个二叉树。要建立一个二叉链表，需按照完全二叉树的层次顺序，依次输入结点信息建立二叉链表。对于一般的二叉树，必须添加一些虚结点，使其成为完全二叉树。我用@表示虚结点，#表示输入结束标志。同时设置一个队列，队列是一个指针类型的数组，保存已输入的结点的地址。根据对为指针奇偶数的判断，来决定把字符放到左结点还是有结点中，这样就能生成想要的二叉树。#definemaxsize100#include“stdio.h”#include“malloc

2、.h”#defineNULL0typedefstructbtnode{chardata;structbtondelchild,rchild;}Btree;BtreeQ[maxsize];Btreecreatree(){charch;intfront,rear;Btreet,s;t=NULL;front=1;rear=0;ch=getchar();}while(ch!=’#’){s=NULL;if(ch!=’@’){s=(btree)mlloc(sizcof(btree));s->data=ch;s->lchild=NULL;s->r

3、child=NULL;rear++;Q[rear]=s;if(rear==1)T=s;else{if(s&&Q[front])If(rear%2==0)Q[front]->lchild=s;ElseQ[front]->rchild=s;if(rear%2==1)front++;}ch=getchar();}returnT;}二叉树的遍历上面虽然已经生成二叉树，但实际上用户生成的二叉树是抽象，用户并不太确信已经生成的二叉树是否是自己想要的，于是，可以编制输出程序进一步验证这个已经存在的二叉树的正确性。二叉树的遍历就是对二叉树的每一个结

4、点访问一次且仅访问一次。我们通过二叉树的序遍历的非递归算法来验证其正确性。二叉树非递归遍历是用显示栈来存储二叉树的结点指针。1、先序遍历使用一个栈，首先将根结点入栈，开始循环；从栈中退出当前结点，先访问它，然后将其右结点入栈，再将其左结点入栈，如此直到栈空为止。Voidporder(BtreeT){Btreestack[maxsize],p;inttop=-1;if(T!=NULL){top++;stack[top]=T;while(top>-1){p=stack[top];top--;prinft(“%c”,p->data);if

5、(p->right!=NULL){top++;stack[top]=p->left;}}}2、后序遍历先将根结点的所有左结点并入栈，出栈一个结点，将该结点的右结点入栈，再将该结点的左结点入栈，当一个结点的左右子树均访问该结点，如此，直到栈空为止。voidpmorder(BtreeT){Btreestack[maxsize],p;inttop=-1;do{while(T){top++;stack[top]=T;T=T->left;}p=NULL;flag=1;while(top!=-1&&flag){T=stack[top];if{t

6、->right==p}{printf(“%c”,T->data);top++;p=T;}else{T=T->right;flag=0;}]}while(top!=-1);}中序遍历先将根结点的所有左结点并入栈,出栈一个结点,访问该结点,将该结点的右结点入栈,再将该结点的左结点入栈,当一个结点的左子树均访问后再访问该结点,最后访问右结点.如此,直到栈空为止。Voidpsorder(btreeT){Btreestack[maxsize],p;inttop=-1;do{while(T){top++;stack[top]=T;T=T->le

7、ft;}T=stack[top];printf(“%c”,T->data);top--;if(t->right){T=T->right;top++;stack[top]=T;T=T->lefti}}while(top!=-1);}