下载文档原格式
第三节二叉树的遍历方法和递归实现什么是二叉树的遍历？二叉树的遍历：是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅被访问一次。
为什么要遍历二叉树？遍历是二叉树中经常要用到的一种操作。
因为在实际应用问题中，常常需要按一定的顺序对二叉树中的每个结点逐个进行访问。
如何遍历二叉树？由二叉树的定义可知，一棵二叉树由根结点、根结点的左子树和根结点的右子树三部分组成。
因此，只要依次遍历这三部分，就可以遍历整个二叉树。
遍历二叉树主要有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.掌握二叉树中序遍历的算法原理和实现方法；3.掌握二叉树后序遍历的算法原理和实现方法；4.使用递归和非递归两种方式实现以上三种遍历算法；5.进行正确性验证和性能评估。
三、方法1.算法原理：1.1先序遍历：先访问根节点，然后递归遍历左子树，再递归遍历右子树；1.2中序遍历：先递归遍历左子树，然后访问根节点，最后递归遍历右子树；1.3后序遍历：先递归遍历左子树，再递归遍历右子树，最后访问根节点。
2.实现方法：2.1递归实现：采用函数递归调用的方式，实现对二叉树的遍历；2.2非递归实现：采用栈的数据结构，模拟递归的过程，实现对二叉树的遍历。
四、实验步骤1.数据结构设计：1.1定义二叉树的节点结构，包括节点值和两个指针（分别指向左子节点和右子节点）；1.2定义一个栈结构，用于非递归实现时的辅助存储。
2.先序遍历：2.1递归实现：按照先序遍历的原理，通过递归调用遍历左子树和右子树，再输出根节点；2.2非递归实现：通过栈结构模拟递归的过程，先将根节点入栈，然后循环将栈顶节点弹出并输出，再将其右子节点入栈，最后将左子节点入栈，直到栈为空。
3.中序遍历：3.1递归实现：按照中序遍历的原理，通过递归调用先遍历左子树，再输出根节点，最后遍历右子树；3.2非递归实现：先将根节点入栈，然后循环将左子节点入栈，直到左子节点为空，然后弹出栈顶节点并输出，再将其右子节点入栈，重复以上过程直到栈为空。
4.后序遍历：4.1递归实现：按照后序遍历的原理，通过递归调用先遍历左子树，再遍历右子树，最后输出根节点；4.2非递归实现：通过栈结构模拟递归的过程，先将根节点入栈，然后重复以下步骤直到栈为空。
二叉树递归遍历数据结构实验报告一、引言二叉树是一种简单而重要的树形结构，在计算机科学领域中被广泛应用。
它具有良好的动态性能和数据组织能力，递归遍历是二叉树最基本的操作之一、本次实验旨在通过编程实现二叉树的递归遍历算法，并对实验结果进行分析和总结。
二、实验目的1.掌握二叉树的基本概念和操作方法；2.熟悉递归算法的实现过程；3.实践二叉树的递归遍历算法。
三、实验原理1.二叉树的概念二叉树是一种树形结构，其中每个节点最多有两个子节点，被分为左子树和右子树。
树中每个节点最多有一个父节点，除了根节点没有父节点。
二叉树的递归定义：（1）空树是一个二叉树；（2）一棵非空二叉树由根节点和左子树、右子树组成。
2.二叉树的递归遍历二叉树的遍历方式分为三种：前序遍历、中序遍历和后序遍历。
其定义如下：（1）前序遍历：根节点->左子树->右子树；（2）中序遍历：左子树->根节点->右子树；（3）后序遍历：左子树->右子树->根节点。
四、实验过程1.定义二叉树的数据结构和相关操作方法首先，我们需要定义二叉树的节点结构，包含数据域和左右子节点指针域。
然后，可定义插入节点、删除节点等操作方法。
2.实现递归遍历算法（1）前序遍历前序遍历的流程为：先访问根节点，再前序遍历左子树，最后前序遍历右子树。
通过递归调用即可实现。
伪代码如下：```void preOrder(Node* root)if (root != NULL)cout << root->data;preOrder(root->left);preOrder(root->right);}（2）中序遍历和后序遍历与前序遍历类似，中序遍历的流程为：先中序遍历左子树，再访问根节点，最后中序遍历右子树。
后序遍历的流程为：先后序遍历左子树，再后序遍历右子树，最后访问根节点。
也可以通过递归调用实现。
伪代码如下：```void inOrder(Node* root)if (root != NULL)inOrder(root->left);cout << root->data;inOrder(root->right);}void postOrder(Node* root)if (root != NULL)postOrder(root->left);postOrder(root->right);cout << root->data;}五、实验结果与分析我们通过编写测试数据并调用递归遍历算法进行遍历，得到以下结果：（1）前序遍历结果：ABDECFG（2）中序遍历结果：DBEAFCG（3）后序遍历结果：DEBFGCA实验结果与预期相符，表明递归遍历算法编写正确。
《数据结构》第六次实验报告学生学生班级学生学号指导老师一、实验容1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。
2) 输出树的深度，最大元，最小元。
二、需求分析遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。
递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。
直到递归全部结束。
下面重点来讲述非递归方法：首先介绍先序遍历：先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。
具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。
再次介绍中序遍历：中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。
具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。
如此循环直至结点指针和栈均为空，遍历结束。
最后介绍后序遍历：后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。
如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。
实验报告课程名称：数据结构与算法课程类型：必修实验项目：树型结构及应用实验题目：二叉树的遍历及应用一、实验目的1.通过对二叉树的各种操作更好理解树型结构及其应用；2.了解各种二叉树的遍历算法；3.理解递归和非递归的差别。
二、实验要求及实验环境实验要求：1．编写建立二叉树(大于10个结点) 的二叉链表存储结构（左右链表示）的程序，并以适当的形式显示和保存二叉树；2．采用二叉树的二叉链表存储结构，编写程序实现二叉树的先序、中序和后序遍历的递归和非递归算法以及层序遍历算法，并以适当的形式显示和保存二叉树及其相应的遍历序列；3．给定一个二叉树，编写算法完成下列应用:（1）判断其是否为完全二叉树；（2）求二叉树中任意两个结点的公共祖先。
实验环境：codeblocks/Dev-C++三、设计思想（本程序中的用到的所有数据抽象数据性ADT的定义，主程序的流程图及各程序模块之间的调用关系）1. 所用的抽象数据性ADT的定义1）逻辑结构：栈：是一种特殊形式的线性表，所有的插入和删除操作都在栈顶。
栈的置空操作：void makenull(stack* s)判断栈是否为空：int empty(stack* s)返回栈顶元素：btree* top(stack* s)入栈操作：void push(btree* x, stack* s)出栈操作：void pop(stack* s)队列：是一种特殊形式的线性表，队尾入队，队首出队。
将队列置空：void makenull_q(queue* duilie)在队列后面插入T：void enqueue_q(btree* T, queue* duilie)判断队列是否为空：int empty_q(queue* duilie)返回队列的第一个元素：btree* front_q(queue* duilie)删除队列的第一个元素:void dequeue_q(queue* duilie)2) 存储结构定义了一个字符栈stack，一个队列queue，一个队列里面的节点node2，一个广义表数组char widechart[100]，一个存储树节点数据的数组char store_ancestors[100]。
二叉树的遍历实验报告一、需求分析在二叉树的应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是二叉树的遍历问题。
对二叉树的数据结构进行定义，建立一棵二叉树，然后进行各种实验操作。
二叉树是一个非线性结构，遍历时要先明确遍历的规则，先访问根结点还时先访问子树，然后先访问左子树还是先访问有右子树，这些要事先定好，因为采用不同的遍历规则会产生不同的结果。
本次实验要实现先序、中序、后序三种遍历。
基于二叉树的递归定义，以及遍历规则，本次实验也采用的是先序遍历的规则进行建树的以及用递归的方式进行二叉树的遍历。
二、系统总框图三、各模块设计分析（1）建立二叉树结构建立二叉树时，要先明确是按哪一种遍历规则输入，该二叉树是按你所输入的遍历规则来建立的。
本实验用的是先序遍历的规则进行建树。
二叉树用链表存储来实现，因此要先定义一个二叉树链表存储结构。
因此要先定义一个结构体。
此结构体的每个结点都是由数据域data 、左指针域Lchild 、右指针域Rchild 组成，两个指针域分别指向该结点的左、右孩子，若某结点没有左孩子或者右孩子时，对应的指针域就为空。
最后，还需要一个链表的头指针指向根结点。
要注意的是，第一步的时候一定要先定义一个结束标志符号，例如空格键、＃等。
当它遇到该标志时，就指向为空。
建立左右子树时，仍然是调用create（）函数，依此递归进行下去，直到遇到结束标志时停止操作。
（2）输入二叉树元素输入二叉树时，是按上面所确定的遍历规则输入的。
最后，用一个返回值来表示所需要的结果。
（3）先序遍历二叉树当二叉树为非空时，执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
（4）中序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
（5）后序遍历二叉树当二叉树为非空时，程序执行以下三个操作：访问根结点、先序遍历左子树、先序遍历右子树。
实验六二叉树的递归遍历及其应用一、实验目的1、深入了解二叉树递归的逻辑结构特征及其基本操作。
2、了解二叉树各种存储结构的特点及其适用范围，熟练掌握二叉树的二叉链表结构的定义及其递归遍历算法、按层次遍历算法的c语言实现，能深入了解递归算法的执行过程。
3、熟练掌握二叉树递归遍历算法的应用。
一、实验内容和要求2、设计并验证如下算法：与“ 12.7.4参考源程序”类似，按中序序列输入建立两棵二叉树的二叉链表结构，求双分支结点数，判断两棵树是否相等。
3、设计并验证如下算法：按层次遍历二叉树，打印结点所在的层次，并求该二叉树的宽度。
二、实验过程及结果(第一题)一、需求分析1、从键盘输入二叉树的序列，但由于建树是从根结点往下建立的，故只能输入先序序列，则按照中序建树完成二叉树的创建。
2、从键盘输入一段正确的序列后，按回车键自动生成二叉树，若该序列不能生成一颗二叉树，则程序无法继续进行，只能退出。
3、程序能实现的功能包括：①初始化二叉树；②创建一棵完整二叉树；③先中后序遍历二叉树;④求二叉树双分支结点数；⑤比较两棵二叉树是否相等；、概要设计1、二叉树的抽象数据类型定义：ADT Bin aryTree{数据对象D D是具有相同特征的数据元素的集合。
数据关系R若。
=空，贝U只=空，称BinaryTree 为空二叉树；若D!=空，则R={H}, H是如下二元关系：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}!= ①，则存在D-{root}={D1,Dr} ，且D1A Dr=Q；(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}；(4) ( D1,{H1})是一棵符合本定义的二叉树，称为根的左子树，(Dr,{Hr}) 是一棵符合本定义的二叉树，称为根的右子树。
二叉树的递归及非递归的遍历及其应用二叉树是一种常见的数据结构，由节点和边组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。
递归和非递归是两种遍历二叉树的方法，递归是通过递归函数实现，而非递归则利用栈的数据结构来实现。
二叉树的遍历是指按照一定的顺序访问二叉树中的每个节点。
常见的遍历方式有前序遍历、中序遍历和后序遍历。
1.前序遍历（Preorder Traversal）：在前序遍历中，首先访问根节点，然后递归地遍历左子树和右子树。
遍历顺序为：根节点-左子树-右子树。
2.中序遍历（Inorder Traversal）：在中序遍历中，首先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。
遍历顺序为：左子树-根节点-右子树。
3.后序遍历（Postorder Traversal）：在后序遍历中，首先递归地遍历左子树和右子树，最后访问根节点。
遍历顺序为：左子树-右子树-根节点。
递归遍历方法的实现相对简单，但可能存在性能问题，因为递归调用会导致函数的调用和返回开销，尤其是在处理大规模二叉树时。
而非递归遍历方法则能够通过利用栈的特性，在迭代过程中模拟函数调用栈，避免了函数调用的性能开销。
非递归遍历二叉树的方法通常利用栈来实现。
遍历过程中，将节点按照遍历顺序入栈，然后访问栈顶元素，并将其出栈。
对于前序遍历和中序遍历，入栈顺序不同，而对于后序遍历，需要维护一个已访问标记来标识节点是否已访问过。
以下是非递归遍历二叉树的示例代码（以前序遍历为例）：```pythonclass TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef preorderTraversal(root): if not root:return []stack = []result = []stack.append(root)while stack:node = stack.pop()result.append(node.val)if node.right:stack.append(node.right)if node.left:stack.append(node.left)return result```在实际应用中，二叉树的遍历方法有很多应用。
实验六二叉树的递归遍历及其应用一、实验目的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;}。
