为什么需要树结构1、数组存储方式分析：优点：通过下标访问元素，速度快。对于排序好的数组，还可以使用二分查找来提高检索速度。缺点：如果检索一个特定的值，或者插入一个值（按一定的顺序），它会整体移动，效率较低。2、链式存储方式分析：优点：一定程度上优化了数组存储方式（例如：插入一个值节点，只需要将插入的节点链接到链表即可，删除效率非常高高的）。缺点：查找时，效率还是很低，需要从头节点开始遍历。3、树存储方式分析：可以提高数据存储和读取的效率。例如，使用二叉排序树（Binarysorttree）可以保证数据检索的速度和数据插入、删除、修改的速度。.假设一组[7,3,10,1,5,9,12]以树的形式存储，分析如下：二元的前序遍历，中序遍历，后序遍历树的前序遍历：输出父节点，输出左节点，输出右节点；中序遍历：输出左节点，输出父节点，输出右节点；后序遍历：输出左节点，输出右节点，输出父节点；需求案例完成一个二叉树节点存储和前序如下遍历搜索、中序遍历搜索、后序遍历搜索和删除节点功能。删除节点的要求如下：如果删除的节点是叶子节点，则删除该节点。如果删除的节点是非叶节点，则删除树。测试，删除5号叶子节点和3号子树。代码示例packagecom.xie.tree；publicclassBinaryTreeDemo{publicstaticvoidmain(String[]args){BinaryTreebinaryTree=newBinaryTree();HeroNoderoot=newHeroNode(1,"宋江");HeroNodenode2=newHeroNode(2,"吴勇");HeroNodenode3=newHeroNode(3,"卢俊义"));HeroNodenode4=newHeroNode(4,"林冲");HeroNodenode5=newHeroNode(5,"关胜");//先手动创建二叉树，再使用递归root.setLeft(node2);root.setRight(node3);node3.setRight(node4);node3.setLeft(node5);binaryTree.setRoot(root);//前序遍历System.out.println("前序遍历");binaryTree.preOrder();//中序遍历System.out.println("中序遍历");binaryTree.infixOrder();//后续遍历System.out.println("后续遍历");binaryTree.postOrder();//前序遍历搜索System.out.println("前序遍历搜索~~");HeroNoderesultNode=binaryTree.preOrderSearch(5);if(resultNode!=null){System.out.printf("找到了，信息没有=%d,name=%s\n",resultNode.getNo(),resultNode.getName());System.out.println("遍历次数："+HeroNode.preCount);}else{System.out.println("Notfound");}//中序遍历查找System.out.println("中序遍历查找~~");HeroNoderesultNode1=binaryTree.infixOrderSearch(5);if(resultNode1!=null){System.out.printf("找到，信息为no=%d,name=%s\n",resultNode1.getNo(),resultNode1.getName());System.out.println("遍历次数："+HeroNode.infoxCount);}else{System.out.println("Notfound");}//后序遍历查找System.out.println("后序遍历查找~~");HeroNoderesultNode2=binaryTree.postOrderSearch(5);if(resultNode2!=null){System.out.printf("找到，信息为no=%d,name=%s\n",resultNode2.getNo(),resultNode2.getName());System.out.println("遍历次数："+HeroNode.postCount);}else{System.out.println("未找到");}System.out.println("删除节点3");binaryTree.delNo(3);System.out.println("删除节点");binaryTree.preOrder();/***前序遍历*HeroNode{no=1,name=宋江}*HeroNode{no=2,name=吴勇}*HeroNode{no=3,name=卢俊义}*HeroNode{no=5,name=关胜}*HeroNode{no=4,name=林冲}*中序遍历*HeroNode{no=2,name=吴勇}*HeroNode{no=1,name=宋江}*HeroNode{no=5,name=关胜}*HeroNode{no=3,name=卢俊义}*HeroNode{no=4,name=林冲}*后续遍历*HeroNode{no=2,name=Wu勇}*HeroNode{no=5,name=关胜}*HeroNode{no=4,name=林冲}*HeroNode{no=3,name=卢俊义}*HeroNode{no=1,name=宋江}*前序遍历查找~~*找到，信息为no=5，name=关胜*遍历次数：4*中序遍历查找~~*找到，信息为no=5，name=关胜*遍历次数：3*后序遍历查找~~*找到，信息为no=5,name=关胜*遍历次数：2*删除节点3*删除节点*HeroNode{no=1,name=松江}*HeroNode{no=2,name=WuYong}*/}}classBinaryTree{privateHeroNoderoot;publicvoidsetRoot(HeroNoderoot){this.root=root;}//前序遍历publicvoidpreOrder(){if(this.root!=null){this.root.preOrder();}}//中序遍历publicvoidinfixOrder(){if(this.root!=null){this.root.infixOrder();}}//删除节点publicvoiddelNo(intno){if(this.root!=null){if(this.root.getNo()==no){this.root=null;}else{this.root.delNo(no);}}return;}//后序遍历publicvoidpostOrder(){if(this.root!=null){this.root.postOrder();}}//前序遍历查找publicHeroNodepreOrderSearch(intno){if(root!=null){returnroot.preOrderSearch(no);}else{returnnull;}}//中序遍历找到publicHeroNodeinfixOrderSearch(intno){if(root!=null){returnroot.infixOrderSearch(no);}else{returnnull;}}//后序遍历搜索publicHeroNodepostOrderSearch(intno){if(root!=null){returnroot.postOrderSearch(no);}else{returnnull;}}}classHeroNode{staticintpreCount=0;staticintinfoxCount=0;staticintpostCount=0;privateintno;privateStringname;privateHeroNodeleft;privateHeroNoderight;publicHeroNode(intno,Stringname){this.no=no;this.name=name;}publicintgetNo(){returnno;}publicvoidsetNo(intno){this.no=no;}publicStringgetName(){returnname;}publicvoidsetName(Stringname){this.name=name;}publicHeroNodegetLeft(){returnleft;}publicvoidsetLeft(HeroNodeleft){this.left=left;}publicHeroNodegetRight(){returnright;}publicvoidsetRight(HeroNoderight){this.right=right;}@OverridepublicStringtoString(){return"HeroNode{"+"no="+no+",name="+name+'}';}//前序遍历publicvoidpreOrder(){System.out.println(this);//前序递归遍历左子树if(this.left!=null){this.left.preOrder();}//递归去右子树前Ordertraversalif(this.right!=null){this.right.preOrder();}}//中序遍历publicvoidinfixOrder(){//递归中序遍历到左子树if(this.left!=null){this.left.infixOrder();}System.out.println(this);//递归到右子树中序遍历if(this.right!=null){this.right.infixOrder();}}//后序遍历publicvoidpostOrder(){//递归左子树后序遍历if(this.left!=null){this.left.postOrder();}//递归后序遍历右子树if(this.right!=null){this.right.postOrder();}System.out.println(this);}//递归删除节点//1.如果删除的节点是叶节点，则删除该节点//2。如果删除的节点是非叶节点，则删除树。publicvoiddelNo(intno){/***1.因为我们的二叉树是单向的，我们判断当前节点的子节点是否是需要删除的节点，但是无法判断当前节点是否是需要删除的节点。*2.如果当前节点的左子节点不为空，且左子节点为要删除的节点，则设置this.left=null；并返回（结束递归）。*3.如果当前节点的右子节点不为空，且右子节点为要删除的节点，则设置this.right=null；并返回（结束递归）。*4.如果在第2步和第3步中没有删除该节点，则需要递归删除左子树。*5.如果第4步没有删除该节点，则递归删除到右子树。*/if(this.left!=null&&this.left.no==no){this.left=null;return;}if(this.right!=null&&this.right.no==no){this.right=null;return;}if(this.left!=null){this.left.delNo(no);}if(this.right!=null){this.right.delNo(no);}}//前序遍历查找publicHeroNodepreOrderSearch(intno){HeroNoderes=null;preCount++;//这个必须放在this之前。no==实际比较前不判断//找到则返回if(this.no==no){returnthis;}//不是找到，递归对左子树进行前序搜索if(this.left!=null){res=this.left.preOrderSearch(no);}//如果res!=null,直接返回if(res!=null){returnres;}//如果左子树没有搜索到，则按前序搜索右子树if(this.right!=null){res=this.right.preOrderSearch(no);}//找到则返回){res=this.left.infixOrderSearch(no);}if(res!=null){returnres;}infoxCount++;//必须放在this之前.no==在实际比较之前没有判断if(this.no==no){returnthis;}if(this.right!=null){res=this.right.infixOrderSearch(no);}if(res!=null){returnres;}returnres;}//后序遍历查找publicHeroNodepostOrderSearch(intno){HeroNoderes=null;if(this.left!=null){res=this.left.postOrderSearch(no);}if(res!=null){returnres;}if(this.right!=null){res=this.right.postOrderSearch(no);}if(res!=null){returnres;}postCount++;//这个必须放在this.no之前==实际比较前不判断if(this.no==no){returnthis;}returnres;}}【小编推荐】5分钟让你理解K8S必备架构和网络模型的概念。1992年，百度程序员被捕。我们有什么警告？开源云盘工具：Nextcloud21私有云盘构建更纯粹，微软Windows1021H2大更新将减少系统臃肿软件数量996操作系统是好是坏？
