代码都是书上的。 需要注意的是怎么输入。 第一行 为自己输入的数据，在创建的二叉树中数据域为char型，故空格和enter键也会被存入二叉树数据中。‘#’号总比二叉树数据结点多一个，不然一直在输入，无法进入输出。输出是中序遍历打印的。 根据上面的输入数据可以画出自己创建的二叉树（上图）。这是草稿纸上的操作，代码结果只输出中序遍历结果。
完整代码如下：
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct BiTNode { char data;//结点的数据域 struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree; void CreateTree(BiTree &T)//创建二叉树，这里是先序遍历的顺序建立的二叉链表 递归形式 { char ch,trmp; scanf("%c",&ch);//输入链表数据 if(ch == '#')//如果出现输入的是#,终止递归。终止递归条件 T = NULL; else { T = (BiTNode*)malloc(sizeof(BiTNode));//申请一个根结点 T->data = ch;//对根结点进行赋值 CreateTree(T->lchild);//递归创建左子树 CreateTree(T->rchild);//递归创建右子树 } } bool TreeEmpty(BiTree T)//判断二叉树是否为空 { if(T == NULL)//bool类型，如果二叉树为空，返回true,否则返回false return true; return false; } void InOrderTraverse(BiTree T)//打印二叉树 ，中序遍历二叉树的递归算法 { if(T)//递归终止条件是T为NULL { InOrderTraverse(T->lchild);//中序遍历左子树 printf("%c ",T->data);//输出打印根结点 InOrderTraverse(T->rchild);//中序遍历右子树 } } void CopyTree(BiTree T,BiTree &NewT)//复制一颗和T完全相同的二叉树 { if(T == NULL)//递归终止条件 { NewT = NULL; return ; } else { NewT = (BiTNode*)malloc(sizeof(BiTNode));//申请一个根结点 NewT->data = T->data;//复制根结点 CopyTree(T->lchild,NewT->lchild);//递归复制左子树 CopyTree(T->rchild,NewT->rchild);//递归复制右子树 } } int Depth(BiTree T)//计算二叉树T的深度 { int m = 0, n = 0;//定义两个变量 if(TreeEmpty(T))//递归终止条件 return 0; else { m = Depth(T->lchild);//递归计算左子树的深度记为m n = Depth(T->rchild);//递归计算右子树的深度记为n if(m>n)//二叉树的深度为m与n的较大者加1 return m+1; return n+1; } } int NodeCount(BiTree T)//统计二叉树T中的结点的个数 { if(T == NULL)//递归终止条件 return 0; else//结点个数为左子树的结点个数+右子树的结点个数 return NodeCount(T->lchild)+NodeCount(T->rchild)+1; } int main() { BiTree T;//创建一个空二叉树 CreateTree(T);// 创建二叉树 InOrderTraverse(T);//打印二叉树 中序遍历 printf("\n"); BiTree NewT;//创建一个新二叉树 CopyTree(T,NewT);//复制二叉树 InOrderTraverse(NewT); printf("\n"); printf("%d\n",Depth(T));//二叉树T的深度 printf("%d\n",NodeCount(T));//二叉树的结点个数 return 0; }（完）
