数据结构实验

数据结构实验报告 实验六 二叉树遍历算法的设计与实现实验人:杨嘉雯 学号: Xb 时间：2012.11.27一、 实验目的1. 掌握二叉树的建立与存储2. 掌握二叉树的遍历方法二、 实验内容1. 编写程序实现根据用户输入二叉树的先序序列建立一棵二叉树，并实现对此二叉树的先序、中序、和后序遍历。用非递归方法实现中序遍历。（选做）三、 实验步骤： 1接收用户输入的先序序列建立以二叉链表为存储结构的二叉树。 2 对建立好的二叉树实现先序、中序、和后序遍历，将遍历后的序列 输出。四、 算法说明对于三种遍历的过程，要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了。至于非递归的三种遍历，中序最为简单，用一个栈就可以完成了，思路是边进栈边收索左孩子，直到左孩子为空的时候才开始进行出栈输出再收索右孩子的操作。采用非递归中序遍历算法，先逐步扫描二叉树的左子树，并压入堆栈，如果栈不为空，左子树为空，则弹出栈顶的一个元素并输出。然后再扫描右子树，然后再重复上面的步骤扫描该分支的左子树，直至整棵二叉树都扫描完成。此时输出的序列便是该二叉树的中序遍历序列。五、 测试结果中序线索化二叉树:六、 分析与探讨实验中经常会出现前后字符不一致的情况，主要原因是自己比较马虎，平时编程比较少，遇到比较长的程序，就容易出错。七、 附录：源代码#include #include typedef struct BiTNode /*定义二叉链表结点结构*/ char data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree;void CreateBiTree(BiTree *T)/* 输入二叉树的先序遍历序列，创建二叉链表 */ char ch; ch=getchar(); if (ch=#) *T=NULL; else *T=(BiTNode*)malloc(sizeof(BiTNode); (*T)-data=ch; /printf(当前根结点:%cn,(*T)-data); CreateBiTree(&(*T)-lchild); /* 建左子树 */ CreateBiTree(&(*T)-rchild); /* 建右子树 */ void PreOrderTraverse(BiTree T)/* 对二叉树进行先序遍历 */ if(T=NULL) return; printf(%c,T-data); PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); void InOrderTraverse(BiTree T)/* 对二叉树进行中序遍历 */if(T=NULL) return;InOrderTraverse(T-lchild); /中序遍历左子树 printf(%c,T-data); /显示结点数据，可以更改为其它对结点操作 InOrderTraverse(T-rchild); /最后中序遍历右子树 void PostOrderTraverse(BiTree T)/* 对二叉树进行后序遍历 */if(T=NULL) return;PostOrderTraverse(T-lchild); PostOrderTraverse(T-rchild); printf(%c,T-data); main() BiTree T=NULL; printf(请输入二叉树的结点:n); /scanf(%c,&ch); CreateBiTree(&T); printf(先序遍历:); PreOrderTraverse(T); printf(n中序遍历:); InOrderTraverse(T); printf(n后序遍历:); PostOrderTraverse(T);printf(n);中序线索化二叉树：#include#include#define NULL 0#define LEN_T sizeof(yangjiawen)#define LEN_S 50typedef struct yangjiawen char data; struct yangjiawen *lchild,*rchild; int lt,rt;yangjiawen,*yjwTree;void CreateTree(yjwTree *T) char c; c=getchar(); if (c=#)(*T)=NULL; else (*T)=(yjwTree)malloc(LEN_T); (*T)-lt=0; (*T)-rt=0; CreateTree(&(*T)-lchild); (*T)-data=c; CreateTree(&(*T)-rchild); yjwTree XianSuo(yjwTree *T) yjwTree t,pr,p,StackLEN_S; int top=0; t=(yjwTree)malloc(LEN_T); t-rchild=t; if(*T)=NULL)t-lchild=t; else t-lchild=(*T); p=(*T); pr=t; dowhile(p) Stacktop+=p;p=p-lchild; if(top0) p=Stack-top; printf(%2c,p-data); if(p-lchild=NULL)p-lt=1; p-lchild=pr; if(pr-rchild=NULL) pr-rt=1;pr-rchild=p; pr=p; p=p-rchild; while(p | top0);pr-rt=1;pr-rchild=t;t-rchild