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

1、是我个人写的，很简单的记录下来了，呵呵呵。我的百度空间:/heihei_shaweiwei/blog/item/eec5a3de6bb28c.html#include using namespace std;/定义树的结构typedef struct _binTree char data; _binTree *lNode,*rNode;binTree;/创建二叉树void createT(binTree *&rootNode,binTree *tempNode) if(rootNode=NULL) rootNode=tempNode; return; els

2、e if(rootNode-data tempNode-data) createT(rootNode-lNode,tempNode); else if(rootNode-data data) createT(rootNode-rNode,tempNode); /打印已创建的数void printT(binTree *rootNode) if(rootNode=NULL)return ; else printT(rootNode-lNode); coutdatarNode); /先序遍历二叉树void preTraverse(binTree *rootNode) if(rootNode=NULL

3、)return ; else coutdatalNode); printT(rootNode-rNode); /中序遍历二叉树void midTraverse(binTree *rootNode) if(rootNode=NULL)return ; else printT(rootNode-lNode); coutdatarNode); /后序遍历二叉树void lastTraverse(binTree *rootNode) if(rootNode=NULL)return ; else printT(rootNode-lNode); printT(rootNode-rNode); coutda

4、talNode)+nodeTotal(rootNode-rNode); /计算二叉树的深度int treeDepth(binTree *rootNode) if(rootNode=NULL)return -1; else int lH=treeDepth(rootNode-lNode); int rH=treeDepth(rootNode-rNode); if(lHrH)return lH+1; return rH+1; /计算叶子结点的个数int leafTotal(binTree *rootNode) if(rootNode=NULL)return 0; else if(rootNode-

5、lNode=NULL & rootNode-rNode=NULL)return 1; else int lH=leafTotal(rootNode-lNode); int rH=leafTotal(rootNode-rNode); return rH+lH; int main() binTree *rootNode,*tNode; rootNode=NULL; tNode=NULL; char ch; cout按照下面给出的顺序进行输入构建二叉树：endlF D B E A C J H K G I Lch; while(ch!=0) tNode=new binTree; tNode-data=

6、ch; tNode-lNode=NULL; tNode-rNode=NULL; createT(rootNode,tNode); cinch; if(rootNode=NULL) coutTree is NULL.endl; else cout正常输出二叉树的各节点数据：; printT(rootNode); coutendl; cout先序遍历二叉树的各节点数据：; preTraverse(rootNode); coutendl; cout中序遍历二叉树的各节点数据：; midTraverse(rootNode); coutendl; cout后序遍历二叉树的各节点数据：; lastTrav

7、erse(rootNode); coutendl; cout二叉树的深度为：treeDepth(rootNode)endl; cout二叉树的结点的个数为：nodeTotal(rootNode)endl; cout二叉树的叶子结点的个数为：leafTotal(rootNode)endl; return 0;在vc6.0和dev-C+上都可以顺利运行，可以看一下 啊，呵呵。 !#include using namespace std;/*/二叉树结点类的定义templatestruct BTNode T data; BTNode * Lchild,*Rchild; BTNode(T nodeVa

8、lue = T(),BTNode* leftNode = NULL,BTNode* rightNode = NULL ) :data(nodeValue),Lchild(leftNode),Rchild(rightNode) /可选择参数的默认构造函数;/*/二叉树的建立template void createBinTree(BTNode * &root ) BTNode* p = root; BTNode* k; T nodeValue ; cinnodeValue; if(nodeValue=-1) root=NULL; else root=new BTNode(); root-data

9、= nodeValue; createBinTree(root-Lchild); createBinTree(root-Rchild); /*/二叉树的先序遍历template void preOrder( BTNode * & p) if(p) coutdataLchild); preOrder(p-Rchild); /*/二叉树的中序遍历template void inOrder(BTNode * & p) if(p) inOrder(p-Lchild); coutdataRchild); /*/二叉树的后序遍历template void levelOrder(BTNode *& p) i

10、f(p) levelOrder(p-Lchild); levelOrder(p-Rchild); coutdata ; /*/统计二叉树中结点的个数templateint countNode(BTNode * & p) if(p = NULL) return 0; return 1+countNode(p-Lchild)+countNode(p-Rchild);/*/求二叉树的深度templateint depth(BTNode *& p) if(p = NULL) return -1; int h1 = depth(p-Lchild); int h2 = depth(p-Rchild); i

11、f(h1h2)return (h1+1); return h2+1;/*/二叉树的消毁操作templateBTNode* destroy(BTNode* p) /消毁函数，用来消毁二叉树中的各个结点 if(p) return destroy(p-Lchild); return destroy(p-Rchild); delete p; /*/主函数的设计 int main () BTNode * rootNode = NULL; int choiced = 0; while(true) system(cls); coutnnn -主界面-nnn; cout 1、创建二叉树 2、先序遍历二叉树n;

12、 cout 3、中序遍历二叉树 4、后序遍历二叉树n; cout 5、统计结点总数 6、查看树深度 n; cout 7、消毁二叉树 0、退出nn; coutchoiced; if(choiced = 0) return 0; else if(choiced = 1) system(cls); cout请输入每个结点，回车确认，并以-1结束：n; createBinTree(rootNode ); else if(choiced = 2) system(cls); cout先序遍历二叉树结果：n; preOrder(rootNode); coutendl; system(pause); else

13、 if(choiced = 3) system(cls); cout中序遍历二叉树结果：n; inOrder(rootNode); coutendl; system(pause); else if(choiced = 4) system(cls); cout后序遍历二叉树结果：n; levelOrder(rootNode); coutendl; system(pause); else if(choiced = 5) system(cls); int count = countNode(rootNode); cout二叉树中结点总数为countendl; system(pause); else

14、if(choiced = 6) system(cls); int dep = depth(rootNode); cout此二叉树的深度为dependl; system(pause); else if(choiced = 7) system(cls); cout二叉树已被消毁！n; destroy(rootNode); coutendl; system(pause); else system(cls); coutnnnnnt错误选择！n; 如 5 / 3 8 / / 2 4 6 9 / / / / 1 -1-1-1-17 -1 -1 / / -1 -1 -1 -1那么输入时的序列为:5321-1

15、-1-14-1-186-17-1-19-1-1#include /预编译命令 using namespace std; struct TREE /结构体定义 int data; /整型数 struct TREE *L,*R; /TREE结构指针 ; /被调用函数insert，将结点插入二叉树 void insert(TREE *&pRoot,TREE *pNode) if(pRoot=NULL) /如果根结点为空 pRoot=pNode; /将结点pNode插入根结点 return; /返回 else /根结点不为空 /如果pNode结点数据小于等于根结点数据 if(pNode-datadat

16、a) insert(pRoot-L,pNode); /插入左子树 else /如果pNode结点数据大于根结点数据 insert(pRoot-R,pNode); /插入左子树木 /函数体结束 /被调用函数，形参为TREE结构指针，输出二叉树内容 void print(TREE *pRoot) /函数体开始 if(pRoot=NULL) /根或子树根结点为空 return; /返回 print(pRoot-L); /输出左子树内容 coutdataR); /输出右子树内容 /被调用函数结束 int main() /主函数开始 /函数体开始 struct TREE *pRoot,*pNode; /

17、TREE型结构指针 int temp; /临时变量，用于用户输入数据 pRoot=NULL; /初始化二叉树根结点为空 pNode=NULL; /初始化待插入结点的指针为空 cout请输入要插入结点的数据n; /提示信息 couttemp; /输入待插入结点数据 while(temp!=-1) /当型循环，-1为结束标志 /循环体开始 /为待插入结点分配内存单元 pNode=new TREE; pNode-data=temp; /将赋值给结点的数据域 pNode-L=NULL; /将结点的左右 pNode-R=NULL; /指针域置为空 insert(pRoot,pNode); /将pNode

18、结点插入到根为pRoo的根中 cout请输入待插入结点的数据n; /提示信息 couttemp; /输入待插入结点数据 /循环体结束 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 /二叉树结构体struct BTNode char data; BTNode *rchild; BTNode *lchild;char PreNode8 =A,B,D,F,E,G,H,C;char MidNode8 =D,F,B,G,E,H,A,C;/* 二叉树创建函数dCreateBranchTree3() 已知二叉树的前,中序遍历序列串,构造对应的二叉