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

是我个人写的，很简单的记录下来了，呵呵呵。我的百度空间:/heihei_shaweiwei/blog/item/eec5a3de6bb28c0462279805.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; else 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)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); coutdatalNode)+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-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=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后序遍历二叉树的各节点数据：; lastTraverse(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 nodeValue = 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 = 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) if(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); if(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; 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 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 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-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-datadata) 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; /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结点插入到根为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() 已知二叉树的前,中序遍历序列串,构造对应的二