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

6、二叉树的生成建立一个二叉树是指在内存中建立二叉树的存储结构，这里讨论建立一个二叉链表的方式生成一个二叉树。要建立一个二叉链表，需按照完全二叉树的层次顺序，依次输入结点信息建立二叉链表。对于一般的二叉树，必须添加一些虚结点，使其成为完全二叉树。我用表示虚结点，#表示输入结束标志。同时设置一个队列，队列是一个指针类型的数组，保存已输入的结点的地址。根据对为指针奇偶数的判断，来决定把字符放到左结点还是有结点中，这样就能生成想要的二叉树。#define maxsize 100#include “stdio.h”#include “malloc.h”#define NULL 0typedef struct btnode char data; struct btonde lchild,rchild;Btree;Btree*Qmaxsize;Btree*creatree()char ch;int front,rear;Btree *t,*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-rchild=NULL;rear+;Qrear=s;if(rear=1)T=s;elseif(s&Qfront)If(rear%2=0)Qfront-lchild=s;ElseQfront-rchild=s;if(rear%2=1)front+;ch=getchar();returnT;二叉树的遍历上面虽然已经生成二叉树，但实际上用户生成的二叉树是抽象，用户并不太确信已经生成的二叉树是否是自己想要的，于是，可以编制输出程序进一步验证这个已经存在的二叉树的正确性。二叉树的遍历就是对二叉树的每一个结点访问一次且仅访问一次。我们通过二叉树的序遍历的非递归算法来验证其正确性。二叉树非递归遍历是用显示栈来存储二叉树的结点指针。1、 先序遍历 使用一个栈，首先将根结点入栈，开始循环；从栈中退出当前结点，先访问它，然后将其右结点入栈，再将其左结点入栈，如此直到栈空为止。Void porder(Btree*T)Btree*stackmaxsize,*p;int top=-1;if(T!=NULL)top+;stacktop=T;while(top-1)p=stacktop;top-;prinft(“%c”,p-data);if(p-right!=NULL)top+;stacktop=p-left;2、 后序遍历先将根结点的所有左结点并入栈，出栈一个结点，将该结点的右结点入栈，再将该结点的左结点入栈，当一个结点的左右子树均访问该结点，如此，直到栈空为止。void pmorder(Btree*T)Btree*stackmaxsize,*p;int top=-1; dowhile(T)top+;stacktop=T;T=T-left;p=NULL;flag=1;while(top!=-1 &flag)T=stacktop;ift-right=pprintf(“%c”,T-data);top+;p=T;elseT=T-right;flag=0;while(top!=-1);中序遍历先将根结点的所有左结点并入栈,出栈一个结点,访问该结点,将该结点的右结点入栈,再将该结点的左结点入栈,当一个结点的左子树均访问后再访问该结点,最后访问右结点.如此,直到栈空为止。Void psorder(btree*T)Btree*stackmaxsize,*p;int top=-1;dowhile(T)top+;stacktop=T;T=T-left;T=stacktop;printf(“%c”,T-data);top-;if(t-right)T=T-right;top+;stacktop=T;T=T-leftiwhile(top!=-1);