087-089 哈希表

087 哈希表实现思路图解

基本介绍： 哈希表的基本介绍（Hash table，也叫哈希表），是根据关键码值（key value）而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

088-089 哈希表代码实现1-2

package com.old.hashTable_087_089; import java.util.Random; import java.util.Scanner; public class HashTableDemo { public static void main(String[] args) { //创建哈希表 HashTable hashTable = new HashTable(7); int size = hashTable.getSize(); int count = size * 2; Random random = new Random(count); for (int i = 0; i < size; i++) { int id = random.nextInt(); hashTable.add(new Emp(id, id + "号")); } //写一个简单菜单 String key = ""; Scanner scanner = new Scanner(System.in); boolean flag = true; while (flag) { System.out.println("1.添加"); System.out.println("2.显示"); System.out.println("3.退出"); key = scanner.nextLine(); try { switch (key) { case "1": System.out.println("输入id"); int id = scanner.nextInt(); System.out.println("输入名称"); String name = scanner.next(); Emp emp = new Emp(id, name); hashTable.add(emp); break; case "2": hashTable.list(); break; case "3": flag = false; break; case "4": System.out.println("输入要查找的id"); id = scanner.nextInt(); hashTable.findEmpById(id); break; } key = null; System.out.println(); } catch (Exception e) { e.printStackTrace(); } } scanner.close(); } } /** * 创建 HashTable 管理多条链表 */ class HashTable { private EmpLinkedList[] empLinkedListArray; private int size; public int getSize() { return size; } /** * 构造器 */ public HashTable(int size) { this.size = size; empLinkedListArray = new EmpLinkedList[size]; for (int i = 0; i < size; i++) { empLinkedListArray[i] = new EmpLinkedList(); } } /** * 添加雇员 */ public void add(Emp emp) { //根据员工的 id ， 得到该员工应当添加到哪条链表 int empLinkedListNO = hashFun(emp.id); EmpLinkedList empLinkedList = empLinkedListArray[empLinkedListNO]; empLinkedList.add(emp); } /** * 遍历所有的链表，遍历哈希表 */ public void list() { for (int i = 0; i < empLinkedListArray.length; i++) { empLinkedListArray[i].list( i + 1); } } /** * */ public void findEmpById(int id){ //使用散列函数确定到哪条链表 int empLinkedListNO = hashFun(id); Emp emp = empLinkedListArray[empLinkedListNO].findEmpById(id); System.out.println("第" + (empLinkedListNO + 1) + "条链表中找到: " + emp); } /** * 编写散列函数，使用一个简单取模法 * * @param id * @return */ public int hashFun(int id) { return id % size; } } class Emp { public int id; public String name; public Emp next; public Emp(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "Emp{" + "id=" + id + ", name='" + name + '\'' + '}'; } } //创建 EmpLinkedList ，表示链表 class EmpLinkedList { //头指针，执行第一个Emp，因此我们这个链表的 head，是直接指向第一个 Emp private Emp head; //默认是空的 /** * 添加员工 * 1. 假定，当添加雇员时，id 是自增长的，即id的分配问题从小到大 * 2. 因此我们将该雇员直接加入到本链表的最后即可 * * @param emp */ public void add(Emp emp) { //如果是添加第一个 if (head == null) { head = emp; return; } //如果不是第一个雇员，则使用一个辅助指针，帮助定位到最后 Emp curEmp = this.head; while (true) { //说明到链表最后 if (curEmp.next == null) { break; } //后移 curEmp = curEmp.next; } //退出时，直接将 emp 加入链表 curEmp.next = emp; } public void list(int no) { if (head == null) { //说明链表为空 System.out.println("链表为空"); return; } //辅助指针 Emp curEmp = head; while (true) { System.out.println("第" + no + "条链表，id:" + curEmp.id + "名称："+ curEmp.name); if (curEmp.next == null) { //说明已经是最后结点 break; } //后移，遍历 curEmp = curEmp.next; } System.out.println(); } /** * */ public void mylist() { if (head == null) { //说明链表为空 System.out.println("链表为空"); return; } for (Emp curEmp = head; curEmp != null; curEmp = curEmp.next) { System.out.println(curEmp); } } /** * my 是我写的 * * @param emp */ public void myAdd(Emp emp) { //如果是添加第一个 if (head == null) { head = emp; return; } //如果不是第一个雇员，则使用一个辅助指针，帮助定位到最后 Emp temp = this.head; while (temp != null) { temp = temp.next; } temp = emp; return; } public Emp findEmpById(int id){ if (head == null){ System.out.println("链表为空"); return null; } //辅助指针 Emp curEmp = head; while (true){ if (curEmp.id == id){ //找到 break; } //退出 if (curEmp.next == null){ //说明遍历当前链表没有找到该雇员，即退出 curEmp = null; } curEmp = curEmp.next; } return curEmp; } /** * 根据id查找雇员 * @param id * @return */ public Emp myFindEmpById(int id){ for (Emp curEmp = head; curEmp != null; curEmp = curEmp.next) { if (curEmp.id == id){ return curEmp; } } return null; } }

090-106 二叉树

090 数组、链表、树存储方式

二叉树

数组存储方式的分析 优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。 缺点：如果要检索某个值，或者插入传下（按一定顺序）会整体移动，效率较低

链式存储方式的分析 优点：在一定程度上对数组存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好） 缺点：在进行检索时，效率仍然较低，比如：检索某个值，需要从头节点开始遍历

树存储方式的分析 能提高数据存储，读取的效率，比如利用 **二叉排序树（Binary Sort Tree），既可以保证数据的检索速度，同时可以保证数据的插入，删除，修改的速度）

ArrayList 的底层操作机制源码分析

#＃ 091 二叉树的概念和常用术语 树的常用术语

节点根节点父节点子节点叶子节点（没有子节点的节点）节点的权（节点值）路径（从 root 节点找到该节点的路线）层子树树的高度（最大层度）森林：多颗子树构成森林

二叉树的概念

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树二叉树的子节点分为左节点和右节点如果该二叉树的的所有叶子节点都在最后一层，并且结点总数(这里的结点总数，是指所有的结点)=2ⁿ - 1 , n 为层数，则我们称为二叉树如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

092 前序中序后序遍历二叉树的图解

前序遍历：先输出父节点，再遍历左子树和右子树 中序遍历：先遍历左子树，再输出父节点，再遍历右子树 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点 小结：看输出父节点的顺序，就确定是前序、中序不是后序

图解

创建一棵二叉树前序遍历 先输出当前节点（初始的时候是root节点）如果左子节点不为空，则递归继续前序遍历如果右子节点不为空，则递归继续前序遍历 中序遍历 如果当前节点的左子节点不为空，则递归继续中序遍历先输出当前节点如果当前节点的右子节点不为空，则递归继续中序遍历 后序遍历 如果当前节点的左子节点不为空，则递归后序遍历如果当前节点的右子节点不为空，则递归后序遍历先输出当前节点

093-094 前序中序后序遍历代码实现

package com.old.Tree_90; 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); binaryTree.setRoot(root); System.out.println("前序遍历"); binaryTree.preOrder();//1,2,3,4 System.out.println(); System.out.println("中序遍历"); binaryTree.infixOrder();//2,1,3,4 System.out.println(); System.out.println("后序遍历"); binaryTree.postOrder();//2,4,3,1 System.out.println(); node3.setLeft(node5); System.out.println("前序遍历"); binaryTree.preOrder();//1,2,3,5,4 System.out.println(); System.out.println("中序遍历"); binaryTree.infixOrder();//2,1,5,3,4 System.out.println(); System.out.println("后序遍历"); binaryTree.postOrder();//2,5,4,3,1 System.out.println(); } } /** * 定义BinaryTree */ class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } public void preOrder() { if (this.root != null) { root.preOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void infixOrder() { if (this.root != null) { root.infixOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void postOrder() { if (this.root != null) { root.postOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } } /** * */ class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } public void setNo(int no) { this.no = no; } public void setName(String name) { this.name = name; } public void setLeft(HeroNode left) { this.left = left; } public void setRight(HeroNode right) { this.right = right; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } //前序遍历的方法 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); } }

095-097 前序中序后序查找

095 思路图解

前序、中序、后序的方式来查询指定的结点

前序查找

先判断当前结点的 no 是否等于要查找的相等，则返回当前结点如果不等于，则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找如果左递归前序查找，找到结点，则返回，否继续判断，当前的结点的右子节点是否为空，如果不空，则继续向右递归查找

中序查找

判断当前结点的左子节点是否为空，如果不为空，则递归中序查找如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点，否则继续进行右递归的中序查找如果右递归中序查找，找到就返回，否则返回null

后序查找

判断当前结点的左子节点是否为空，如果不为空，则递归后序查找如果找到，就返回，如果没有找到，就判断当前结点的右子节点是否为空，如果不为空，则右递归进行后序查找，如果找到，就返回就和当前结点进行，比如，如果是则返回，否则返回null

096-097 代码实现

package com.old.Tree_90; 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, "关胜"); HeroNode node6 = new HeroNode(5, "测试胜"); //先手动创建二叉树，后面以递归的方式创建二叉树 root.setLeft(node2); root.setRight(node3); node3.setRight(node4); binaryTree.setRoot(root); System.out.println("前序遍历"); binaryTree.preOrder();//1,2,3,4 System.out.println(); System.out.println("中序遍历"); binaryTree.infixOrder();//2,1,3,4 System.out.println(); System.out.println("后序遍历"); binaryTree.postOrder();//2,4,3,1 System.out.println(); node3.setLeft(node5); System.out.println("前序遍历"); binaryTree.preOrder();//1,2,3,5,4 System.out.println(); System.out.println("中序遍历"); binaryTree.infixOrder();//2,1,5,3,4 System.out.println(); System.out.println("后序遍历"); binaryTree.postOrder();//2,5,4,3,1 System.out.println(); /** * 要判断次数，要把输出语句写在判断no的地方，因为有地方只是进去 * 判断了是否为null */ int no = 2; System.out.println(binaryTree.myPreOrderSearch(no)); System.out.println(); System.out.println(binaryTree.preOrderSearch(no)); System.out.println(); System.out.println(binaryTree.infixOrderSearch(no)); System.out.println(); System.out.println(binaryTree.postOrderSearch(no)); System.out.println(); System.out.println("二分查找测试：" + binaryTree.mySearch(no)); } } /** * 定义BinaryTree */ class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } public void preOrder() { if (this.root != null) { root.preOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void infixOrder() { if (this.root != null) { root.infixOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void postOrder() { if (this.root != null) { root.postOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } /** * 我写的前序 * * @param no * @return */ public HeroNode myPreOrderSearch(int no) { if (root == null) { return null; } else { return root.myPreOrderSearch(no); } } /** * 我写的前序 * * @param no * @return */ public HeroNode mySearch(int no) { if (root == null) { return null; } else { return root.mySearch(no); } } /** * 前序 * * @param no * @return */ public HeroNode preOrderSearch(int no) { if (root == null) { return null; } else { return root.preOrderSearch(no); } } /** * 中序 * * @param no * @return */ public HeroNode infixOrderSearch(int no) { if (root == null) { return null; } else { return root.infixOrderSearch(no); } } /** * 后序 * * @param no * @return */ public HeroNode postOrderSearch(int no) { if (root == null) { return null; } else { return root.postOrderSearch(no); } } } /** * */ class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } public void setNo(int no) { this.no = no; } public void setName(String name) { this.name = name; } public void setLeft(HeroNode left) { this.left = left; } public void setRight(HeroNode right) { this.right = right; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } //前序遍历的方法 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); } /** * 前序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode myPreOrderSearch(int no) { System.out.println("我的前序遍历"); if (this.no == no) { return this; } HeroNode temp = null; if (this.left != null) { temp = this.left.myPreOrderSearch(no); } if (temp != null) { return temp; } if (this.right != null) { temp = this.right.myPreOrderSearch(no); } return temp; } /** * 前序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode preOrderSearch(int no) { System.out.println("前序遍历"); if (this.no == no) { return this; } /** * 则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.preOrderSearch(no); } if (repNode != null) { return repNode; } if (this.right != null) { repNode = this.right.preOrderSearch(no); } return repNode; } /** * 中序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode infixOrderSearch(int no) { /** * 判断当前结点的左子节点是否为空，如果不为空，则递归中序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.infixOrderSearch(no); } if (repNode != null) { return repNode; } /** * 如果找到，则返回，如果没有找到，就和当前结点比较， * 如果是则返回当前结点，否则继续进行右递归的中序查找 */ System.out.println("中序遍历"); if (this.no == no) { return this; } if (this.right != null) { repNode = this.right.infixOrderSearch(no); } return repNode; } /** * 后序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode postOrderSearch(int no) { /** * 判断当前结点的左子节点是否为空，如果不为空，则递归后序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.postOrderSearch(no); } if (repNode != null) { return repNode; } if (this.right != null) { repNode = this.right.postOrderSearch(no); } if (repNode != null) { return repNode; } System.out.println("后序遍历"); if (this.no == no) { return this; } return repNode; } public HeroNode mySearch(int no) { HeroNode temp = null; if (this.no < no && this.left != null) { temp = this.left.mySearch(no); } else if (this.no > no && this.right != null) { temp = this.right.mySearch(no); } else { return this; } return temp; } }

098-099 二叉树删除节点

要删除的节点是叶子节点，则删除该节点如果删除的节点是非叶子节点，则删除该子树测试删除掉5号叶子节点和3号子树

098 思路

思路: 目前先实现整个删除的效果，后续再实现更复杂的删除 是否是空树，如果只有一个 root 结点，则等价将二叉树置空

因为二叉树是单向的，所以是判断当前节点的子节点是否需要删除节点，而不能去判断当前这个节点是不是需要删除节点如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将 this.left = null; 并且就返回 （结束递归）如果当前节点的右子节点不为空， 并且右子节点就是要删除结点，就将 this.right = null; 并返回如果第二步和第三歩没有删除节点，就需要向左子树递归删除如果第4步也没有删除结点，则应当向右子树进行递归删除如果树是空root，如果只有一个 root 节点，则等价将二叉树置空

二叉树删除节点代码实现

package com.old.Tree_90; 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, "关胜"); HeroNode node6 = new HeroNode(5, "测试胜"); //先手动创建二叉树，后面以递归的方式创建二叉树 root.setLeft(node2); root.setRight(node3); node3.setRight(node4); binaryTree.setRoot(root); System.out.println("前序遍历"); binaryTree.preOrder();//1,2,3,4 System.out.println(); System.out.println("中序遍历"); binaryTree.infixOrder();//2,1,3,4 System.out.println(); System.out.println("后序遍历"); binaryTree.postOrder();//2,4,3,1 System.out.println(); node3.setLeft(node5); System.out.println("前序遍历"); binaryTree.preOrder();//1,2,3,5,4 System.out.println(); System.out.println("中序遍历"); binaryTree.infixOrder();//2,1,5,3,4 System.out.println(); System.out.println("后序遍历"); binaryTree.postOrder();//2,5,4,3,1 System.out.println(); /** * 要判断次数，要把输出语句写在判断no的地方，因为有地方只是进去 * 判断了是否为null */ int no = 2; System.out.println(binaryTree.myPreOrderSearch(no)); System.out.println(); System.out.println(binaryTree.preOrderSearch(no)); System.out.println(); System.out.println(binaryTree.infixOrderSearch(no)); System.out.println(); System.out.println(binaryTree.postOrderSearch(no)); System.out.println(); System.out.println("二分查找测试：" + binaryTree.mySearch(no)); System.out.println(); System.out.println("开始删除"); binaryTree.myRemove(5); binaryTree.myRemove(3); // binaryTree.delNode(5); // binaryTree.delNode(3); binaryTree.preOrder();//1,2,3,4 System.out.println(); } } /** * 定义BinaryTree */ class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } public void preOrder() { if (this.root != null) { root.preOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void infixOrder() { if (this.root != null) { root.infixOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void postOrder() { if (this.root != null) { root.postOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } /** * 我写的前序 * * @param no * @return */ public HeroNode myPreOrderSearch(int no) { if (root == null) { return null; } else { return root.myPreOrderSearch(no); } } /** * 我写的前序 * * @param no * @return */ public HeroNode mySearch(int no) { if (root == null) { return null; } else { return root.mySearch(no); } } /** * 我写的删除 * * @param no * @return */ public void myRemove(int no) { if (root == null) { return; } if (root.getNo() == no){ root = null; return; } root.myRemove(no); } /** * * * @param no * @return */ public void delNode(int no) { if (root == null) { return; } if (root.getNo() == no){ root = null; return; } root.delNode(no); } /** * 前序 * * @param no * @return */ public HeroNode preOrderSearch(int no) { if (root == null) { return null; } else { return root.preOrderSearch(no); } } /** * 中序 * * @param no * @return */ public HeroNode infixOrderSearch(int no) { if (root == null) { return null; } else { return root.infixOrderSearch(no); } } /** * 后序 * * @param no * @return */ public HeroNode postOrderSearch(int no) { if (root == null) { return null; } else { return root.postOrderSearch(no); } } } /** * */ class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; public HeroNode(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } public void setNo(int no) { this.no = no; } public void setName(String name) { this.name = name; } public void setLeft(HeroNode left) { this.left = left; } public void setRight(HeroNode right) { this.right = right; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } //前序遍历的方法 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); } /** * 前序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode myPreOrderSearch(int no) { System.out.println("我的前序遍历"); if (this.no == no) { return this; } HeroNode temp = null; if (this.left != null) { temp = this.left.myPreOrderSearch(no); } if (temp != null) { return temp; } if (this.right != null) { temp = this.right.myPreOrderSearch(no); } return temp; } /** * 前序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode preOrderSearch(int no) { System.out.println("前序遍历"); if (this.no == no) { return this; } /** * 则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.preOrderSearch(no); } if (repNode != null) { return repNode; } if (this.right != null) { repNode = this.right.preOrderSearch(no); } return repNode; } /** * 中序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode infixOrderSearch(int no) { /** * 判断当前结点的左子节点是否为空，如果不为空，则递归中序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.infixOrderSearch(no); } if (repNode != null) { return repNode; } /** * 如果找到，则返回，如果没有找到，就和当前结点比较， * 如果是则返回当前结点，否则继续进行右递归的中序查找 */ System.out.println("中序遍历"); if (this.no == no) { return this; } if (this.right != null) { repNode = this.right.infixOrderSearch(no); } return repNode; } /** * 后序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode postOrderSearch(int no) { /** * 判断当前结点的左子节点是否为空，如果不为空，则递归后序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.postOrderSearch(no); } if (repNode != null) { return repNode; } if (this.right != null) { repNode = this.right.postOrderSearch(no); } if (repNode != null) { return repNode; } System.out.println("后序遍历"); if (this.no == no) { return this; } return repNode; } /** * 有问题 * @param no * @return */ public HeroNode mySearch(int no) { HeroNode temp = null; if (this.no < no && this.left != null) { temp = this.left.mySearch(no); } else if (this.no > no && this.right != null) { temp = this.right.mySearch(no); } else { return this; } return temp; } /** * 如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将 this.left = null; 并且就返回 （结束递归） * 如果当前节点的右子节点不为空， 并且右子节点就是要删除结点，就将 this.right = null; 并返回 * 如果第二步和第三歩没有删除节点，就需要向左子树递归删除 * 如果第4步也没有删除结点，则应当向右子树进行递归删除 * @param no */ public void delNode(int no){ //如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将 this.left = null; 并且就返回 （结束递归） if (this.left != null && left.no == no){ this.left = null; return; } //如果当前节点的右子节点不为空， 并且右子节点就是要删除结点，就将 this.right = null; 并返回 if (this.right != null && right.no == no){ this.right = null; return; } //如果第二步和第三歩没有删除节点，就需要向左子树递归删除 if (this.left != null){ this.left.delNode(no); } //如果第4步也没有删除结点，则应当向右子树进行递归删除 if (this.right != null){ this.right.delNode(no); } } /** *没有问题 * @param no */ public void myRemove(int no){ boolean leftFlag = this.left != null; if (leftFlag && this.left.no == no){ this.left = null; return; } boolean rightFlag = this.right != null; if (rightFlag && this.right.no == no){ this.right = null; return; } if (rightFlag) { this.left.myRemove(no); } if (rightFlag) { this.right.myRemove(no); } } }

100-101 顺序存储二叉树

100 思路解析

基本说明： 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，

概念

顺序二叉树只考虑完全二叉树第n个元素的左子节点为 2 * n + 1第n个元素的右子节点为 2 * n + 2第n个元素的父节点为 (n - 1) / 2 表示二叉树中的第几个元素（按0开始编号）

101 顺序存储二叉树代码实现

需求：给你一个数组{1,2,3,4,5,6,7} ，要求以二叉树遍历的方式进行遍历。前序遍历的结果应当为1,2,3,4,5,6,7

package com.old.Tree_90; public class ArrBinaryTreeDemo { public static void main(String[] gsg) { int[] arr = {1, 2, 3, 4, 5, 6, 7,}; ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr); arrBinaryTree.preOrder(); /** * 前序这个结果都是对的 * 1 * 2 * 4 * 5 * 3 * 6 * 7 */ System.out.println(); arrBinaryTree.infixOrder(); System.out.println(); arrBinaryTree.postOrder(); } } /** * 编写一个 ArrBinaryTree，实现顺序存储二叉树 */ class ArrBinaryTree { //存储数据结点的数组 private int[] arr; public ArrBinaryTree(int[] arr) { this.arr = arr; } /** * 重载，传0显得有些尴尬 */ public void preOrder() { preOrder(0); } /** * 重载，传0显得有些尴尬 */ public void infixOrder() { infixOrder(0); } /** * 重载，传0显得有些尴尬 */ public void postOrder() { postOrder(0); } /** * 编写方法，完成顺序存储二叉树的遍历 * * @param index 表示数组的下标 */ public void preOrder(int index) { //如果数组为空，或者arr.length = 0 if (arr == null || arr.length == 0) { System.out.println("数组为空，不能按照二叉树的遍历"); } //输出当前这个元素 System.out.println(arr[index]); //向左递归遍历 int leftIndex = 2 * index + 1; if (leftIndex < arr.length) { preOrder(leftIndex); } int rightIndex = 2 * index + 2; if (rightIndex < arr.length) { preOrder(rightIndex); } } /** * 中序排序 */ public void infixOrder(int index) { //如果数组为空，或者arr.length = 0 if (arr == null || arr.length == 0) { System.out.println("数组为空，不能按照二叉树的遍历"); } //向左递归遍历 int leftIndex = 2 * index + 1; if (leftIndex < arr.length) { infixOrder(leftIndex); } //输出当前这个元素 System.out.println(arr[index]); int rightIndex = 2 * index + 2; if (rightIndex < arr.length) { infixOrder(rightIndex); } } /** * 后序排序 */ public void postOrder(int index) { //如果数组为空，或者arr.length = 0 if (arr == null || arr.length == 0) { System.out.println("数组为空，不能按照二叉树的遍历"); } //向左递归遍历 int leftIndex = 2 * index + 1; if (leftIndex < arr.length) { postOrder(leftIndex); } int rightIndex = 2 * index + 2; if (rightIndex < arr.length) { postOrder(rightIndex); } //输出当前这个元素 System.out.println(arr[index]); } }

102-106 线索化二叉树

102-103 线索化二叉树的介绍与思路图解

顺序存储二叉树应用实例 八大排序算法中的堆排序，使用到顺序存储二叉树，

基本介绍

n个节点的二叉链表中含有 n + 1 公式 2n - (n - 1) = n + 1 个空指针域。利用二叉链表中的空指针域，存入指向节点在某种启程遍历次序下的前驱和后继节点的指针（这种附加的的绝佳称为“线索”）这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树[Threaded BinaryTree]。根据性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树、后序线索二叉树三种一个结点的前一个结点，称为前驱结点一个结点的后一个结点，称为后继节点

104-105 线索二叉树代码实现

package com.old.Tree_90.threadedBinaryTree104_105; public class ThreadedBrinaryTreeDemo { public static void main(String[] args) { //测试一把中序线索二叉树的功能 HeroNode root = new HeroNode(1, "tom"); HeroNode node2 = new HeroNode(3, "jack"); HeroNode node3 = new HeroNode(6, "smith"); HeroNode node4 = new HeroNode(8, "mary"); HeroNode node5 = new HeroNode(10, "king"); HeroNode node6 = new HeroNode(14, "dim"); //后面要递归创建 root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); //测试线索化 ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(); threadedBinaryTree.setRoot(root); threadedBinaryTree.threadedNodes(); //以10号结点测试 HeroNode leftNode = node5.getLeft(); System.out.println(leftNode); System.out.println(rightNode); } } /** * 定义BinaryTree，实现线索化功能的二叉树 */ class ThreadedBinaryTree { private HeroNode root; /** * 为了实现线索化，需要创建要给指向当前结点的前驱结点的指针 * 在递归进行线索化时，pre 问题保留前一个结点 */ private HeroNode pre; public void setRoot(HeroNode root) { this.root = root; } public void threadedNodes() { threadedNodes(root); } /** * 编写对二叉树进行中序索化的方法 * * @param node 就是当前需要线索化的结点 */ public void threadedNodes(HeroNode node) { if (node == null) { return; } // 先线索化左子树 threadedNodes(node.getLeft()); // 线索化当前结点 //处理当前结点的前驱结点 if (node.getLeft() == null) { //让当前结点的左指针，指向前驱结点 node.setLeft(pre); //修改当前结点的左指针的类型 node.setLeftType(Type.LEFT_PRECURSOR); } //处理后继结点 if (pre != null && pre.getRight() == null) { //让前驱结点的右指针指向当前结点 pre.setRight(node); //修改前驱结点的右指针类型 pre.setRightType(Type.RIGHT_SUCCESSOR); } //这行代码很重要，每处理一个结点后，让当前结点是下一个结点的前驱结点 pre = node; /** * 再线索化右子树 * 这里开始写错了， threadedNodes(node.getLeft()); * 导致栈溢出了，猜测，因为上面已经是将node 的 lfet 赋值了， * 形成了一个环状，导致最上面的 node == null 判断没有办法 * 实现 */ threadedNodes(node.getRight()); } public void preOrder() { if (this.root != null) { root.preOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void infixOrder() { if (this.root != null) { root.infixOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void postOrder() { if (this.root != null) { root.postOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } /** * 我写的前序 * * @param no * @return */ public HeroNode myPreOrderSearch(int no) { if (root == null) { return null; } else { return root.myPreOrderSearch(no); } } /** * 我写的前序 * * @param no * @return */ public HeroNode mySearch(int no) { if (root == null) { return null; } else { return root.mySearch(no); } } /** * 我写的删除 * * @param no * @return */ public void myRemove(int no) { if (root == null) { return; } if (root.getNo() == no) { root = null; return; } root.myRemove(no); } /** * @param no * @return */ public void delNode(int no) { if (root == null) { return; } if (root.getNo() == no) { root = null; return; } root.delNode(no); } /** * 前序 * * @param no * @return */ public HeroNode preOrderSearch(int no) { if (root == null) { return null; } else { return root.preOrderSearch(no); } } /** * 中序 * * @param no * @return */ public HeroNode infixOrderSearch(int no) { if (root == null) { return null; } else { return root.infixOrderSearch(no); } } /** * 后序 * * @param no * @return */ public HeroNode postOrderSearch(int no) { if (root == null) { return null; } else { return root.postOrderSearch(no); } } } /** * 创建 HeroNode */ class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; /** * 说明： * 1. 如果 leftType == 0 表示指向的是左子树，如果 1 则表示前驱结点 * 2. 如果 rightType == 0 表示指向的是右子树，如果 1 则表示后继结点 */ private int leftType; private int rightType; public HeroNode(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } public void setNo(int no) { this.no = no; } public void setName(String name) { this.name = name; } public void setLeft(HeroNode left) { this.left = left; } public void setRight(HeroNode right) { this.right = right; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } public int getLeftType() { return leftType; } public void setLeftType(int leftType) { this.leftType = leftType; } public int getRightType() { return rightType; } public void setRightType(int rightType) { this.rightType = rightType; } //前序遍历的方法 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); } /** * 前序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode myPreOrderSearch(int no) { System.out.println("我的前序遍历"); if (this.no == no) { return this; } HeroNode temp = null; if (this.left != null) { temp = this.left.myPreOrderSearch(no); } if (temp != null) { return temp; } if (this.right != null) { temp = this.right.myPreOrderSearch(no); } return temp; } /** * 前序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode preOrderSearch(int no) { System.out.println("前序遍历"); if (this.no == no) { return this; } /** * 则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.preOrderSearch(no); } if (repNode != null) { return repNode; } if (this.right != null) { repNode = this.right.preOrderSearch(no); } return repNode; } /** * 中序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode infixOrderSearch(int no) { /** * 判断当前结点的左子节点是否为空，如果不为空，则递归中序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.infixOrderSearch(no); } if (repNode != null) { return repNode; } /** * 如果找到，则返回，如果没有找到，就和当前结点比较， * 如果是则返回当前结点，否则继续进行右递归的中序查找 */ System.out.println("中序遍历"); if (this.no == no) { return this; } if (this.right != null) { repNode = this.right.infixOrderSearch(no); } return repNode; } /** * 后序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode postOrderSearch(int no) { /** * 判断当前结点的左子节点是否为空，如果不为空，则递归后序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.postOrderSearch(no); } if (repNode != null) { return repNode; } if (this.right != null) { repNode = this.right.postOrderSearch(no); } if (repNode != null) { return repNode; } System.out.println("后序遍历"); if (this.no == no) { return this; } return repNode; } /** * 有问题 * * @param no * @return */ public HeroNode mySearch(int no) { HeroNode temp = null; if (this.no < no && this.left != null) { temp = this.left.mySearch(no); } else if (this.no > no && this.right != null) { temp = this.right.mySearch(no); } else { return this; } return temp; } /** * 如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将 this.left = null; 并且就返回 （结束递归） * 如果当前节点的右子节点不为空， 并且右子节点就是要删除结点，就将 this.right = null; 并返回 * 如果第二步和第三歩没有删除节点，就需要向左子树递归删除 * 如果第4步也没有删除结点，则应当向右子树进行递归删除 * * @param no */ public void delNode(int no) { //如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将 this.left = null; 并且就返回 （结束递归） if (this.left != null && left.no == no) { this.left = null; return; } //如果当前节点的右子节点不为空， 并且右子节点就是要删除结点，就将 this.right = null; 并返回 if (this.right != null && right.no == no) { this.right = null; return; } //如果第二步和第三歩没有删除节点，就需要向左子树递归删除 if (this.left != null) { this.left.delNode(no); } //如果第4步也没有删除结点，则应当向右子树进行递归删除 if (this.right != null) { this.right.delNode(no); } } /** * 没有问题 * * @param no */ public void myRemove(int no) { boolean leftFlag = this.left != null; if (leftFlag && this.left.no == no) { this.left = null; return; } boolean rightFlag = this.right != null; if (rightFlag && this.right.no == no) { this.right = null; return; } if (rightFlag) { this.left.myRemove(no); } if (rightFlag) { this.right.myRemove(no); } } } /** * 1. 如果 leftType == 0 表示指向的是左子树，如果 1 则表示前驱结点 * 2. 如果 rightType == 0 表示指向的是右子树，如果 1 则表示后继结点 */ interface Type { int LEFT_TREE = 0; int LEFT_PRECURSOR = 1; int RIGHT_TREE = 0; int RIGHT_SUCCESSOR = 1; }

106 遍历线索化二叉树实现

说明： 对前面的中序线索化二叉树，进行遍历 分析：因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这里需要使用新的方式遍历线索化二叉树，各个节点可以通过线形方式遍历，因此无需递归方式，就提高了遍历的效率。遍历的次序应当和中序遍历保持一致

package com.old.Tree_90.threadedBinaryTree104_106; public class ThreadedBrinaryTreeDemo { public static void main(String[] args) { //测试一把中序线索二叉树的功能 HeroNode root = new HeroNode(1, "tom"); HeroNode node2 = new HeroNode(3, "jack"); HeroNode node3 = new HeroNode(6, "smith"); HeroNode node4 = new HeroNode(8, "mary"); HeroNode node5 = new HeroNode(10, "king"); HeroNode node6 = new HeroNode(14, "dim"); //后面要递归创建 root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); //测试线索化 ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(); threadedBinaryTree.setRoot(root); threadedBinaryTree.threadedNodes(); //以10号结点测试 HeroNode leftNode = node5.getLeft(); HeroNode rightNode = node5.getRight(); System.out.println(leftNode); System.out.println(rightNode); //当线索化中序二叉树后，不能使用原来的中序遍历方法 System.out.println("开始遍历"); threadedBinaryTree.threadList(); } } /** * 定义BinaryTree，实现线索化功能的二叉树 */ class ThreadedBinaryTree { private HeroNode root; /** * 为了实现线索化，需要创建要给指向当前结点的前驱结点的指针 * 在递归进行线索化时，pre 问题保留前一个结点 */ private HeroNode pre; public void setRoot(HeroNode root) { this.root = root; } public void threadList() { //定义变量，临时存储遍历的结点，从root开始 HeroNode node = root; while (node != null) { /** * 循环的找到 leftType == 1 的结点，第一个找到的就是 8 结点 * 后面随着遍历而变化，因为当 leftType == 1 时，说明该结点是按照 * 线索化处理后的有效结点 */ while (node.getLeftType() == Type.LEFT_TREE){ node = node.getLeft(); } //打印当前这个结点 System.out.println(node); //如果当前结点的右指针指向的是后继结点，就一直输出 while (node.getRightType() == Type.RIGHT_SUCCESSOR){ //获取当前结点的后继节点 node = node.getRight(); System.out.println(node); } //当上面的 while 循环结束后，就替换遍历的结点 node = node.getRight(); } } public void threadedNodes() { threadedNodes(root); } /** * 编写对二叉树进行中序索化的方法 * * @param node 就是当前需要线索化的结点 */ public void threadedNodes(HeroNode node) { if (node == null) { return; } // 先线索化左子树 threadedNodes(node.getLeft()); // 线索化当前结点 //处理当前结点的前驱结点 if (node.getLeft() == null) { //让当前结点的左指针，指向前驱结点 node.setLeft(pre); //修改当前结点的左指针的类型 node.setLeftType(Type.LEFT_PRECURSOR); } //处理后继结点 if (pre != null && pre.getRight() == null) { //让前驱结点的右指针指向当前结点 pre.setRight(node); //修改前驱结点的右指针类型 pre.setRightType(Type.RIGHT_SUCCESSOR); } //这行代码很重要，每处理一个结点后，让当前结点是下一个结点的前驱结点 pre = node; /** * 再线索化右子树 * 这里开始写错了， threadedNodes(node.getLeft()); * 导致栈溢出了，猜测，因为上面已经是将node 的 lfet 赋值了， * 形成了一个环状，导致最上面的 node == null 判断没有办法 * 实现 */ threadedNodes(node.getRight()); } public void preOrder() { if (this.root != null) { root.preOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void infixOrder() { if (this.root != null) { root.infixOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } public void postOrder() { if (this.root != null) { root.postOrder(); } else { System.out.println("二叉树为空，无法遍历"); } } /** * 我写的前序 * * @param no * @return */ public HeroNode myPreOrderSearch(int no) { if (root == null) { return null; } else { return root.myPreOrderSearch(no); } } /** * 我写的前序 * * @param no * @return */ public HeroNode mySearch(int no) { if (root == null) { return null; } else { return root.mySearch(no); } } /** * 我写的删除 * * @param no * @return */ public void myRemove(int no) { if (root == null) { return; } if (root.getNo() == no) { root = null; return; } root.myRemove(no); } /** * @param no * @return */ public void delNode(int no) { if (root == null) { return; } if (root.getNo() == no) { root = null; return; } root.delNode(no); } /** * 前序 * * @param no * @return */ public HeroNode preOrderSearch(int no) { if (root == null) { return null; } else { return root.preOrderSearch(no); } } /** * 中序 * * @param no * @return */ public HeroNode infixOrderSearch(int no) { if (root == null) { return null; } else { return root.infixOrderSearch(no); } } /** * 后序 * * @param no * @return */ public HeroNode postOrderSearch(int no) { if (root == null) { return null; } else { return root.postOrderSearch(no); } } } /** * 创建 HeroNode */ class HeroNode { private int no; private String name; private HeroNode left; private HeroNode right; /** * 说明： * 1. 如果 leftType == 0 表示指向的是左子树，如果 1 则表示前驱结点 * 2. 如果 rightType == 0 表示指向的是右子树，如果 1 则表示后继结点 */ private int leftType; private int rightType; public HeroNode(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } public void setNo(int no) { this.no = no; } public void setName(String name) { this.name = name; } public void setLeft(HeroNode left) { this.left = left; } public void setRight(HeroNode right) { this.right = right; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } public int getLeftType() { return leftType; } public void setLeftType(int leftType) { this.leftType = leftType; } public int getRightType() { return rightType; } public void setRightType(int rightType) { this.rightType = rightType; } //前序遍历的方法 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); } /** * 前序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode myPreOrderSearch(int no) { System.out.println("我的前序遍历"); if (this.no == no) { return this; } HeroNode temp = null; if (this.left != null) { temp = this.left.myPreOrderSearch(no); } if (temp != null) { return temp; } if (this.right != null) { temp = this.right.myPreOrderSearch(no); } return temp; } /** * 前序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode preOrderSearch(int no) { System.out.println("前序遍历"); if (this.no == no) { return this; } /** * 则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.preOrderSearch(no); } if (repNode != null) { return repNode; } if (this.right != null) { repNode = this.right.preOrderSearch(no); } return repNode; } /** * 中序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode infixOrderSearch(int no) { /** * 判断当前结点的左子节点是否为空，如果不为空，则递归中序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.infixOrderSearch(no); } if (repNode != null) { return repNode; } /** * 如果找到，则返回，如果没有找到，就和当前结点比较， * 如果是则返回当前结点，否则继续进行右递归的中序查找 */ System.out.println("中序遍历"); if (this.no == no) { return this; } if (this.right != null) { repNode = this.right.infixOrderSearch(no); } return repNode; } /** * 后序遍历查找 * * @param no * @return 如果找到就返回该 node，如果没有找到返回 null */ public HeroNode postOrderSearch(int no) { /** * 判断当前结点的左子节点是否为空，如果不为空，则递归后序查找 */ HeroNode repNode = null; if (this.left != null) { repNode = this.left.postOrderSearch(no); } if (repNode != null) { return repNode; } if (this.right != null) { repNode = this.right.postOrderSearch(no); } if (repNode != null) { return repNode; } System.out.println("后序遍历"); if (this.no == no) { return this; } return repNode; } /** * 有问题 * * @param no * @return */ public HeroNode mySearch(int no) { HeroNode temp = null; if (this.no < no && this.left != null) { temp = this.left.mySearch(no); } else if (this.no > no && this.right != null) { temp = this.right.mySearch(no); } else { return this; } return temp; } /** * 如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将 this.left = null; 并且就返回 （结束递归） * 如果当前节点的右子节点不为空， 并且右子节点就是要删除结点，就将 this.right = null; 并返回 * 如果第二步和第三歩没有删除节点，就需要向左子树递归删除 * 如果第4步也没有删除结点，则应当向右子树进行递归删除 * * @param no */ public void delNode(int no) { //如果当前节点的左子节点不为空，并且左子节点就是要删除节点，就将 this.left = null; 并且就返回 （结束递归） if (this.left != null && left.no == no) { this.left = null; return; } //如果当前节点的右子节点不为空， 并且右子节点就是要删除结点，就将 this.right = null; 并返回 if (this.right != null && right.no == no) { this.right = null; return; } //如果第二步和第三歩没有删除节点，就需要向左子树递归删除 if (this.left != null) { this.left.delNode(no); } //如果第4步也没有删除结点，则应当向右子树进行递归删除 if (this.right != null) { this.right.delNode(no); } } /** * 没有问题 * * @param no */ public void myRemove(int no) { boolean leftFlag = this.left != null; if (leftFlag && this.left.no == no) { this.left = null; return; } boolean rightFlag = this.right != null; if (rightFlag && this.right.no == no) { this.right = null; return; } if (rightFlag) { this.left.myRemove(no); } if (rightFlag) { this.right.myRemove(no); } } } /** * 1. 如果 leftType == 0 表示指向的是左子树，如果 1 则表示前驱结点 * 2. 如果 rightType == 0 表示指向的是右子树，如果 1 则表示后继结点 */ interface Type { int LEFT_TREE = 0; int LEFT_PRECURSOR = 1; int RIGHT_TREE = 0; int RIGHT_SUCCESSOR = 1; }