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

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

2、ine NULL 0typedef struct btnodechar 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->rchi

3、ld=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;二叉树的遍历上面虽然已经生成二叉树，但实际上用户生成的二叉树是抽象，用户并不太 确信已经生成的二叉树是否是自己想要的， 于是，可以编制输出程序进一步验证 这个已经存在的二叉树的正确性。二叉树的遍历就是对二叉树的每一个结点访问一次且仅访问一次。 我们通过 二叉树的序遍历的非递归算

4、法来验证其正确性。 二叉树非递归遍历是用显示栈来 存储二叉树的结点指针。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、后序

5、遍历 先将根结点的所有左结点并入栈，出栈一个结点，将该结点的右结点入栈， 再将该结点的左结点入栈， 当一个结点的左右子树均访问该结点， 如此，直到栈 空为止。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”,