下载文档原格式
第三节二叉树的遍历方法和递归实现什么是二叉树的遍历？二叉树的遍历：是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
为什么要遍历二叉树？遍历是二叉树中经常要用到的一种操作。
因为在实际应用问题中，常常需要按一定的顺序对二叉树中的每个结点逐个进行访问。
如何遍历二叉树？由二叉树的定义可知，一棵二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。
因此，只要依次遍历这三部分，就可以遍历整个二叉树。
遍历二叉树主要有4种方式：先序遍历中序遍历后序遍历层次遍历约定：用D表示访问根结点，用L表示遍历左子树，用R表示遍历右子树。
先序遍历：用DLR表示，即先访问根结点→再遍历根结点的左子树→最后遍历根结点的右子树。
中序遍历：用LDR表示，即先遍历根结点的左子树→再访问根结点→最后遍历根结点的右子树。
后序遍历：用LRD表示，即先遍历根结点的左子树→再遍历根结点的右子树→最后访问根结点。
层次遍历：从二叉树的第一层(根结点)开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。
注意：如何区分先序遍历、中序遍历和后序遍历？关键看一点：根结点什么时候被访问。
如果最先访问根结点，就是先序遍历；如果在中间访问根结点，就是中序遍历；如果最后访问根结点，就是后序遍历。
以图1所示的二叉树为例，下面将通过上述4种遍历方式分别来遍历这棵二叉树。
1. 先序遍历(DLR)先序遍历的递归过程为：若二叉树为空，遍历结束；否则：(1) 先访问根结点；(2) 再遍历根结点的左子树；(3) 最后遍历根结点的右子树。
对图1所示的二叉树，首先访问根结点A，然后移动到A结点的左子树。
A结点的左子树的根结点是B，于是访问B结点。
移动到B的左子树，B结点的左子树的根结点是D，于是访问D结点。
由于D结点没有左子树，因此移动D结点的右子树。
D结点的右子树的根结点是G，于是访问G结点。
现在就完成了对根结点和左子树的遍历，以类似的方法遍历根结点的右子树。
实验报告题目：二叉树的遍历及应用院系：数学系专业：数学与应用数学学号： **********姓名：***一、实验名称：二叉树的遍历及应用二、实验日期：2012年11月14日三、实验要求：编程实现二叉树的建立并对其进行遍历四、实验目的：1、掌握二叉树链式存储结构的类型定义及实现；2、掌握二叉树链式存储结构的各类基本运算方法；3、掌握二叉树各个重要性质在解决实际问题中的应用；4、掌握二叉树的分析方法、解决方法，从而提高实际编程能力及程序调试能力。
五、实验内容1、创建二叉树；2、用递归方法实现二叉树的各种遍历。
六、程序代码#include<stdio.h>#include<malloc.h>#define TRUE 1#define FALSE 0#define Stack_Size 50typedef struct Node{char data;struct Node *LChild;struct Node *RChild;}BiTNode,*BiTree;typedef BiTree StackElementType;typedef struct{StackElementType elem[Stack_Size];int top;}SeqStack;//初始化void InitStack(SeqStack *S){S->top=-1;}//进栈int Push(SeqStack *S,StackElementType x) { if(S->top==Stack_Size-1) return(FALSE); S->top++;S->elem[S->top]=x;return(TRUE);}//出栈int Pop(SeqStack *S,StackElementType *x) {if(S->top==-1)return(FALSE);else{*x=S->elem[S->top];S->top--;return(TRUE);}}//先序遍历void PreOrder(BiTree root){if(root!=NULL){printf("%c",root->data);PreOrder(root->LChild);PreOrder(root->RChild);}}//中序遍历void InOrder(BiTree root) { if(root!=NULL){ InOrder(root->LChild); printf("%c",root->data); InOrder(root->RChild);}}//后序遍历void PostOrder(BiTree root) {if(root!=NULL){PostOrder(root->LChild); PostOrder(root->RChild); printf("%c",root->data);}}//创建二叉链表void CreateBiTree(BiTree *bt){char ch;ch=getchar();if(ch=='.') *bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode)); (*bt)->data=ch;CreateBiTree(&((*bt)->LChild)); CreateBiTree(&((*bt)->RChild));}}//后序遍历球二叉树高度int PostTreeDepth(BiTree bt){int hl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt->LChild);hr=PostTreeDepth(bt->RChild);max=hl>hr?hl:hr;return(max+1);}else return(0);}//横向打印二叉树void PrintTree(BiTree bt,int nLayer) {int i;if(bt==NULL) return;PrintTree(bt->RChild,nLayer+1);for( i=0;i<nLayer;i++)printf(" ");printf("%c\n",bt->data);PrintTree(bt->LChild,nLayer+1);}void main(){BiTree root;printf("请输入序列:\n"); CreateBiTree(&root);printf("输出结果为:\n");printf("先序遍历结果:\n"); PreOrder(root);printf("\n中序遍历结果:\n"); InOrder(root);printf("\n后序遍历结果:\n"); PostOrder(root);printf("\n二叉树的深度:\n");printf("%d",PostTreeDepth(root)); printf("\n横向打印二叉树结果:\n"); PrintTree(root,5);}七、成果展示。
二叉树的遍历实验报告二叉树的遍历实验报告引言：二叉树是一种常见的数据结构，它由节点和连接节点的边组成。
在实际应用中，我们经常需要对二叉树进行遍历，以便对其中的节点进行访问和操作。
本次实验旨在探索二叉树的遍历算法，并通过实验验证其正确性和效率。
一、二叉树的定义和基本操作二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。
根据节点的访问顺序，二叉树的遍历可以分为前序遍历、中序遍历和后序遍历三种方式。
前序遍历是指先访问根节点，然后按照左子树、右子树的顺序递归地进行遍历；中序遍历是指先按照左子树、根节点、右子树的顺序递归地进行遍历；后序遍历是指先按照左子树、右子树、根节点的顺序递归地进行遍历。
二、实验设计和方法为了验证二叉树的遍历算法的正确性和效率，我们设计了以下实验方案：1. 构建二叉树：我们首先构建一个具有一定规模的二叉树，以模拟实际应用中的情况。
为了方便起见，我们选择随机生成一棵二叉树，并确保其结构合理。
2. 实现遍历算法：我们根据前文所述的遍历方式，实现了相应的遍历算法。
在实现过程中，我们考虑到了递归和迭代两种方式，并分别进行了实验比较。
3. 遍历实验：我们使用不同规模的二叉树进行遍历实验，并记录遍历的结果和所花费的时间。
通过对比不同规模下不同遍历方式的结果和时间，我们可以评估遍历算法的效率和准确性。
三、实验结果和分析在实验中，我们构建了一棵具有1000个节点的二叉树，并分别使用前序、中序和后序遍历算法进行遍历。
通过实验结果的比较，我们得出以下结论：1. 遍历结果的正确性：无论是前序、中序还是后序遍历，我们都能够正确地访问到二叉树中的每个节点。
这表明我们所实现的遍历算法是正确的。
2. 遍历算法的效率：在1000个节点的二叉树中，我们发现中序遍历算法的执行时间最短，后序遍历算法的执行时间最长，前序遍历算法的执行时间居中。
这是因为中序遍历算法在访问节点时可以尽可能地减少递归次数，而后序遍历算法需要递归到最深层才能返回。
实习报告——“二叉树的遍历（递归）”演示程序（一）、程序的功能和特点主要实现的功能：1.建立空树；2.按照前序遍历方式建立二叉树；3.获取二叉树的根节点；4.以前、中、后序三种方式进行遍历输出二叉树；5.取出当前从m开始n个字符组成的子串；6.获取二叉树的结点数；7.获取树的高度；（二）、程序的算法设计“二叉树遍历（递归）”算法：1.【逻辑结构与存储结构设计】逻辑结构：非线性结构——树状结构存储结构：链式存储2.【基本操作设计】键盘读入参数设定参照值递归生成左右子树封闭叶子节点返回二叉树3.【算法设计】ADCBE F leftChild root rightChild得到串s的第is个字符是判断是否是参照值封闭叶子结点否递归生成左右子树若实参是空二叉树，得到返回的子二叉树返回二叉树P4.【高级语言代码】//按前序遍历方式建立二叉树int is=0;//串s的下标public BinTreeNode preOrderCreate(BinTreeNode p,String s){ char item=s.charAt(is++);//得到串s的第is个字符if(item!=invalue){//读入的不是参照值p=new BinTreeNode(item);//递归生成左子树p.leftChild=preOrderCreate(p.leftChild,s);//递归生成右子树p.rightChild=preOrderCreate(p.rightChild,s);//实参是空二叉树，得到返回的子二叉树}else//读入的是参照值p=null;//封闭叶子结点return p;//返回二叉树p}//按前序遍历方式输出二叉树public void preOrderTraverse(BinTreeNode p){if(p!=null){//输出根结点数据域System.out.print(" "+p.GetData());//递归输出p的左子树preOrderTraverse(p.leftChild);//递归输出p的右子树preOrderTraverse(p.rightChild);}}//按中序遍历方式输出二叉树public void inOrderTraverse (BinTreeNode p) { if ( p != null ) {//递归输出p的左子树inOrderTraverse ( p.leftChild );System.out.print(" "+p.GetData());//递归输出p的右子树inOrderTraverse (p.rightChild );}}//按后序遍历方式输出二叉树public void postOrderTraverse (BinTreeNode p) { if ( p != null ) {//递归输出p的左子树postOrderTraverse ( p.leftChild );//递归输出p的右子树postOrderTraverse (p.rightChild );//输出根结点数据域System.out.print(" "+p.GetData());}}//结点数：左右子树的结点数之和+1public int Count(BinTreeNode t){if(t==null)return 0;//空树else{return Count(t.leftChild)+Count(t.rightChild)+1;}}//树的高度：左右子树的最大高度+1public int Height(BinTreeNode t){int a,b;if(t==null) return 0;else{a=Height(t.leftChild);b=Height(t.rightChild);return (a>b?a:b)+1;}}（三）、程序中类的设计“BinaryTree”类：1.【逻辑结构与存储结构】2.【主要成员变量说明】private BinTreeNode root;//根节点int is=0;//串s的下标private char invalue;//参照值3.【主要成员方法说明】//以root为根建立二叉树public void CreateBinTree()//按前序遍历方式建立二叉树Public BinTreeNodepreOrderCreate(BinTreeNode p,String s) //按前序遍历方式输出二叉树public void preOrderTraverse(BinTreeNode p)//按中序遍历方式输出二叉树public void inOrderTraverse (BinTreeNode p)//按后序遍历方式输出二叉树public void postOrderTraverse (BinTreeNode p)//结点数：左右子树的结点数之和+1public int Count(BinTreeNode t)//树的高度：左右子树的最大高度+1public int Height(BinTreeNode t)4.【高级语言代码】public class BinaryTree {private BinTreeNode root;//根节点/*在建立二叉树之前，给定一个结点数据域中不可能出现的数，* 用来标记二叉树的一条分支到此封闭*/private char invalue;//构造函数：建立一棵空树，并设定参照值public BinaryTree(char v){invalue=v;root=null;}//以root为根建立二叉树public void CreateBinTree(){String s=new String();System.out.println("按照前序遍历输入字符串:");try{//键盘接受一个字符串BufferedReaderbr=new BufferedReader(new InputStreamReader(System.in));s=br.readLine();}catch(IOException e){}/*用s字符串生成二叉树，实参为空二叉树，* 根root得到返回的二叉树归根结点* 输入的字符串是含参照值的前序的前序遍历序列，否则崩溃*/root=preOrderCreate(root,s);}//按前序遍历方式建立二叉树int is=0;//串s的下标public BinTreeNode preOrderCreate(BinTreeNode p,String s){ char item=s.charAt(is++);//得到串s的第is个字符if(item!=invalue){//读入的不是参照值p=new BinTreeNode(item);//递归生成左子树p.leftChild=preOrderCreate(p.leftChild,s);//递归生成右子树p.rightChild=preOrderCreate(p.rightChild,s);//实参是空二叉树，得到返回的子二叉树}else//读入的是参照值p=null;//封闭叶子结点return p;//返回二叉树p}/** 得到二叉树的根，根root被定义为私有，只有本类的成员能访问*/public BinTreeNode GetRoot(){return root;}//按前序遍历方式输出二叉树public void preOrderTraverse(BinTreeNode p){if(p!=null){//输出根结点数据域System.out.print(" "+p.GetData());//递归输出p的左子树preOrderTraverse(p.leftChild);//递归输出p的右子树preOrderTraverse(p.rightChild);}}//按中序遍历方式输出二叉树public void inOrderTraverse (BinTreeNode p) {if ( p != null ) {//递归输出p的左子树inOrderTraverse ( p.leftChild );System.out.print(" "+p.GetData());//递归输出p的右子树inOrderTraverse (p.rightChild );}}//按后序遍历方式输出二叉树public void postOrderTraverse (BinTreeNode p) { if ( p != null ) {//递归输出p的左子树postOrderTraverse ( p.leftChild );//递归输出p的右子树postOrderTraverse (p.rightChild );//输出根结点数据域System.out.print(" "+p.GetData());}}//结点数：左右子树的结点数之和+1public int Count(BinTreeNode t){if(t==null)return 0;//空树else{return Count(t.leftChild)+Count(t.rightChild)+1;}}//树的高度：左右子树的最大高度+1public int Height(BinTreeNode t){int a,b;if(t==null) return 0;else{a=Height(t.leftChild);b=Height(t.rightChild);return (a>b?a:b)+1;}}public static void main(String[] args) {BinaryTree s=new BinaryTree('^');//定义一棵二叉树s.CreateBinTree();//前序遍历s.preOrderTraverse(s.GetRoot());System.out.println();//中序遍历s.inOrderTraverse(s.GetRoot());System.out.println();//后序遍历s.postOrderTraverse(s.GetRoot());System.out.println();//求结点总数System.out.println(s.Count(s.GetRoot()));//求二叉树高度System.out.println(s.Height(s.GetRoot()));}}（四）、程序的输入输出和运行结果截屏。
总结二叉树的遍历及应用二叉树是一种常用的数据结构，它由节点组成，每个节点最多有两个孩子节点，分别称为左孩子和右孩子。
二叉树的遍历是指按照一定的规则，依次访问二叉树中的每个节点。
常见的二叉树遍历方式主要有前序遍历、中序遍历和后序遍历。
下面将介绍这三种遍历方式及其应用。
1. 前序遍历（Preorder Traversal）：先访问根节点，然后递归遍历左子树，最后递归遍历右子树。
前序遍历的顺序是“中-左-右”。
前序遍历的应用场景有：（1）复制二叉树：可以通过前序遍历将原始二叉树的节点复制到一个新的二叉树中。
（2）输出二叉树结构：通过前序遍历可以将二叉树的结构以一种清晰明了的方式输出。
2. 中序遍历（Inorder Traversal）：先递归遍历左子树，然后访问根节点，最后递归遍历右子树。
中序遍历的顺序是“左-中-右”。
中序遍历的应用场景有：（1）二叉搜索树（BST）的中序遍历结果是一个有序序列，可以利用这个特点进行查找、插入和删除等操作。
（2）输出二叉搜索树的所有节点：通过中序遍历可以将二叉搜索树的节点按照从小到大的顺序输出。
3. 后序遍历（Postorder Traversal）：先递归遍历左子树，然后递归遍历右子树，最后访问根节点。
后序遍历的顺序是“左-右-中”。
后序遍历的应用场景有：（1）计算二叉树的高度或深度：通过后序遍历可以方便地计算二叉树的高度或深度，从而优化树的深度相关的操作。
（2）释放二叉树的内存：通过后序遍历可以按照从底部向上的顺序释放二叉树的节点内存。
除了上述三种基本的二叉树遍历方式外，还有一种特殊的二叉树遍历方式，它是层序遍历（Level Order Traversal）。
层序遍历是从上到下逐层访问二叉树的节点，同一层的节点按照从左到右的顺序访问。
层序遍历可以使用队列来实现。
层序遍历的应用场景有：（1）打印二叉树的层次结构：通过层序遍历可以将二叉树按照层次结构打印出来，便于观察和分析。
二叉树的遍历算法实验报告二叉树的遍历算法实验报告引言：二叉树是计算机科学中常用的数据结构之一，它是由节点组成的层次结构，每个节点最多有两个子节点。
在实际应用中，对二叉树进行遍历是一项重要的操作，可以帮助我们理解树的结构和节点之间的关系。
本文将介绍二叉树的三种遍历算法：前序遍历、中序遍历和后序遍历，并通过实验验证其正确性和效率。
一、前序遍历前序遍历是指先访问根节点，然后按照先左后右的顺序遍历左右子树。
具体的实现可以通过递归或者使用栈来实现。
我们以递归方式实现前序遍历算法，并进行实验验证。
实验步骤：1. 创建一个二叉树，并手动构造一些节点和它们之间的关系。
2. 实现前序遍历算法的递归函数，函数的输入为根节点。
3. 在递归函数中，首先访问当前节点，然后递归调用函数遍历左子树，最后递归调用函数遍历右子树。
4. 调用前序遍历函数，输出遍历结果。
实验结果：经过实验，我们得到了正确的前序遍历结果。
这证明了前序遍历算法的正确性。
二、中序遍历中序遍历是指按照先左后根再右的顺序遍历二叉树。
同样，我们可以使用递归或者栈来实现中序遍历算法。
在本实验中，我们选择使用递归方式来实现。
实验步骤：1. 继续使用前面创建的二叉树。
2. 实现中序遍历算法的递归函数，函数的输入为根节点。
3. 在递归函数中，首先递归调用函数遍历左子树，然后访问当前节点，最后递归调用函数遍历右子树。
4. 调用中序遍历函数，输出遍历结果。
实验结果：通过实验，我们得到了正确的中序遍历结果。
这证明了中序遍历算法的正确性。
三、后序遍历后序遍历是指按照先左后右再根的顺序遍历二叉树。
同样，我们可以使用递归或者栈来实现后序遍历算法。
在本实验中，我们选择使用递归方式来实现。
实验步骤：1. 继续使用前面创建的二叉树。
2. 实现后序遍历算法的递归函数，函数的输入为根节点。
3. 在递归函数中，首先递归调用函数遍历左子树，然后递归调用函数遍历右子树，最后访问当前节点。
4. 调用后序遍历函数，输出遍历结果。
⼆叉树遍历的递归实现详解（先序、中序、后序和层次遍历）由⼆叉树的定义可知，⼀棵⼆叉树由根结点、左⼦树和右⼦树三部分组成。
因此，只要遍历了这三个部分，就可以实现遍历整个⼆叉树。
若以D、L、R分别表⽰遍历根结点、左⼦树、右⼦树，则⼆叉树的递归遍历可以有⼀下四种⽅式：先序遍历（DLR）先序遍历的递归过程为（1）访问根结点（2）先序遍历根结点的左⼦树（3）先序遍历根结点的右⼦树举例：代码：void PreOrder(BiTree bt){if(bt ==NULL)return; //递归的结束条件----某结点为空时printf("%d",bt->data); //这⾥⽤printf data表⽰访问结点的数据域PreOrder(bt->lchild); //递归遍历左孩⼦PreOrder(bt->rclild); //递归遍历右孩⼦}中序遍历（LDR）（1）中序遍历根结点的左⼦树（2）访问根结点（3）中序遍历根结点的右⼦树举例：代码：void InOrder(BiTree bt){if(bt ==NULL)return; //递归的结束条件----某结点为空时InOrder(bt->lchild); //递归遍历左孩⼦printf("%d",bt->data); //这⾥⽤printf data表⽰访问结点的数据域InOrder(bt->rclild); //递归遍历右孩⼦}后序遍历（LRD）（1）后序遍历⼆叉树的左⼦树（2）后序遍历⼆叉树的右⼦树（3）访问根结点。
举例：代码：void PostOrder(BiTree bt){if(bt ==NULL)return; //递归的结束条件----某结点为空时PostOrder(bt->lchild); //递归遍历左孩⼦PostOrder(bt->rclild); //递归遍历右孩⼦printf("%d",bt->data); //这⾥⽤printf data表⽰访问结点的数据域}层次遍历（1）根结点⼊队列（2）根结点出队列，根结点的左⼦树、右⼦树相继⼊队列（3）根结点的左⼦树结点出队列，左⼦树结点的左⼦树、右⼦树相继⼊队列（4）.......举例：代码：//层次遍历⼆叉树void LevelOrder(BiTree T){BiTree Queue[MAX],b; //⽤⼀维数组表⽰队列，front和rear表⽰队⾸和队尾的指针int front,rear;front=rear=0;if(T)//若树为空{Queue[rear++]=T; //根节点⼊队列while(front!=rear) //当队列⾮空{b=Queue[front++]; //队⾸元素出队列，并访问这个节点printf("%2c",b->data);if(b->lchild!=NULL) Queue[rear++]=b->lchild ; //若左⼦树⾮空，则⼊队列if(b->rchild!=NULL) Queue[rear++]=b->rchild ; //若右⼦树⾮空，则⼊队列}}}最终代码：#include<stdio.h>#include<stdlib.h>#define MAX 20typedef char TElemType;typedef int Status;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild; //左右孩⼦的指针} BiTNode,*BiTree;//先序创建⼆叉树void CreateBiTree(BiTree *T){char ch;ch=getchar();if(ch=='#')(*T)=NULL; //#代表空指针else{(*T)=(BiTree)malloc(sizeof(BiTNode)); //申请节点(*T)->data=ch; //⽣成跟节点CreateBiTree(&(*T)->lchild);CreateBiTree(&(*T)->rchild);}}//先序输出⼆叉树void PreOrder(BiTree T){if(T){printf("%2c",T->data); //访问根节点，此处为输出根节点的数据值PreOrder(T->lchild); //先序遍历左⼦树PreOrder(T->rchild); //先序遍历右⼦树}}//中序输出⼆叉树void InOrder(BiTree T){if(T){InOrder(T->lchild);printf("%2c",T->data);InOrder(T->rchild);}}//后序输出⼆叉树void PostOrder(BiTree T){if(T){PostOrder(T->lchild);PostOrder(T->rchild);printf("%2c",T->data);}}//层次遍历⼆叉树void LevelOrder(BiTree T){BiTree Queue[MAX],b; //⽤⼀维数组表⽰队列，front和rear表⽰队⾸和队尾的指针 int front,rear;front=rear=0;if(T)//若树为空{Queue[rear++]=T; //根节点⼊队列while(front!=rear) //当队列⾮空{b=Queue[front++]; //队⾸元素出队列，并访问这个节点printf("%2c",b->data);if(b->lchild!=NULL) Queue[rear++]=b->lchild ; //若左⼦树⾮空，则⼊队列if(b->rchild!=NULL) Queue[rear++]=b->rchild ; //若右⼦树⾮空，则⼊队列}}}//求树的深度int depth(BiTree T){int dep1,dep2;if(T==NULL) return 0;else{dep1=depth(T->lchild);dep2=depth(T->rchild);return dep1>dep2?dep1+1:dep2+1;}}int main(){BiTree T=NULL;printf("\n 创建⼀棵⼆叉树： \n");CreateBiTree(&T); //创建⼆叉树printf("\n先序遍历的结果为：\n");PreOrder(T); //先序遍历printf("\n中序遍历的结果为：\n");InOrder(T); //中序遍历printf("\n 后序遍历的结果为： \n");PostOrder(T);printf("\n 层次遍历的结果为: \n");LevelOrder(T); //层次遍历printf("\n 树的深度为:%d\n",depth(T));}结果⽰例：⼤家喜欢的话可以点个赞，有错误的地⽅请务必在评论区指出哟。
1．实验题目二叉树的建立与遍历[问题描述]建立一棵二叉树，并对其进行遍历（先序、中序、后序），打印输出遍历结果。
2．需求分析（1）输入的形式和输入值的范围：以字符形式按先序遍历输入（2）输出的形式：依次按递归先序、中序、后序遍历，非递归先序、中序、后序遍历结果输出(3) 程序所能达到的功能：从键盘接受输入（先序）进行遍历（先序、中序、后序），将遍历结果打印输。
(4) 测试数据：ABCффDEфGффFффф（其中ф表示空格字符）则输出结果为先序：ABCDEGF中序：CBEGDFA后序：CGBFDBA3．概要设计（1）struct btnode{char data; 数据struct btnode *Lchild;左子数指针struct btnode *Rchild; 右子数指针};struct btnode *createbt(struct btnode *bt )初始条件：空二叉树存在操作结果：先序建立二叉树void preOrder(struct btnode *bt)初始条件：二叉树存在递归先序遍历二叉树void preOrder1(struct btnode *bt)初始条件：二叉树存在操作结果：非递归先序遍历void midOrder(struct btnode *bt)初始条件：二叉树存在操作结果：递归中序遍历void midOrder1(struct btnode *bt)初始条件：二叉树存在操作结果：非递归中序遍历void postOrder(struct btnode *bt)初始条件：二叉树存在操作结果：递归后序遍历void postOrder1 (struct btnode *bt)初始条件：二叉树存在操作结果：非递归后序遍历void main() 主函数（2）void main() 主函数{*createbtpreOrderpreOrder1midOrdermidOrder1postOrderpostOrder1}4．详细设计struct btnode{char data;struct btnode *Lchild;struct btnode *Rchild;};struct btnode *createbt(struct btnode *bt ){ 输入结点数据c检查存储空间将c赋给结点参数p递归建立左子树递归建立右子树}void preOrder(struct btnode *bt){判断树是否为空输出根结点数data递归遍历左子树递归遍历右子树}void preOrder1(struct btnode *bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){输出根结点数data将根结点压栈遍历左子树}提取栈顶元素值栈顶元素出栈访问右子树}void midOrder(struct btnode *bt){判断树是否为空递归遍历左子树输出根结点数data递归遍历右子树}void midOrder1(struct btnode *bt){定义栈，结点参数pWhile(栈或p是否为空){While(p!=null){将根结点压栈遍历左子树}提取栈顶元素值输出根结点数data栈顶元素出栈访问右子树}void postOrder(struct btnode *bt){判断树是否为空递归遍历左子树递归遍历右子树输出根结点数data}void postOrder1 (struct btnode *bt){定义栈，结点参数p,prebt入栈While(栈或p是否为空){提取栈顶元素值if判断p是否为空或是pre的根结点输出根结点数data栈顶元素出栈栈顶元素p赋给pre记录else if右结点非空将右结点压栈if左结点将左结点压栈}}void main(){struct btnode *root=NULL;root=createbt(root);preOrder(root); midOrder(root); postOrder(root);preOrder1(root); midOrder1(root)；postOrder1(root);}5.调试分析（1）先序建立二叉树时，虽用到递归建左右子树，但没有把他们赋值给根节点的左右指针，造成二叉树脱节。
实验四二叉树的操作班级：计算机1002班姓名：唐自鸿学号：201003010207 完成日期：2010.6.14 题目：对于给定的一二叉树，实现各种约定的遍历。
一、实验目的：（1）掌握二叉树的定义和存储表示，学会建立一棵特定二叉树的方法；（2）掌握二叉树的遍历算法（先序、中序、后序遍历算法）的思想，并学会遍历算法的递归实现和非递归实现。
二、实验内容：构造二叉树，再实现二叉树的先序、中序、后序遍历，最后统计二叉树的深度。
三、实验步骤：(一) 需求分析1. 二叉树的建立首先要建立一个二叉链表的结构体，包含根节点和左右子树。
因为树的每一个左右子树又是一颗二叉树，所以用递归的方法来建立其左右子树。
二叉树的遍历是一种把二叉树的每一个节点访问并输出的过程，遍历时根结点与左右孩子的输出顺序构成了不同的遍历方法，这个过程需要按照不同的遍历的方法，先输出根结点还是先输出左右孩子，可以用选择语句来实现。
2．程序的执行命令为：1）构造结点类型，然后创建二叉树。
2）根据提示，从键盘输入各个结点。
3）通过选择一种方式（先序、中序或者后序）遍历。
4）输出结果，结束。
(二)概要设计1.二叉树的二叉链表结点存储类型定义typedef struct Node{DataType data;struct Node *LChild;struct Node *RChild;}BitNode,*BitTree;2.建立如下图所示二叉树：void CreatBiTree(BitTree *bt)用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点。
3.本程序包含四个模块1) 主程序模块：2)先序遍历模块3)中序遍历模块4)后序遍历模块4.模块调用关系：主程序模块（三）详细设计1.建立二叉树存储类型//==========构造二叉树=======void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是当前树根置为空，否则申请一个新节点//{char ch;ch=getchar();if(ch=='.')*bt=NULL;else{*bt=(BitTree)malloc(sizeof(BitNode));//申请一段关于该节点类型的存储空间(*bt)->data=ch; //生成根结点CreatBiTree(&((*bt)->LChild)); //构造左子树CreatBiTree(&((*bt)->RChild)); //构造右子树}}2. 编程实现以上二叉树的前序、中序和后序遍历操作，输出遍历序列1）先序遍历二叉树的递归算法如下：void PreOrder(BitTree root){if (root!=NULL){Visit(root ->data);PreOrder(root ->LChild); //递归调用核心PreOrder(root ->RChild);}}2）中序遍历二叉树的递归算法如下：void InOrder(BitTree root){if (root!=NULL){InOrder(root ->LChild);Visit(root ->data);InOrder(root ->RChild);}}3）后序遍历二叉树的递归算法如下：void PostOrder(BitTree root){if(root!=NULL){PostOrder(root ->LChild);PostOrder(root ->RChild);Visit(root ->data);}}4）计算二叉树的深度算法如下：int PostTreeDepth(BitTree bt) //求二叉树的深度{int hl,hr,max;if(bt!=NULL){hl=PostTreeDepth(bt->LChild); //求左子树的深度hr=PostTreeDepth(bt->RChild); //求右子树的深度max=hl>hr?hl:hr; //得到左、右子树深度较大者return(max+1); //返回树的深度}else return(0); //如果是空树，则返回0}四、调试分析及测试结果1. 进入演示程序后的显示主界面：请输入二叉树中的元素；先序、中序和后序遍历分别输出结果。
实验六二叉树的递归遍历及其应用一、实验目的1、深入了解二叉树递归的逻辑结构特征及其基本操作。
2、了解二叉树各种存储结构的特点及其适用范围，熟练掌握二叉树的二叉链表结构的定义及其递归遍历算法、按层次遍历算法的c语言实现，能深入了解递归算法的执行过程。
3、熟练掌握二叉树递归遍历算法的应用。
一、实验内容和要求2、设计并验证如下算法：与“12.7.4参考源程序”类似，按中序序列输入建立两棵二叉树的二叉链表结构，求双分支结点数，判断两棵树是否相等。
3、设计并验证如下算法：按层次遍历二叉树，打印结点所在的层次，并求该二叉树的宽度。
二、实验过程及结果（第一题）一、需求分析1、从键盘输入二叉树的序列，但由于建树是从根结点往下建立的，故只能输入先序序列，则按照中序建树完成二叉树的创建。
2、从键盘输入一段正确的序列后，按回车键自动生成二叉树，若该序列不能生成一颗二叉树，则程序无法继续进行，只能退出。
3、程序能实现的功能包括：①初始化二叉树；②创建一棵完整二叉树；③先中后序遍历二叉树；④求二叉树双分支结点数；⑤比较两棵二叉树是否相等；二、概要设计1、二叉树的抽象数据类型定义：ADT BinaryTree{数据对象D：D是具有相同特征的数据元素的集合。
数据关系R：若D=空，则R=空，称BinaryTree为空二叉树；若D！=空，则R={H}，H是如下二元关系：（1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；（2）若D-{root}!=Φ，则存在D-{root}={D1,Dr}，且D1∩Dr=Φ；（3）若D1！=Φ，则D1中存在唯一元素x1，<root,x1>∈H,且存在D1上的关系H1包含于H；若Dr!=Φ,则Dr中存在唯一的元素，<root,xr>∈H，且存在Dr上的的关系Hr包含于H；H={<root,,x1>，<root,xr>，H1，Hr}；（Dr,{Hr}）（4）（D1,{H1}）是一棵符合本定义的二叉树，称为根的左子树，是一棵符合本定义的二叉树，称为根的右子树。
基本操作:InitBiTree(&BT)操作结果：构造空二叉树CreateBiTree(&BT)操作结果：建立二叉树PreOrder(BT)初始条件：二叉树BT已存在操作结果：先序遍历InOrder(BT)初始条件：二叉树BT已存在操作结果：中序遍历PostOrder(BT)初始条件：二叉树BT已存在操作结果：后序遍历Do_BranNumber(BT)初始条件：二叉树BT已存在操作结果：求BT的双分支结点数Same_CompareTree(BT_a,BT1_b)初始条件：二叉树BT_a、BT_b已存在操作结果：比较两棵树是否相等}ADT BinaryTree；⒊本程序模块结构⑴主函数模块void main(){初始化两颗二叉树；创建二叉树BT_a，返回根结点BT_a；getchar();创建二叉树BT_b，返回根结点BT_b；getchar();先、中、后序遍历BT_a和BT_b；if(两棵树相等)printf("相同");elseprintf("不同");输出BT_a和BT_b的双分支结点数；｝三、详细设计1、基本数据类型操作⑴二叉链表的存储结构typedef char TElemType;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild; //左右孩子指针}BiTNode,*BiTree;四、调试分析1、创建两棵二叉树程序便不能继续运行，只能创建一棵树，加了getchar()后便能操作，原因可能是换行符造成的。
2、进行两棵树的比较时不仅要保证各结点值相等，还要确保结构相同，若结构不同，两棵树则不等，故采用递归算法。
3、求双分支结点数采用递归算法，一定要保证结束条件，此结束条件应为结点为空时返回0。
五、用户说明及测试结果1、两棵二叉树不相等2、两颗二叉树相等七、附录（源代码及部分注释）#include "stdio.h"#include "stdlib.h"#include "conio.h"#include "string.h"#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define OVERFLOW -1#define INFEASIBLE -2#define Max_Tree_SIZE 20//最大结点数typedef int Status;typedef char TElemType;typedef struct BiTNode{TElemType data;struct BiTNode *lchild,*rchild; //左右孩子指针}BiTNode,*BiTree;Status InitBiTree(BiTree *BT); //构造空二叉树Status CreateBiTree(BiTree *BT); //建立二叉树Status PreOrder(BiTree BT); //先序遍历Status InOrder(BiTree BT); //中序遍历Status PostOrder(BiTree BT); //后序遍历int Do_BranNumber(BiTree BT); //求双分支结点数Status Same_CompareTree(BiTree BT,BiTree BT1); //比较两棵树是否相等void main(){int flag=1,select;BiTree BT_a,BT_b;InitBiTree(&BT_a);InitBiTree(&BT_b);printf("To Create Binary Tree, Please Input PreOrder with '#' :\n");//输入二叉树的先序序列，用#代表空结点printf("Create The First Of Binary Tree(a): ");CreateBiTree(&BT_a); //创建二叉树，返回根结点BT_agetchar();printf("Create The Second Of Binary Tree(b): ");CreateBiTree(&BT_b); //创建二叉树，返回根结点BT_bgetchar();printf("The First Of Binary Tree(a) is:\n");printf("PreOrder Traversal: ");PreOrder(BT_a); //先序遍历printf("\nInOrder Traversal: ");InOrder(BT_a); //中序遍历printf("\nPostOrder Traversal: ");PostOrder(BT_a); //后序遍历printf("\n\nThe Second Of Binary Tree(b) is:\n");printf("PreOrder Traversal: ");PreOrder(BT_b); //先序遍历printf("\nInOrder Traversal: ");InOrder(BT_b); //中序遍历printf("\nPostOrder Traversal: ");PostOrder(BT_b); //后序遍历if(Same_CompareTree(BT_a,BT_b))printf("\n\nThe Binary Tree a and B is Same!\n");elseprintf("\n\nThe Binary Tree a and B is Different!\n");printf("\nThe Binary Tree a's Number of Double Branch is: %d",Do_BranNumber(BT_a));printf("\nThe Binary Tree b's Number of Double Branch is: %d\n\n",Do_BranNumber(BT_b));}/**********************InitBiTree********************/Status InitBiTree(BiTree *BT){ //构造空二叉树*BT=NULL;return OK;}/**********************CreateBiTree********************/Status CreateBiTree(BiTree *BT){//建立二叉树TElemType ch;scanf("%c",&ch);if(ch!='#'){*BT=(BiTree)malloc(sizeof(BiTNode));if(!(*BT))return OVERFLOW;CreateBiTree(&((*BT)->lchild)); //构造左子树(*BT)->data=ch;CreateBiTree(&((*BT)->rchild)); //构造右子树}else*BT=NULL; //读入#，返回空指针return OK;}/*********************PreOrder***********************/Status PreOrder(BiTree BT){ //先序遍历if(BT){if(!(BT->data))return ERROR;printf("%c",BT->data); //访问结点PreOrder(BT->lchild); //先序遍历左子树PreOrder(BT->rchild); //先序遍历右子树}return OK;}/*******************InOrder*******************/Status InOrder(BiTree BT){ //中序遍历if(BT){if(!(BT->data))return ERROR;InOrder(BT->lchild); //中序遍历左子树printf("%c",BT->data); //访问结点InOrder(BT->rchild); //中序遍历右子树}return OK;}/*******************PostOrder*****************/Status PostOrder(BiTree BT){ //后序遍历if(BT){if(!(BT->data))return ERROR;PostOrder(BT->lchild); //后序遍历左子树PostOrder(BT->rchild); //后序遍历右子树printf("%c",BT->data); //访问结点return OK;}}/******************Do_BranNumber*****************/int Do_BranNumber(BiTree BT){if(!BT)return 0;else{if(BT->lchild&&BT->rchild)return Do_BranNumber(BT->lchild)+Do_BranNumber(BT->rchild)+1;elsereturn Do_BranNumber(BT->lchild)+Do_BranNumber(BT->rchild);}}/*****************Same_Compare*******************/Status Same_CompareTree(BiTree BT,BiTree BT1){//递归遍历并比较if(BT==NULL&&BT1==NULL)return TRUE; //两棵树均为空时认为相等else if(BT==NULL||BT1==NULL)return FALSE;else if(BT!=NULL&&BT1!=NULL){if(BT->data==BT1->data){if(Same_CompareTree(BT->lchild,BT1->lchild)&&Same_CompareTree(BT->rchild,BT1->rchild) ||Same_CompareTree(BT->lchild,BT1->rchild)&&Same_CompareTree(BT->rchild,BT1->lchild)) {return TRUE;}}}return FALSE;}。
