一、什么是树结构
树(Tree)结构是一种描述非线性层次关系的数据结构，其中重要的是树的概念。树是n个数据结点的集合，在该集合中包含一个根结点，根结点之下分布着一些互补交叉的子集合，这些子集合是根结点的子树。树结构的基本特征如下：在一个树结构中，有且仅有一个结点没有直接前驱，这个结点就是树的根结点；
除根结点为外，其余每个结点有且仅有一个直接前驱；
每个结点可以有任意多个直接后继。
典型的树结构，如图1所示，可以直观地看到其类似于现实中树的根系，越往下层根系分支越多。图中A便是树的根结点，根结点A有三个直接后继结点B、C和D，而结点C只有一个直接前驱结点A。另外，一个树结构也可以是空，此时空树中没有数据结点，也就是一个空集合。如果树结构中仅包含一个结点，那么这也是一个树，树根便是该结点自身。从树的定义可以看出，树具有层次结构的性质。而从数学的角度来看，树具有递归的特性。在树中的每个结点及其之后的所有结点构成一个子树，这个子树也包括根结点。二、树的基本概念
父结点和子结点：每个结点子树的根称为该结点的子结点，相应的，该结点称为其子结点的父结点。
兄弟结点：具有同一父结点的结点称为兄弟结点。
结点的度：一个结点所包含子树的数量。
树的度：是指该树所有结点中最大的度。
叶结点：树中度为零的结点称为叶结点或终端结点。
分支结点：树中度不为零的结点称为分支结点或非终端结点。
结点的层数：结点的层数从树根开始计算，根结点为第1层、依次向下为第2、3、.......、n层(树是一种层次结构，每个结点都处在一定的层次上)。
树的深度：树中结点的最大层数称为树的深度。
有序树：若树中各结点的子树（兄弟结点）是按一定次序从左向右排列的，称为有序树。
无序树：若树中各结点的子树（兄弟结点）未按一定次序排列，称为无序树。
森林（forest）：n(n0)棵互不相交的树的集合。
下面从一个例子来分析上述树结构的基本概念。图2所示为一个基本的树结构。其中，结点A为根结点。结点A有3个子树，因此A的度为3。同理，结点E有两个子树，结点E的度为2。所有结点中，结点A的度为3最大，因此整个树的度为3。结点E是结点K和结点L的父结点，结点K和结点L是结点E的子结点，结点K是结点L的兄弟结点。在这个树结构中，结点G、结点H、结点K、结点J、结点N、结点O、结点P和结点Q都是叶子结点。其余的都是分支结点，整个树的深度为4。除去根结点A，留下的子树就构成了一个森林。由于树结构不是一种线性结构，很难用数学式子来表示，这就需要采用全新的方式来表示树。一般来说，常采用层次括号法。层次括号法的基本规则如下：根结点放入一对圆括号中；
根结点的子树由左至右的顺序放入括号中；
对子树作上述相同的处理。
这样，同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。按照这种方法，图1所示的树结构可以表示成如下形式：（A（B（E）），（C（F（J）），（G（K，L））），（D（H），（I（M,N））））三、二叉树
任意的树都可以转换成对应的二叉树，因此，二叉树是所有树结构的基础。1、什么是二叉树二叉树是树结构的一种特殊形式，它是n个结点的集合，每个结点最多只能有两个子结点。二叉树的子树仍然是二叉树。二叉树的一个结点上对应的两个子树分别称为左子树和右子树。由于子树有左右之分，因此二叉树是有序树。二叉树结点的最大度数为2。一个二叉树结构也可以是空，此时空二叉树中没有数据结点，是一个空集合。如果二叉树结构中仅包含一个结点，那么这也是一个二叉树，树根便是该结点自身。另外，依照子树的位置的个数，二叉树还有如下几种形式，如图3所示。其中，对于图（a），只有一个子结点且位于左子树位置，右子树为空；对于图（b），只有一个子结点且位于右子树位置，左子树位置为空；对于图（c），具有完整的两个子结点，即左子树和右子树都存在。按照二叉树的这几种形式，为了研究方便，二叉树还可以进一步细分为两种特殊的类型，满二叉树和完全二叉树。满二叉树即在二叉树中除最下一层的叶结点外，每层的结点都有两个子结点。典型的满二叉树如图4所示。完全二叉树即在二叉树中除二叉树最后一层外，其他各层的结点数都达到最大个数，且最后一层叶结点按照从左到右的顺序连续存在，只缺最后一层右侧若干结点。典型的完全二叉树，如图5所示。
从上述满二叉树和完全二叉树的定义可以看出，满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树，因为其没有达到完全满分支的结构。
2、完全二叉树的性质二叉树中树结构研究的重点是完全二叉树。对于完全二叉树，若树中包含n个结点，假设这些结点按照顺序方式存储。那么，对于任意一个结点m来说，具有如下性质：如果m!=1，则结点m的父结点的编号为m/2；
如果2*m=n，则结点m的左子树根节点的编号为2*m；若2*mn，则无左子树，也没有右子树；
如果2*m+1=n，则结点m的右子树根结点编号为2*m+1；若2*m+1n，则无右子树。
另外，对于该完全二叉树来说，其深度为[log2n]+1。这些基本性质展示了完全二叉树结构的特点，在完全二叉树的存储方式及运算处理上都有重要意义。按照数据的存储方式，树结构可以分为顺序存储结构和链式存储结构两种。3、二叉树的顺序存储顺序存储方式是最基本的数据存储方式。与线性表类似，树结构的顺序存储一般采用一维结构数组来表示。这里的关键是定义合适的次序来存放树中各个层次的数据。先来分析完全二叉树的顺序存储结构，如图6所示，左侧是一个典型的完全二叉树，每个结点的数据为字符类型。如果采用顺序存储方式，可以将其按层来存储，即先存储根结点，然后从左至右依次存储下一层结点的数据......，直到所有的结点数据完全存储。图6右侧所示为这种存储的形式。上述完全二叉树顺序存储结构的数据定义，可以采用如下形式：staticfinalintMAXLen=;//最大结点数char[]SeqBinTree=newchar[MAXLen];//定义保存二叉树数组其中，元素类型是每个结点的数据类型，这里是简单的字符型。对于复杂的数据，也可以采用自定义的对象，这样保存完全二叉树的数据成为对象数组。可以根据前面介绍的完全二叉树的性质来推算各个结点之间的位置关系。例如：对于结点D，其位于数组的第4个位置，则其父结点的编号为4/2=2，即结点B。
结点D左子结点的编号为2*4=8,即结点H。
结点D右子结点的编号为3*4+1=9,即为结点I。
非完全二叉树的存储要稍复杂些。为了忍让可以使用上述简单有效的完全二叉树的性质，将一个非完全二叉树填充为一个完全二叉树，如图7所示。图7（a）为一个非完全二叉树，将缺少的部分填补上一个空的数据结点来构成图7（b）的完全二叉树。这样，再按照完全二叉树的顺序存储方式来存储，如图8所示。下面便可以按照前述的规则来推算结点之间的关系了。但是，这种方式有很大的缺点，即浪费存储空间，这是因为其中填充了大量的无用数据。因此，顺序存储方式一般只适用于完全二叉树的情况。对于其他的情况，一般采用链式存储方式。4、二叉树的链式存储与线性结构的链式存储类似，二叉树的链式存储结构包含结点元素及分别指向左子树和右子树的引用。典型的二叉树的链式存储结构，如图9所示。二叉树的链式存储结构定义代码示例如下：classChainTreeType{charNodeData;//元素数据ChainTreeTypeLSonNode;//左子树结点引用ChainTreeTypeRSonNode;//右子树结点引用}ChainTreeTyperoot=null;//定义二叉树根结点引用
为了后续计算方便，也可以保存一个该结点的父结点的引用。此时二叉树的链式存储结构包含了结点元素、指向父结点的引用及分别指向左子树和右子树的引用。这种带父结点的二叉树链式存储结构如图10所示。
带父结点的二叉树链式存储结构定义代码如下：publicclassChainTreeType{charNodeData;//元素数据ChainTreeTypeLSonNode;//左子树结点引用ChainTreeTypeRSonNode;//右子树结点引用ChainTreeTypeParentNode;//父结点引用}ChainTreeTyperoot=null;//定义二叉树根结点引用接下来建立二叉树，并完成二叉树的基本运算。
四、准备数据
首先要准备数据，即准备在二叉树结构操作中需要用到的变量及类等。示例代码如下：staticfinalintMAXLEN=20;//最大长度publicclassCBTType{//定义二叉树结点类型Stringdata;//元素数据CBTTypeleft;//左子树结点引用CBTTyperight;//右子树结点引用}上述代码定义了二叉树结构的类CBTType。结点的具体数据保存在一个字符串data中，而引用left用来指向左子树结点，引用right用来指向右子树结点。
五、初始化二叉树
初始化二叉树，只需要将一个结点设置为二叉树的根结点，代码如下：//初始化二叉树CBTTypeInitTree(){//初始化二叉树的根CBTTypenode;//定义一个二叉树类应用if((node=newCBTType())!=null){//申请内存System.out.println("请先输入一个根结点数据:\n");node.data=input.next();node.left=null;node.right=null;if(node!=null){//如果二叉树根结点不为空returnnode;}else{returnnull;}}returnnull;}在上述代码中，首先申请内存，然后由用户输入一个根结点数据，并将指向左子树和右子树的引用设置为空，即可完成二叉树的初始化工作。
六、添加结点
添加结点即在二叉树中添加结点数据。添加结点时除了要输入结点数据外，还需要指定其父结点，以及添加的结点是作为左子树还是右子树。添加结点的代码示例如下：//添加结点voidAddTreeNode(CBTTypetreeNode){CBTTypepnode,parent;Stringdata;intmenusel;if((pnode=newCBTType())!=null){//分配内存System.out.println("输入二叉树结点数据：\n");pnode.data=input.next();pnode.left=null;//设置左右子树为空pnode.right=null;System.out.println("输入该结点的父结点数据:");data=input.next();parent=TreeFindNode(treeNode,data);//查找指定数据的结点if(parent==null){//如果未找到System.out.println("未找到该父结点!\n");pnode=null;//释放创建的结点内存return;}System.out.println("1.添加该结点到左子树\n2.添加该结点到右子树\n");do{menusel=input.nextInt();//输入选择项if(menusel==1
menusel==2){if(parent==null){System.out.println("不存在父结点，请先设置父结点!\n");}else{switch(menusel){case1://添加到左节点if(parent.left!=null){//左子树不为空System.out.println("左子树结点不为空!\n");}else{parent.left=pnode;}break;case2://添加到右子树if(parent.right!=null){//右子树不为空System.out.println("右子树结点不为空!\n");}else{parent.right=pnode;}break;default:System.out.println("无效参数!\n");}}}}while(menusel!=1menusel!=2);}}
在上述代码中，输入参数treeNode为二叉树的根结点，参数传入根结点是为了方便在代码中进行查找。程序中首先申请内存，然后由用户输入二叉树的结点数据，并设置左、右子树为空，接着指定其父结点，最后设置其作为左子树还是右子树。
七、查找结点
查找结点即在二叉树中的每一个结点中，逐个比较数据，当找到目标数据时将返回该数据所在结点的引用。查找结点的代码如示例所示：//查找结点//参数treeNode为二叉树的根结点CBTTypeTreeFindNode(CBTTypetreeNode,Stringdata){CBTTypeptr;if(treeNode==null){returnnull;}else{if(treeNode.data.equals(data)){returntreeNode;}else{//分别向左右子树递归查找if((ptr=TreeFindNode(treeNode.left,data))!=null){returnptr;}elseif((ptr=TreeFindNode(treeNode.right,data))!=null){returnptr;}else{returnnull;}}}}在上述代码中，输入参数treeNode为待查找的二叉树的根结点，输入擦书data为待查找的结点数据。程序中首先判断根结点是否为空，然后分别向左、右子树递归查找。如果当前结点的数据与查找数据相等，则返回当前结点的引用。
八、获取左子树
获取左子树即返回当前结点的左子树结点的值。由于在二叉树结构中定义了相应的引用，因此，该操作比较简单。获取左子树的示例代码如下：//获取左子树CBTTypeTreeLeftNode(CBTTypetreeNode){if(treeNode!=null){returntreeNode.left;//返回值}else{returnnull;}}在上述代码中，输入参数treeNode为二叉树的一个结点。该程序将返回该结点的左子树的引用。
九、获取右子树
获取右子树即返回当前结点的右子树结点的值。由于在二叉树结构中定义了相应的引用，因此该操作比较简单。获取右子树的示例代码如下：//获取右子树CBTTypeTreeRightNode(CBTTypetreeNode){if(treeNode!=null){returntreeNode.right;//返回值}else{returnnull;}}在上述代码中，输入参数treeNode为二叉树的一个结点。该程序将返回该结点右子树的引用。
十、判断空树
判断空树即判断一个二叉树结构是否为空。如果是空树，则表示该二叉树结构中没有数据。判断空树的代码如下：//判断空树intTreeIsEmpty(CBTTypetreeNode){if(treeNode!=null){return0;}else{return1;}}在上述代码中，输入参数treeNode为待判断的二叉树的根结点。该函数检查二叉树是否为空，为空则返回1，否则返回0。
十一、计算二叉树深度
计算二叉树深度即计算二叉树中结点的最大层数，这里往往需要采用递归算法来实现。计算二叉树深度的示例代码如下：//计算二叉树深度intTreeDepth(CBTTypetreeNode){intdepleft,depright;if(treeNode==null){return0;//对于空树，深度为0}else{depleft=TreeDepth(treeNode.left);//左子树深度（递归调用）depright=TreeDepth(treeNode.right);//右子树深度（递归调用）if(depleftdepright){returndepleft+1;}else{returndepright+1;}}}在上述代码中，输入参数treeNode为待计算的二叉树的根结点。程序中首先判断根结点是否为空，然后分别按照递归调用来计算左子树深度和右子树深度，从而完成整个二叉树深度的计算。
十二、清空二叉树
清空二叉树即将二叉树变成一个空树，这里也需要使用递归算法来实现。清空二叉树的示例代码如下：//清空二叉树voidClearTree(CBTTypetreeNode){if(treeNode!=null){ClearTree(treeNode.left);//清空左子树ClearTree(treeNode.right);//清空右子树treeNode=null;//释放当前结点所占内存}}在上述代码中，输入参数treeNode为待清空的二叉树的根结点。程序中按照递归调用来清空左子树和右子树，并且使用赋值null操作来释放当前结点所占内存，从而完成清空操作。
十三、显示结点数据
显示结点数据即显示当前结点的数据内容，此操作比较简单。显示结点数据的代码示例如下：//显示结点数据voidTreeNodeData(CBTTypetreeNode){System.out.printf("%s",treeNode.data);//输出结点数据}上述代码中，输入参数treeNode为待显示的结点。在程序中，直接使用printf方法输出该结点的数据。
十四、遍历二叉树
遍历二叉树即逐个查找二叉树中所有的结点，这是二叉树的基本操作，因为很多操作都需要首先遍历整个二叉树。由于二叉树结构的特殊性，往往可以采用多种方法进行遍历。由于二叉树代表的是一种层次结构，因此，首先按层来遍历整个二叉树。对于二叉树的按层遍历，一般不能使用递归算法来编写代码，而是使用一个循环队列来进行处理。首选将第1层（根结点）进入队列，再将第1层根结点的左右子树（第2层）进入队列......，循环处理，可以逐层遍历。上述按层遍历有点复杂，也可以使用递归来简化遍历算法。首先来分析一个二叉树中的基本结构，如图11所示。这里D表示根结点，L表示左结点，R表示右结点。一般可以采用如下几种方法来遍历整个二叉树。先序遍历：即先访问根结点，再按先序遍历左子树，最后按先序遍历右子树。先序遍历一般也称为先根次序遍历，简称为DLR遍历。
中序遍历：即先按中序遍历左子树，再访问根结点，最后按中序遍历右子树，中序遍历一般也称为中根次序遍历，简称为LDR遍历。
后序遍历：即先按后序遍历左子树，再按后序遍历右子树，最后访问根结点。后序遍历一般也称为后根次序遍历，简称为LRD遍历。
先序遍历、中序遍历和后序遍历的最大好处是可以方便地利用递归的思想来实现遍历算法。下面详细介绍这几种遍历算法的代码实现。
按层遍历算法
按层遍历算法是最直观的遍历算法。首先处理第1层即根结点，再处理第1层根结点的左右子树，即第2层......，循环处理，就可以逐层遍历。按层遍历算法的代码实现如下：
//按层遍历算法voidLevelTree(CBTTypetreeNode){CBTTypep;CBTType[]q=newCBTType[MAXLEN];//定义一个顺序栈inthead=0,tail=0;
if(treeNode!=null){//如果队首应用不为空tail=(tail+1)%MAXLEN;//计算循环队列队尾序号q[tail]=treeNode;//将二叉树根引用进队列}while(head!=tail){//队列不为空，进行循环head=(head+1)%MAXLEN;//计算循环队列的队首序号p=q[head];//获取队首元素TreeNodeData(p);//处理队首元素if(p.left!=null){//如果结点存在左子树tail=(tail+1)%MAXLEN;//计算循环队列的队尾序号q[tail]=p.left;//将左子树引用进队}if(p.right!=null){//如果结点存在右子树tail=(tail+1)%MAXLEN;//计算循环队列的队尾序号q[tail]=p.right;//将右子树引用进队}}}
上述代码中，输入参数treeNode为需要遍历的二叉树根结点。程序在整个处理过程中，首先从根结点开始，将每层的结点逐步进入队列，这样就可得到按层遍历的效果。
先序遍历算法
先序遍历算法即先按中序遍历左子树，再访问根结点，最后按中序遍历右子树。程序中可以按照递归的思路来遍历整个二叉树。先序遍历算法的示例代码如下：
//先序遍历算法voidDLRTree(CBTTypetreeNode){if(treeNode!=null){TreeNodeData(treeNode);//显示结点的数据DLRTree(treeNode.left);//先序遍历左子树DLRTree(treeNode.right);//先序遍历右子树}}
在上述代码中，输入参数treeNode为需要遍历的二叉树根结点。
中序遍历算法
中序遍历算法即先访问根结点，再按先序遍历左子树，最后按先序遍历右子树。程序中可以按照递归的思路来遍历整个二叉树。中序遍历算法的示例代码如下：
//中序遍历算法voidLDRTree(CBTTypetreeNode){if(treeNode!=null){LDRTree(treeNode.left);//中序遍历左子树TreeNodeData(treeNode);//显示结点数据LDRTree(treeNode.right);//中序遍历右子树}}
在上述代码中，输入参数treeNode为需要遍历的二叉树根结点。
后序遍历算法
后序遍历算法即先按后序遍历左子树，再按后序遍历右子树，最后访问根结点。程序中可以按照递归的思路来遍历整个二叉树。后序遍历算法的示例代码如下：
//后序遍历算法voidLRDTree(CBTTypetreeNode){if(treeNode!=null){LRDTree(treeNode.left);//后序遍历左子树LRDTree(treeNode.right);//后序遍历右子树TreeNodeData(treeNode);//显示结点数据}}在上述代码中，输入参数treeNode为需要遍历的二叉树根结点。
十五、树结构操作实例
下面给出一个完整的例子，来演示树结构的创建、插入结点和遍历等操作，代码示例如下：classCBTType{//定义二叉树结点类型Stringdata;//元素数据CBTTypeleft;//左子树结点引用CBTTyperight;//右子树结点引用}publicclassCTBTreeOperate{staticfinalintMAXLEN=20;staticScannerinput=newScanner(System.in);//初始化二叉树CBTTypeInitTree(){//初始化二叉树的根CBTTypenode;//定义一个二叉树类应用if((node=newCBTType())!=null){//申请内存System.out.println("请先输入一个根结点数据:\n");node.data=input.next();node.left=null;node.right=null;if(node!=null){//如果二叉树根结点不为空returnnode;}else{returnnull;}}returnnull;}//添加结点voidAddTreeNode(CBTTypetreeNode){CBTTypepnode,parent;Stringdata;intmenusel;if((pnode=newCBTType())!=null){//分配内存System.out.println("输入二叉树结点数据：\n");pnode.data=input.next();pnode.left=null;//设置左右子树为空pnode.right=null;System.out.println("输入该结点的父结点数据:");data=input.next();parent=TreeFindNode(treeNode,data);//查找指定数据的结点if(parent==null){//如果未找到System.out.println("未找到该父结点!\n");pnode=null;//释放创建的结点内存return;}System.out.println("1.添加该结点到左子树\n2.添加该结点到右子树\n");do{menusel=input.nextInt();//输入选择项if(menusel==1
menusel==2){if(parent==null){System.out.println("不存在父结点，请先设置父结点!\n");}else{switch(menusel){case1://添加到左节点if(parent.left!=null){//左子树不为空System.out.println("左子树结点不为空!\n");}else{parent.left=pnode;}break;case2://添加到右子树if(parent.right!=null){//右子树不为空System.out.println("右子树结点不为空!\n");}else{parent.right=pnode;}break;default:System.out.println("无效参数!\n");}}}}while(menusel!=1menusel!=2);}}//查找结点//参数treeNode为二叉树的根结点CBTTypeTreeFindNode(CBTTypetreeNode,Stringdata){CBTTypeptr;if(treeNode==null){returnnull;}else{if(treeNode.data.equals(data)){returntreeNode;}else{//分别向左右子树递归查找if((ptr=TreeFindNode(treeNode.left,data))!=null){returnptr;}elseif((ptr=TreeFindNode(treeNode.right,data))!=null){returnptr;}else{returnnull;}}}}//获取左子树CBTTypeTreeLeftNode(CBTTypetreeNode){if(treeNode!=null){returntreeNode.left;//返回值}else{returnnull;}}//获取右子树CBTTypeTreeRightNode(CBTTypetreeNode){if(treeNode!=null){returntreeNode.right;//返回值}else{returnnull;}}//判断空树intTreeIsEmpty(CBTTypetreeNode){if(treeNode!=null){return0;}else{return1;}}//计算二叉树深度intTreeDepth(CBTTypetreeNode){intdepleft,depright;if(treeNode==null){return0;//对于空树，深度为0}else{depleft=TreeDepth(treeNode.left);//左子树深度（递归调用）depright=TreeDepth(treeNode.right);//右子树深度（递归调用）if(depleftdepright){returndepleft+1;}else{returndepright+1;}}}//清空二叉树voidClearTree(CBTTypetreeNode){if(treeNode!=null){ClearTree(treeNode.left);//清空左子树ClearTree(treeNode.right);//清空右子树treeNode=null;//释放当前结点所占内存}}//显示结点数据voidTreeNodeData(CBTTypetreeNode){System.out.printf("%s",treeNode.data);//输出结点数据}//按层遍历算法voidLevelTree(CBTTypetreeNode){CBTTypep;CBTType[]q=newCBTType[MAXLEN];//定义一个顺序栈inthead=0,tail=0;if(treeNode!=null){//如果队首应用不为空tail=(tail+1)%MAXLEN;//计算循环队列队尾序号q[tail]=treeNode;//将二叉树根引用进队列}while(head!=tail){//队列不为空，进行循环head=(head+1)%MAXLEN;//计算循环队列的队首序号p=q[head];//获取队首元素TreeNodeData(p);//处理队首元素if(p.left!=null){//如果结点存在左子树tail=(tail+1)%MAXLEN;//计算循环队列的队尾序号q[tail]=p.left;//将左子树引用进队}if(p.right!=null){//如果结点存在右子树tail=(tail+1)%MAXLEN;//计算循环队列的队尾序号q[tail]=p.right;//将右子树引用进队}}}//先序遍历算法voidDLRTree(CBTTypetreeNode){if(treeNode!=null){TreeNodeData(treeNode);//显示结点的数据DLRTree(treeNode.left);//先序遍历左子树DLRTree(treeNode.right);//先序遍历右子树}}//中序遍历算法voidLDRTree(CBTTypetreeNode){if(treeNode!=null){LDRTree(treeNode.left);//中序遍历左子树TreeNodeData(treeNode);//显示结点数据LDRTree(treeNode.right);//中序遍历右子树}}//后序遍历算法voidLRDTree(CBTTypetreeNode){if(treeNode!=null){LRDTree(treeNode.left);//后序遍历左子树LRDTree(treeNode.right);//后序遍历右子树TreeNodeData(treeNode);//显示结点数据}}publicstaticvoidmain(String[]args){CBTTyperoot=null;//root为指向二叉树根结点的引用intmenusel;//表示选择项CTBTreeOperatet=newCTBTreeOperate();//设置根元素root=t.InitTree();//添加结点do{System.out.println("请选择菜单添加二叉树的结点\n");System.out.println("0.退出\t");//显示菜单System.out.println("1.添加二叉树的结点\n");menusel=input.nextInt();switch(menusel){case1:t.AddTreeNode(root);break;case0:break;default:;}}while(menusel!=0);//遍历do{System.out.printf("请选择菜单遍历二叉树，输入0表示退出\n");System.out.printf("1.先序遍历DLR\t");//显示菜单System.out.printf("2.中序遍历LDR\n");System.out.printf("3.后序遍历LRD\t");System.out.printf("4.按层遍历\n");menusel=input.nextInt();switch(menusel){case0:break;case1:System.out.printf("\n先序遍历DLR的结果：");t.DLRTree(root);System.out.printf("\n");break;case2:System.out.printf("\n中序LDR遍历的结果：");t.LDRTree(root);System.out.printf("\n");break;case3:System.out.printf("\n后序遍历LRD的结果：");t.LRDTree(root);System.out.printf("\n");break;case4:System.out.printf("\n按层遍历的结果：");t.LevelTree(root);System.out.printf("\n");break;default:;}}while(menusel!=0);//深度System.out.printf("\n二叉树深度为:%d\n",t.TreeDepth(root));//清空二叉树t.ClearTree(root);root=null;}}在上述代码中，主方法首先初始化二叉树，设置根元素。然后由用户来选择添加结点的操作。接着分别可以选择先序遍历、中序遍历、后序遍历和按层遍历4中方式来遍历整个二叉树。最后，输出该二叉树的深度，并清空二叉树，结束整个操作过程。在程序执行过程中，首先初始化输入根结点为A，然后选择菜单“1”分别添加结点B作为结点A的左子树，添加结点C为结点A的右子树......，整个程序的执行过程，如下所示。添加完所有的结点后，选择菜单“0”便可以退出结点的添加过程，进而执行后面的程序。程序接下来便是执行不同的二叉树遍历操作，按照菜单的指示分别选择先序遍历、中序遍历、后序遍历和按层遍历4种方式。程序执行结果如下所示。最后，输入菜单“0”退出遍历过程。程序最后输出该二叉树的深度为3，并清空整个二叉树，从而完成整个操作过程。
请先输入一个根结点数据:a请选择菜单添加二叉树的结点0.退出1.添加二叉树的结点1输入二叉树结点数据：b输入该结点的父结点数据:a1.添加该结点到左子树2.添加该结点到右子树1请选择菜单添加二叉树的结点0.退出1.添加二叉树的结点1输入二叉树结点数据：c输入该结点的父结点数据:a1.添加该结点到左子树2.添加该结点到右子树2请选择菜单添加二叉树的结点0.退出1.添加二叉树的结点1输入二叉树结点数据：d输入该结点的父结点数据:b1.添加该结点到左子树2.添加该结点到右子树1请选择菜单添加二叉树的结点0.退出1.添加二叉树的结点0请选择菜单遍历二叉树，输入0表示退出1.先序遍历DLR2.中序遍历LDR3.后序遍历LRD4.按层遍历
1先序遍历DLR的结果：abdc请选择菜单遍历二叉树，输入0表示退出1.先序遍历DLR2.中序遍历LDR3.后序遍历LRD4.按层遍历2中序LDR遍历的结果：dbac请选择菜单遍历二叉树，输入0表示退出1.先序遍历DLR2.中序遍历LDR3.后序遍历LRD4.按层遍历3后序遍历LRD的结果：dbca请选择菜单遍历二叉树，输入0表示退出1.先序遍历DLR2.中序遍历LDR3.后序遍历LRD4.按层遍历4按层遍历的结果：abcd请选择菜单遍历二叉树，输入0表示退出1.先序遍历DLR2.中序遍历LDR3.后序遍历LRD4.按层遍历0二叉树深度为:3预览时标签不可点收录于话题#个上一篇下一篇