二叉树的建立与遍历

1、实践考核题第二题设计报告书学生姓名XXX学生学号09XXX所在地区XXX提交日期（年/月）2014/6实践题目实现二叉树的建立与遍历需求分析（1）以二叉链表作为存储结构，定义二叉树类型 Bitree 定义二叉链表的存储结构，可以更好地对二叉表的操作，在二叉链表中，data域用于存储二叉树节点中的数据信息；lchild是指向左孩子的指针（左指针）。类似的，rchild是指向右孩子的指针（右指针）。此外，每个二叉链表还必须有一个指向根节点的指针，该指针称为根指针。与链表头指针类似，根指针具有标识二叉链表的作用，对二叉链表的访问只能从根指针开始。若果某个节点的右孩子或者左孩子不存在时，则相应指针数据

2、域为空（#）。由此可知叶节点的左右指针必为空（#）。（2）实现二叉树的以下运算 建立 void CreateBiTree(BiTree *T) 输入二叉树的结点元素，建立二叉链表 建立void CreateBiTree(BiTree *T)函数可以往二叉链表中输入数据和向左右指针的指向是否为#，只有建立了二叉链表才能通过调用先序遍历、中序遍历和后序遍历的函数遍历出二叉树中的数据。 选择一种遍历方式（先序、中序、后序）遍历这棵二叉树 通过选择遍历方式，遍历同一颗二叉树，遍历的次序是不同的，遍历的方法也是不一样的，通过不同的遍历方式的得到二叉树的顺序是不一样，但是都是为了得到二叉树最后的排序。通过

3、先序遍历，先访问的是根节点，然后是左子树，最后是右子树。中序遍历，先遍历左子树，在访问根节点，最后遍历右子树。后序遍历，先遍历左子树，在遍历右子树，左后访问根节点。通过不同的排序方式可以确定一棵唯一的二叉树。概要设计（1） 建立二叉链表： void CreateBiTree(BiTree *T) 首先，定义一个结构体，存储每个节点的信息，并给这个结构体定义别名为Bittree；这个结构体中的数据元素有，保存数据的类型，还有指向左右孩子的指针它的类型和结构体的类型一样。（2） 实现二叉树的以下运算 选择一种遍历方式（先序、中序、后序）遍历这棵二叉树 先序遍历：void PreOrder(BiTr

4、ee T)若被遍历的二叉树为空，执行空操作；否则，依次执行下列操作： 访问根节点； 先序遍历左子树； 先序遍历右子树。中序遍历：void InOrder(BiTree T若被遍历的二叉树为空，执行空操作；否则，依次执行下列操作：中序遍历左子树；访问根节点；中序遍历右子树。后序遍历：void PostOrder(BiTree T)若被遍历的二叉树为空，执行空操作；否则，依次执行下列操作：后序遍历左子树；后序遍历右子树；访问根节点。 上面给出的先序遍历、中序遍历和后序遍历的定义都是递归的，因而根据定义很容易得到相应遍历的递归算法。详细设计#include#include#includetypede

5、f char TElemType;typedef struct SBiTNode TElemType data; struct SBiTNode *lchild,*rchild;BiTNode,*BiTree;/采用左序遍历创建二叉树，用到的是递归算法，参数指针T有点晦涩难懂。void CreateBiTree(BiTree *T) TElemType ch; scanf(%c,&ch); if(ch=#) *T=NULL; else *T=(BiTree)malloc( sizeof(BiTNode) ); if(!*T) exit(-1); (*T)-data=ch; CreateBiTr

6、ee(&(*T)-lchild); CreateBiTree(&(*T)-rchild); /输出函数void Visit(BiTree T)if(T-data != #)printf(%c ,T-data);/先序遍历void PreOrder(BiTree T)if(T != NULL)/访问根节点Visit(T);/访问左子结点PreOrder(T-lchild);/访问右子结点PreOrder(T-rchild);/中序遍历void InOrder(BiTree T) /判断是否为空 if(T!=NULL) /中序访问左子树 InOrder(T-lchild); /访问根节点 Visi

7、t(T); /中序访问右子树 InOrder(T-rchild); /后序遍历void PostOrder(BiTree T) /判断是否为空 if(T!=NULL) /后序访问左子树 PostOrder(T-lchild); /后序访问右子树 PostOrder(T-rchild); /访问根节点 Visit(T); /主函数 int main() BiTree T; printf(清数据数据（#代表空数据位，结束前不要使用回车键）：n); CreateBiTree(&T); /创建二叉树 if(T!=NULL) printf(前序遍历n); PreOrder(T); /先序遍历 print

8、f(n); printf(中序遍历n); InOrder(T); /中序遍历 printf(n); printf(后序遍历n); PostOrder(T); /后序遍历 printf(n); elseprintf(二叉树为空！);getch(); return 0;调试分析输入数据6253检查程序执行是否正确：输入数据为空时，检查程序的执行：设计总结在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求（求路径）；但采用后序遍历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结点存储到一个顺序栈中，然后再输出即可。因此，我们可以非递归地后序遍历二叉树T，