C++中二叉树实现方法

1、cpp HYPERLINK /u012967763/article/details/51898281 o view plain view plain HYPERLINK /u012967763/article/details/51898281 o copy copy#ifndef_BINARYTREE_H_#define_BINARYTREE_H_constintMaxSize=100;templatestructBTNodeTdata;BTNode*lchild;BTNode*rchild;templateclassBinaryTreepublic:BinaryTree();/构造函数Bin

2、aryTree();/析构函数voidPreOrder()PreOrder(r);/递归前序遍历voidInOrder()InOrder(r);/递归中序遍历voidPostOrder()PostOrder1(r);/递归后序遍历voidPreOrder1()PreOrder1(r);/非递归前序遍历voidInOrder1()InOrder1(r);/非递归中序遍历voidPostOrder1()PostOrder(r);/非递归后序遍历voidLevelOrder()LevelOrder(r);/层序遍历BTNode*FindNode(Tx)FindNode(r,x);/查找结点intBT

3、NodeHeigth()BTNodeHeigth(r);/树的高度intNodeCount1()NodeCount1(r);/基于前序遍历求结点个数intNodeCount2()NodeCount2(r);/基于中序遍历求结点个数intNodeCount3()NodeCount3(r);/基于后序遍历求结点个数intNodeCount4()NodeCount4(r);/递归求结点个数voidDispLeaf()DispLeaf(r);/输出树的叶子结点voidprintRouteLength()printLeavesDepth(r,0);/输出树的叶子结点到根结点的路径长度boolprintA

4、ncestor(Tx)printAncestor(r,x);/输出值为x的结点的祖先结点private:BTNode*r;BTNode*CreateTree(BTNode*t);/构造函数调用voidDestroyTree(BTNode*t);/析构函数调用voidPreOrder(BTNode*t);/递归前序遍历调用voidInOrder(BTNode*t);/递归中序遍历调用voidPostOrder(BTNode*t);/递归后序遍历调用voidPreOrder1(BTNode*t);/非递归前序遍历调用voidInOrder1(BTNode*t);/非递归中序遍历调用voidPost

5、Order1(BTNode*t);/非递归后序遍历调用voidLevelOrder(BTNode*t);/层序遍历调用BTNode*FindNode(BTNode*t,Tx);intBTNodeHeigth(BTNode*t);intNodeCount1(BTNode*t);/前序遍历求结点个数调用intNodeCount2(BTNode*t);/中序遍历求结点个数调用intNodeCount3(BTNode*t);/后序遍历求结点个数调用intNodeCount4(BTNode*t);/递归求结点个数调用voidDispLeaf(BTNode*t);voidprintLeavesDepth(

6、BTNode*t,intdepth);boolprintAncestor(BTNode*t,Tx);/templateBinaryTree:BinaryTree()r=CreateTree(r);/templateBinaryTree:BinaryTree()DestroyTree(r);/templatevoidBinaryTree:DestroyTree(BTNode*t)if(t!=NULL)DestroyTree(t-lchild);DestroyTree(t-rchild);deletet;/templateBTNode*BinaryTree:CreateTree(BTNode*t)

7、Tch;std:cinch;if(ch=#)t=NULL;elset=newBTNode;t-data=ch;t-lchild=CreateTree(t-lchild);t-rchild=CreateTree(t-rchild);returnt;/templatevoidBinaryTree:PreOrder(BTNode*t)if(t!=NULL)std:coutdatalchild);PreOrder(t-rchild);/templatevoidBinaryTree:InOrder(BTNode*t)if(t!=NULL)InOrder(t-lchild);std:coutdatarch

8、ild);/templatevoidBinaryTree:PostOrder(BTNode*t)if(t!=NULL)PostOrder(t-lchild);PostOrder(t-rchild);std:coutdata;/templateBTNode*BinaryTree:FindNode(BTNode*t,Tx)BTNode*p;if(t=NULL)returnNULL;elseif(t-data=x)returnt;elsep=FindNode(t-lchild,x);if(p!=NULL)returnp;returnFindNode(t-rchild,x);/templateintB

9、inaryTree:BTNodeHeigth(BTNode*t)intlchildh,rchildh;if(t=NULL)return0;elselchildh=BTNodeHeigth(t-lchild);rchildh=BTNodeHeigth(t-rchild);return(lchildhrchildh)?(lchildh+1):(rchildh+1);/templateintBinaryTree:NodeCount4(BTNode*t)if(t=NULL)return0;elsereturn(NodeCount4(t-lchild)+NodeCount4(t-rchild)+1);/

10、templateintBinaryTree:NodeCount1(BTNode*t)intm,n,k;if(t!=NULL)m=NodeCount1(t-lchild);k=1;n=NodeCount1(t-rchild);returnm+n+k;return0;/templateintBinaryTree:NodeCount2(BTNode*t)intm,n,k;if(t!=NULL)m=NodeCount2(t-lchild);n=NodeCount2(t-rchild);k=1;returnm+n+k;return0;/templateintBinaryTree:NodeCount3(B

11、TNode*t)intm,n,k;if(t!=NULL)k=1;m=NodeCount3(t-lchild);n=NodeCount3(t-rchild);returnm+n+k;return0;/templatevoidBinaryTree:DispLeaf(BTNode*t)if(t!=NULL)if(t-lchild=NULL)&(t-rchild=NULL)std:coutdatalchild);DispLeaf(t-rchild);/template/输出路径长度voidBinaryTree:printLeavesDepth(BTNode*t,intdepth)if(t=NULL)r

12、eturn;if(t-lchild=NULL&t-rchild=NULL)std:coutdata:depthlchild,depth+1);printLeavesDepth(t-rchild,depth+1);/templateboolBinaryTree:printAncestor(BTNode*t,Tx)if(t=NULL)returnfalse;if(t-lchild!=NULL)&(t-lchild-data=x)std:coutdatarchild!=NULL)&(t-rchild-data=x)std:coutdatalchild,x)|(printAncestor(t-rchi

13、ld,x)std:coutdata;returntrue;returnfalse;/templatevoidBinaryTree:PreOrder1(BTNode*t)BTNode*stMaxSize;inttop=-1;BTNode*p;top+;sttop=t;/将根结点入栈while(top!=-1)/栈非空p=sttop;top-;std:coutdatarchild!=NULL)/右孩子先进栈top+;sttop=p-rchild;if(p-lchild!=NULL)/左孩子再进栈top+;sttop=p-lchild;/中序遍历非递归算法templatevoidBinaryTree

14、:InOrder1(BTNode*t)BTNode*stMaxSize;BTNode*p;inttop=-1;p=t;while(top!=-1)|(p!=NULL)/栈不空或p不为空时while(p!=NULL)/扫描所有左结点并进栈top+;sttop=p;p=p-lchild;if(top-1)/若栈不为空p=sttop;top-;std:coutdatarchild;/转向处理右子树/templatevoidBinaryTree:PostOrder1(BTNode*t)BTNode*stMaxSize,*p,*q;p=t;inttop=-1;boolflag;dowhile(p!=NU

15、LL)/将p结点及所有的左下结点进栈top+;sttop=p;p=p-lchild;q=NULL;/q指向栈顶结点的前一个已经访问的结点flag=true;/表示p结点的左子树已经遍历完while(top!=-1)&(flag=true)/若p结点及其右子树已访问或为空p=sttop;if(p-rchild=q)std:coutdatarchild;flag=false;while(top!=-1);/templatevoidBinaryTree:LevelOrder(BTNode*t)BTNode*quMaxSize,*p;intfront=0,rear=0;rear+;qurear=t;w

16、hile(front!=rear)/队列不为空front=(front+1)%MaxSize;p=qufront;std:coutdatalchild!=NULL)rear=(rear+1)%MaxSize;qurear=p-lchild;if(p-rchild!=NULL)rear=(rear+1)%MaxSize;qurear=p-rchild;#endif/_BINARYREE_H_源文件cpp HYPERLINK /u012967763/article/details/51898281 o view plain view plain HYPERLINK /u012967763/article/details/51898281 o copy copy#include#includeBinaryTree.husingnamespacestd;intmain()BinaryTreea;cout前序遍历：;a.PreOrder();coutendl;