数据结构实验5页

1、数据结构实验报告 实验六 二叉树遍历算法的设计与实现实验人:杨嘉雯 学号: Xb10680230 时间：2012.11.27一、 实验目的1. 掌握二叉树的建立与存储2. 掌握二叉树的遍历方法二、 实验内容1. 编写程序实现根据用户输入二叉树的先序序列建立一棵二叉树，并实现对此二叉树的先序、中序、和后序遍历。用非递归方法实现中序遍历。（选做）三、 实验步骤： 1接收用户输入的先序序列建立以二叉链表为存储结构的二叉树。 2 对建立好的二叉树实现先序、中序、和后序遍历，将遍历后的序列 输出。四、 算法说明对于三种遍历的过程，要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了。至于非递归的三

2、种遍历，中序最为简单，用一个栈就可以完成了，思路是边进栈边收索左孩子，直到左孩子为空的时候才开始进行出栈输出再收索右孩子的操作。采用非递归中序遍历算法，先逐步扫描二叉树的左子树，并压入堆栈，如果栈不为空，左子树为空，则弹出栈顶的一个元素并输出。然后再扫描右子树，然后再重复上面的步骤扫描该分支的左子树，直至整棵二叉树都扫描完成。此时输出的序列便是该二叉树的中序遍历序列。五、 测试结果中序线索化二叉树:六、 分析与探讨实验中经常会出现前后字符不一致的情况，主要原因是自己比较马虎，平时编程比较少，遇到比较长的程序，就容易出错。七、 附录：源代码#include <stdlib.h>#in

3、clude <stdio.h>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("当前

4、根结点:%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 InOrde

5、rTraverse(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); PostOrderT

6、raverse(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后序遍历:"); PostOrder

7、Traverse(T);printf("n");中序线索化二叉树：#include<stdio.h>#include<malloc.h>#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(

8、); 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

9、)t->lchild=t; else t->lchild=(*T); p=(*T); pr=t; dowhile(p) Stacktop+=p;p=p->lchild; if(top>0) 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 | top>0);pr->rt=1;pr->rchild=t;t->rchild=pr;printf("n&quo