数据结构实验.doc

实验六二叉树遍历算法的设计与实现实验人:杨嘉雯学号:Xb10680230时间：2012.11.27实验目的掌握二叉树的建立与存储掌握二叉树的遍历方法实验内容编写程序实现根据用户输入二叉树的先序序列建立一棵二叉树并实现对此二叉树的先序、中序、和后序遍历。用非递归方法实现中序遍历。（选做）实验步骤：1．接收用户输入的先序序列建立以二叉链表为存储结构的二叉树。2．对建立好的二叉树实现先序、中序、和后序遍历将遍历后的序列输出。算法说明对于三种遍历的过程要是用递归写的就根据书上所给出的遍历步骤做稍微的调整就好了。至于非递归的三种遍历中序最为简单用一个栈就可以完成了思路是边进栈边收索左孩子直到左孩子为空的时候才开始进行出栈输出再收索右孩子的操作。采用非递归中序遍历算法先逐步扫描二叉树的左子树并压入堆栈如果栈不为空左子树为空则弹出栈顶的一个元素并输出。然后再扫描右子树然后再重复上面的步骤扫描该分支的左子树直至整棵二叉树都扫描完成。此时输出的序列便是该二叉树的中序遍历序列。测试结果中序线索化二叉树:分析与探讨实验中经常会出现前后字符不一致的情况主要原因是自己比较马虎平时编程比较少遇到比较长的程序就容易出错。附录：源代码#include<stdlib.h>#include<stdio.h>typedefstructBiTNode/*定义二叉链表结点结构*/{chardata;structBiTNode*lchild*rchild;}BiTNode*BiTree;voidCreateBiTree(BiTree*T)/*输入二叉树的先序遍历序列创建二叉链表*/{charch;ch=getchar();if(ch=='#')*T=NULL;else{*T=(BiTNode*)malloc(sizeof(BiTNode));(*T)->data=ch;//printf("当前根结点:%c\n"(*T)->data);CreateBiTree(&(*T)->lchild);/*建左子树*/CreateBiTree(&(*T)->rchild);/*建右子树*/}}voidPreOrderTraverse(BiTreeT)/*对二叉树进行先序遍历*/{if(T==NULL)return;printf("%c"T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}voidInOrderTraverse(BiTreeT)/*对二叉树进行中序遍历*/{if(T==NULL)return;InOrderTraverse(T->lchild);//中序遍历左子树printf("%c"T->data);//显示结点数据可以更改为其它对结点操作InOrderTraverse(T->rchild);//最后中序遍历右子树}voidPostOrderTraverse(BiTreeT)/*对二叉树进行后序遍历*/{if(T==NULL)return;PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c"T->data);}main(){BiTreeT=NULL;printf("请输入二叉树的结点:\n");//scanf("%c"&ch);CreateBiTree(&T);printf("先序遍历:");PreOrderTraverse(T);printf("\n中序遍历:");InOrderTraverse(T);printf("\n后序遍历:");PostOrderTraverse(T);printf("\n");}中序线索化二叉树：#include<stdio.h>#include<malloc.h>#defineNULL0#defineLEN_Tsizeof(yangjiawen)#defineLEN_S50typedefstructyangjiawen{chardata;structyangjiawen*lchild*rchild;intltrt;}yangjiawen*yjwTree;voidC