二叉树的建立与遍历,叶子结点的数目以及树的深度的求法,采用递归求解

指针域置为空
insert(pRoot,pNode); //将pNode结点插入到根为pRoo的根中
cout<<"请输入待插入结点的数据\n"; //提示信息
cout<<"如果输入-1表示插入过程结束\n"; //提示信息
cin>>temp; //输入待插入结点数据
} //循环体结束
if(pRoot==NULL) //如果根结点为空
cout<<"这是一棵空树。\n"; //输出空树信息
else
print(pRoot); //调用insert函数，输出二叉树内容
return 0;
} //主函数结束语


根据楼主给出的图，可以用下面的代码来进行构建来构建，代码经过实际的运行验证，无错，运行结果是楼主所给的二叉树。
思想：结合先序和中序遍历来构建给定的二叉树。
所给的二叉树图中，先序：A,B,D,E,C,F,G
中序：D,B,E,A,F,C,G
下面直接贴出代码(建立工程后，贴上下面代码可直接运行)：

#include "stdafx.h"
#include <malloc.h>

//二叉树结构体
struct BTNode
{
char data;
BTNode *rchild;
BTNode *lchild;
};
char PreNode[8] ={'A','B','D','F','E','G','H','C'};
char MidNode[8] ={'D','F','B','G','E','H','A','C'};
/*
二叉树创建函数dCreateBranchTree3()<非递归算法>
已知二叉树的前,中序遍历序列串,构造对应的二叉树
<编程思想>:
首先,在前序遍历序列中的首元素是二叉树的根节点,接着
,在中序遍历序列中找到此节点,那么在此节点以前的节点必为
其左孩子节点,以后的必为其右孩子节点;
然后,在中序遍历序列中,根节点的左子树和右子树再分别
对应子树前序遍历序列的首字符确定子树的根节点,再由中序
遍历序列中根节点的位置分别确定构成它们的左子树和右子树
的节点;
依次类推,确定二叉树的全部节点,构造出二叉树.
参数描述：
char *pre: 前序遍历序列
char *mid: 中序遍历序列
int n: 遍历序列中节点个数
返回值:
dCreateBranchTree3 = 新建二叉树的根节点指针
*/
BTNode *dCreateBranchTree3(char *pre,char *mid,int n)
{
BTNode *p;
char *t;
int left;
if(n<=0)
return(NULL);
p = (BTNode *)malloc(sizeof(BTNode));
p->data = *pre;
for(t=mid;t<mid+n;t++)
if(*t==*pre) break; /*在中序遍历序列中查找根节点*/
left = t - mid; /*左子树的节点个数*/
p->lchild = dCreateBranchTree3(pre+1,mid,left);
p->rchild = dCreateBranchTree3(pre+1+left,t+1,n-1-left);

return(p);
}
int _tmain(int argc, _TCHAR* argv[])
{
BTNode *pTree = dCreateBranchTree3(PreNode, MidNode, 8);
_getch();
return 0;
}