实验报告书课程名称：《数据结构》实验题目：实验四树一、实验目的（1）熟练掌握二叉树的二叉链表表示及前序创建算法与实现；（2）熟练掌握二叉树的前序、中序和后序递归遍历算法与实现；（3）掌握中序遍历线索二叉树的基本算法与实现（4）掌握中序遍历线索化二叉树的算法与实现；（5）按照实验题目要求独立完成实验内容；（6）认真书写实验报告,并按时提交二、实验内容（1）按照先序序列建立下图所示二叉树的二插链表树，结点元素类型取字符型，树的字符序列从键盘逐个动态交互输入。
（2）在第（1）步建立好的二叉链表树上实施前序、中序和后序递归遍历，并输出相应遍历序列。
（3）在第（1）步建立好的二叉链表树上实施前序遍历的叶子结点输出及其个数统计。
（4）在第1) 步建立好的二叉链表树上实施二叉树性质三的验证；（5）在第1）步建立好的二叉链表树上实施中序非递归遍历，并输出相应遍历序列。
ABC DE FG三、实验步骤#include<stdio.h>#include<stdlib.h>typedef struct Node//声明二叉树的二叉链表结点的结构{char data;struct Node*LChild;struct Node*RChild;}BiTNode,*BiTree;void title();void CheckTree(int tag1);void CreateBiTree(BiTree*bt);void Visit(char ch);void PreOrder(BiTree root);void InOrder(BiTree root);void PostOrder(BiTree root);void YePreOrder(BiTree root);void Leaf(BiTree root);int CountDouble(BiTree T);int tag=0;int n;int LeafCount=0;int main(){int flag=1;BiTree b;while(flag!=0){title();printf("get the action number:\n");scanf("%d",&flag);getchar;switch(flag){case 1:printf("get the Tree:\n");CreateBiTree(&b);tag++;printf("new tree has been created\n");break;case 2:printf("先序遍历二叉树\n");CheckTree(tag);PreOrder(b);printf("\n");break;case 3:printf("中序遍历二叉树\n");CheckTree(tag);InOrder(b);printf("\n");break;case 4:printf("后序遍历二叉树\n");CheckTree(tag);PostOrder(b);printf("\n");break;case 5:printf("输出叶子节点:\n");YePreOrder(b);putchar('\n');Leaf(b);printf("叶子节点数:%d\n",LeafCount);break;case 6:n=CountDouble(b);printf("有两个节点数的:%d\n",n);printf("叶子节点数:%d\n",LeafCount);printf("二叉树性质:%d=%d+1\n",LeafCount,n);break;case 0:return 0;default:printf("ERROR!!!\n");}}return 0;}void title(){printf("=====BiTree Action=====\n");printf("1 先序建立特定二叉树\n");printf("2 先序遍历二叉树\n");printf("3 中序遍历二叉树\n");printf("4 后序遍历二叉树\n");printf("5 先序遍历叶子并计算数量\n");printf("6 二叉树性质三的验证\n");printf("0 结束程序\n");}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);//生成右子树}}void CheckTree(int tag1){if(tag1==0){printf("Tree hasn't been created ERROR!!!\n");}}void Visit(char ch){printf("%c",ch);}void PreOrder(BiTree root)//先序遍历二叉树{if(root!=NULL){Visit(root->data);PreOrder(root->LChild);PreOrder(root->RChild);}}void InOrder(BiTree root)//中序遍历二叉树{if(root!=NULL){InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);}}void PostOrder(BiTree root)//后序遍历二叉树{if(root!=NULL){PostOrder(root->LChild);PostOrder(root->RChild);Visit(root->data);}}void YePreOrder(BiTree root)//先序遍历叶子{if(root!=NULL){if(root->LChild==NULL&&root->RChild==NULL)Visit(root->data);YePreOrder(root->LChild);YePreOrder(root->RChild);}}void Leaf(BiTree root)//统计叶子结点数目{if(root!=NULL){Leaf(root->LChild);Leaf(root->RChild);if(root->LChild==NULL&&root->RChild==NULL){LeafCount++;//保存叶子结点数目的全局变量，调用之前初始化值为0 }}}int CountDouble(BiTree T)//验证性质3：叶结点数=度数为2的结点数+1{int count=0;if(T==NULL||(T->LChild==NULL&&T->RChild==NULL)){return 0;}else{if(T->LChild!=NULL&&T->RChild!=NULL)count++;return count+CountDouble(T->LChild)+CountDouble(T->RChild);}}四、实验结果分析要注意二叉树的各种遍历方法，一是重点理解访问根节点，二是注意对具体的实现问题是否需要考虑遍历的次序问题。
中序非递归遍历利用到了前面的数据结构栈，而在二叉树的实验中递归思想得到了充分的应用。
先序、中序、后序遍历具有共同的编程思想，先序遍历例程先输出节点数据，再递归输出左孩子（右孩子）的根节点，不断循环，直到遍历整个树。
返回叶子节点个数：类似返回节点个数的实现。