- 当前位置：首页 >IT科技 >Java编程内功-数据结构与算法「树」
Java编程内功-数据结构与算法「树」
发布时间：2025-11-03 10:20:18 来源：创站工坊 作者：应用开发
为什么需要树这种结构
1.数组存储方式分析：
优点：通过下标方式访问元素，编程速度快。内功对于有序数组，数据算法树还可以使用二分查找提高检索速度。结构 缺点：如果检索某个具体的编程值，或者插入值(按一定的内功顺序)会整体移动，效率较低。数据算法树2.链式存储方式分析：
优点：在一定程度上对数组存储方式优化(比如：插入一个数值节点，结构只需要将插入节点，编程链接到链表中即可，内功删除效率很高)。数据算法树 缺点：在进行检索时，结构效率仍然很低，编程需要从头结点开始遍历。内功3.树存储方式分析：能提高数据存储，数据算法树读取的效率，比如利用二叉排序树(Binary sort tree)，即可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。假设一组[7,3,10,1,5,9,12]以树的方式存储，分析如下图：
二叉树的前序遍历、中序遍历、后序遍历
前序遍历：输出父节点、输出左边节点、b2b供应网输出右边节点; 中序遍历：输出左边节点、输出父节点、输出右边节点; 后序遍历：输出左边节点、输出右边节点、输出父节点;需求案例
完成一个如下二叉树节点存储、前序遍历搜索、中序遍历搜索、后序遍历搜索和删除节点功能。
对于删除节点要求如下：
如果删除的节点是叶子节点，则删除该节点。 如果删除的节点是非叶子节点，则删除该树。 测试，删除5号叶子节点和3号子树。
代码案例
package com.xie.tree; public class BinaryTreeDemo { public static void main(String[] args) { BinaryTree binaryTree = new BinaryTree(); HeroNode root = new HeroNode(1, "宋江"); HeroNode node2 = new HeroNode(2, "吴用"); HeroNode node3 = new HeroNode(3, "卢俊义"); HeroNode node4 = new HeroNode(4, "林冲"); HeroNode node5 = new HeroNode(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("前序遍历查找~~"); HeroNode resultNode = binaryTree.preOrderSearch(5); if (resultNode != null) { System.out.printf("找到了，信息为no=%d,name=%sn", resultNode.getNo(), resultNode.getName()); System.out.println("遍历次数：" + HeroNode.preCount); } else { System.out.println("没有找到"); } //中序遍历查找 System.out.println("中序遍历查找~~"); HeroNode resultNode1 = binaryTree.infixOrderSearch(5); if (resultNode1 != null) { System.out.printf("找到了，信息为no=%d,name=%sn", resultNode1.getNo(), resultNode1.getName()); System.out.println("遍历次数：" + HeroNode.infoxCount); } else { System.out.println("没有找到"); } //后序遍历查找 System.out.println("后序遍历查找~~"); HeroNode resultNode2 = binaryTree.postOrderSearch(5); if (resultNode2 != null) { System.out.printf("找到了，信息为no=%d,name=%sn", 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=吴用} * 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=吴用} */ } } class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } //前序遍历 public void preOrder() { if (this.root != null) { this.root.preOrder(); } } //中序遍历 public void infixOrder() { if (this.root != null) { this.root.infixOrder(); } } //删除节点 public void delNo(int no) { if (this.root != null) { if (this.root.getNo() == no) { this.root = null; } else { this.root.delNo(no); } } return; } //后序遍历 public void postOrder() { if (this.root != null) { this.root.postOrder(); } } //前序遍历查找 public HeroNode preOrderSearch(int no) { if (root != null) { return root.preOrderSearch(no); } else { return null; } } //中序遍历查找 public HeroNode infixOrderSearch(int no) { if (root != null) { return root.infixOrderSearch(no); } else { return null; } } //后序遍历查找 public HeroNode postOrderSearch(int no) { if (root != null) { return root.postOrderSearch(no); } else { return null; } } } class HeroNode { static int preCount = 0; static int infoxCount = 0; static int postCount = 0; private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public HeroNode getLeft() { return left; } public void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } public void setRight(HeroNode right) { this.right = right; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name=" + name + }; } //前序遍历 public void preOrder() { System.out.println(this); //递归向左子树前序遍历 if (this.left != null) { this.left.preOrder(); } //递归向右子树前序遍历 if (this.right != null) { this.right.preOrder(); } } //中序遍历 public void infixOrder() { //递归向左子树中序遍历 if (this.left != null) { this.left.infixOrder(); } System.out.println(this); //递归向右子树中序遍历 if (this.right != null) { this.right.infixOrder(); } } //后序遍历 public void postOrder() { //递归向左子树后序遍历 if (this.left != null) { this.left.postOrder(); } //递归向右子树后序遍历 if (this.right != null) { this.right.postOrder(); } System.out.println(this); } //递归删除节点 //1.如果删除的节点是叶子节点，则删除该节点。 //2.如果删除的节点是免费信息发布网非叶子节点，则删除该树。 public void delNo(int no) { /** * 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); } } //前序遍历查找 public HeroNode preOrderSearch(int no) { HeroNode res = null; preCount++;//这里必须放在this.no == no 判断之前，亿华云才进行实际的比较 //若果找到，就返回 if (this.no == no) { return this; } //没有找到，向左子树递归进行前序查找 if (this.left != null) { res = this.left.preOrderSearch(no); } //如果res ！= null 就直接返回 if (res != null) { return res; } //如果左子树没有找打，向右子树进行前序查找 if (this.right != null) { res = this.right.preOrderSearch(no); } //如果找到就返回 if (res != null) { return res; } return res; } //中序遍历查找 public HeroNode infixOrderSearch(int no) { HeroNode res = null; if (this.left != null) { res = this.left.infixOrderSearch(no); } if (res != null) { return res; } infoxCount++;//这里必须放在this.no == no 判断之前，才进行实际的比较 if (this.no == no) { return this; } if (this.right != null) { res = this.right.infixOrderSearch(no); } if (res != null) { return res; } return res; } //后序遍历查找 public HeroNode postOrderSearch(int no) { HeroNode res = null; if (this.left != null) { res = this.left.postOrderSearch(no); } if (res != null) { return res; } if (this.right != null) { res = this.right.postOrderSearch(no); } if (res != null) { return res; } postCount++;//这里必须放在this.no == no 判断之前，才进行实际的比较 if (this.no == no) { return this; } return res; } }【编辑推荐】
5分钟让你理解K8S必备架构概念，以及网络模型 92年百度程序员被抓，给我们警示什么？ 开源云盘利器：Nextcloud 21私有云盘搭建 更纯净，微软 Windows10 21H2 重大更新将减少系统臃肿软件数量 996工作制究竟是好是坏？- 联想电脑开机出现关键错误的解决方案（排除联想电脑开机关键错误的方法及注意事项）
- 梦米手机，性价比之王（一部能满足你多方面需求的智能手机）
- 1MORE耳机的品质与表现（探索音乐新境界，畅享1MORE耳机的震撼声音）
- 小米运动拍照效果如何？（细腻逼真的画面，记录你的运动时刻）
- 探索iPhonePlus系列的魅力——以a1524的iPhone6Plus为例
- 赛德斯SA708（性能卓越、舒适豪华的驾驶体验）
- 宜丽客运动耳机如何？（解析宜丽客运动耳机的性能与功能）
- AMD641处理器（解析AMD641处理器的性能优势及适用领域）
- 用彩纸打造趣味电脑教程（彩纸DIY教程，让电脑知识更有趣）
- 以荣事达油汀怎么样？（探究荣事达油汀的性能和用户评价）
随便看看
源码库亿华云IT资讯网源码下载服务器租用益华科技IT技术网香港云服务器企商汇益强科技益强前沿资讯益华科技技术快报亿华智慧云益华IT技术论坛思维库创站工坊益强编程舍极客编程益强IT技术网多维IT资讯益强智囊团益强科技码上建站亿华云智能时代科技前瞻编程之道亿华云计算云智核全栈开发汇智坊亿华科技益强数据堂亿华灵动亿华智造云站无忧运维纵横益强资讯优选亿华互联益强智未来极客码头码力社
- Copyright © 2025 Powered by Java编程内功-数据结构与算法「树」,创站工坊 滇ICP备2023006006号-44sitemap