树结构基础部分

二叉树

为什么需要树这种数据结构

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

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

树存储方式的分析 ① 能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。 案例：[7,3,10,1,5,9,12]

树的示意图

二叉树的概念

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

二叉树遍历说明使用前序，中序和后序对下面的二叉树进行遍历.

二叉树遍历应用实例（前序、中序、后序）

应用实例的思路和说明

代码

package 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); binaryTree.setRoot(root); // 测试 System.out.println("前序遍历测试"); // 1,2,3,4 binaryTree.preOrder(); System.out.println("中序遍历测试"); // 2,1,3,4 binaryTree.infixOrder(); System.out.println("后序遍历测试"); // 2,4,3,1 binaryTree.postOrder(); // 3号添加左节点 node3.setLeft(node5); System.out.println("前序遍历测试"); // 1,2,3,5,4 binaryTree.preOrder(); System.out.println("中序遍历测试"); // 2,1,5,3,4 binaryTree.infixOrder(); System.out.println("后序遍历测试"); // 2,5,4,3,1 binaryTree.postOrder(); } } // 定义一个BinaryTree 二叉树 class BinaryTree{ private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } // 前序遍历 public void preOrder(){ if(this.root != null){ this.root.preOrder(); }else{ System.out.println("二叉树为空，无法遍历！"); } } // 中序遍历 public void infixOrder(){ if(this.root != null){ this.root.infixOrder(); }else{ System.out.println("二叉树为空，无法遍历！"); } } public void postOrder(){ if(this.root != null){ this.root.postOrder(); }else{ System.out.println("二叉树为空，无法遍历！"); } } } // 先创建HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; // 默认null private HeroNode right; // 默认null public HeroNode(int no, String name) { super(); this.no = no; this.name = name; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } 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; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } // 编写前序遍历方法 public void preOrder() { System.out.println(this.toString()); // 先输出父节点 // 递归向左子树前序遍历 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.toString()); // 递归向右子树中序遍历 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.toString()); } }

二叉树-查找指定节点

要求

请编写前序查找，中序查找和后序查找的方法。并分别使用三种查找方式，查找 heroNO = 5 的节点并分析各种查找方式，分别比较了多少次思路图解分析

代码

package 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); binaryTree.setRoot(root); // 查询测试 node3.setLeft(node5); // 前序遍历查询： // 遍历次数：4 System.out.println("前序遍历查询"); HeroNode preResultNode = binaryTree.preOrderSearch(5); if(preResultNode != null){ System.out.printf("找到了,信息为 : no = %d name = %s\n",preResultNode.getNo(),preResultNode.getName()); }else{ System.out.printf("没有找到编号为 %d 的英雄",5); } // 中序遍历查询： // 遍历次数：3 System.out.println("中序遍历查询"); HeroNode infixResultNode = binaryTree.infixOrderSearch(5); if(preResultNode != null){ System.out.printf("找到了,信息为 : no = %d name = %s\n",preResultNode.getNo(),preResultNode.getName()); }else{ System.out.printf("没有找到编号为 %d 的英雄",5); } // 后序遍历查询： // 遍历次数：2 System.out.println("后序遍历查询"); HeroNode postResultNode = binaryTree.postOrderSearch(5); if(preResultNode != null){ System.out.printf("找到了,信息为 : no = %d name = %s\n",preResultNode.getNo(),preResultNode.getName()); }else{ System.out.printf("没有找到编号为 %d 的英雄",5); } } } // 定义一个BinaryTree 二叉树 class BinaryTree{ private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } // 前序遍历查询 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; } } } // 先创建HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; // 默认null private HeroNode right; // 默认null public HeroNode(int no, String name) { super(); this.no = no; this.name = name; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } 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; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } // 前序遍历查找 public HeroNode preOrderSearch(int no){ // 比较当前节点是不是 if(this.no == no){ return this; } // 1. 判断当前结点左子节点是否为空，如果不为空，递归前序查找 // 2. 如果左递归前序查找，找到结点，则返回 HeroNode resultNode = null; if(this.left != null){ resultNode = this.left.preOrderSearch(no); } if(resultNode != null){ // 说明在左子树找到结果 return resultNode; } // 3. 否则继续判断，咋判断当前结点的右子节点是否为空，如果不空，继续向右递归前序查找 if(this.right != null){ resultNode = this.right.preOrderSearch(no); } return resultNode; } // 中序遍历查找 public HeroNode infixOrderSearch(int no){ HeroNode resultNode = null; if(this.left != null){ resultNode = this.left.infixOrderSearch(no); } if(resultNode != null){ return resultNode; } if(this.no == no){ return this; } if(this.right != null){ resultNode = this.right.infixOrderSearch(no); } return resultNode; } // 后序遍历查找 public HeroNode postOrderSearch(int no){ HeroNode resultNode = null; if(this.left != null){ resultNode = this.left.postOrderSearch(no); } if(resultNode != null){ return resultNode; } if(this.right != null){ resultNode = this.right.postOrderSearch(no); } if(resultNode != null){ return resultNode; } if(this.no == no){ resultNode = this; } return resultNode; } }

二叉树-删除节点

要求

如果删除的节点是叶子节点，则删除该节点如果删除的节点是非叶子节点，则删除该子树.测试，删除掉 5号叶子节点 和 3号子树.思路分析图解

代码

package 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); binaryTree.setRoot(root); /* // 遍历测试 System.out.println("前序遍历测试"); // 1,2,3,4 binaryTree.preOrder(); System.out.println("中序遍历测试"); // 2,1,3,4 binaryTree.infixOrder(); System.out.println("后序遍历测试"); // 2,4,3,1 binaryTree.postOrder(); // 3号添加左节点 node3.setLeft(node5); System.out.println("前序遍历测试"); // 1,2,3,5,4 binaryTree.preOrder(); System.out.println("中序遍历测试"); // 2,1,5,3,4 binaryTree.infixOrder(); System.out.println("后序遍历测试"); // 2,5,4,3,1 binaryTree.postOrder(); */ /* // 查询测试 node3.setLeft(node5); // 前序遍历查询： // 遍历次数：4 System.out.println("前序遍历查询"); HeroNode preResultNode = binaryTree.preOrderSearch(5); if (preResultNode != null) { System.out.printf("找到了,信息为 : no = %d name = %s\n", preResultNode.getNo(), preResultNode.getName()); } else { System.out.printf("没有找到编号为 %d 的英雄", 5); } // 中序遍历查询： // 遍历次数：3 System.out.println("中序遍历查询"); HeroNode infixResultNode = binaryTree.infixOrderSearch(5); if (preResultNode != null) { System.out.printf("找到了,信息为 : no = %d name = %s\n", preResultNode.getNo(), preResultNode.getName()); } else { System.out.printf("没有找到编号为 %d 的英雄", 5); } // 后序遍历查询： // 遍历次数：2 System.out.println("后序遍历查询"); HeroNode postResultNode = binaryTree.postOrderSearch(5); if (preResultNode != null) { System.out.printf("找到了,信息为 : no = %d name = %s\n", preResultNode.getNo(), preResultNode.getName()); } else { System.out.printf("没有找到编号为 %d 的英雄", 5); } */ // 删除测试 node3.setLeft(node5); System.out.println("删除前，前序遍历"); binaryTree.preOrder(); // 1,2,3,5,4 // binaryTree.delNode(5); binaryTree.delNode(3); System.out.println("删除后，前序遍历"); binaryTree.preOrder(); // 1,2,3,4 } } // 定义一个BinaryTree 二叉树 class BinaryTree { private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } // 删除节点 public void delNode(int no) { if (root != null) { // 如果只有一个root,这里立即判断root是否是需要删除的节点 if (root.getNo() == no) { root = null; } else { // 递归删除 root.delNode(no); } } else { System.out.println("空树，无法删除"); } } } // 先创建HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; // 默认null private HeroNode right; // 默认null public HeroNode(int no, String name) { super(); this.no = no; this.name = name; } public int getNo() { return no; } public String getName() { return name; } public HeroNode getLeft() { return left; } public HeroNode getRight() { return right; } 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; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } // 递归删除节点 // 暂时规定： // 1. 如果删除的节点是叶子节点，则删除该节点 // 2. 如果删除的节点是非叶子节点，则删除该子树 public void delNode(int no) { 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.delNode(no); } if (this.right != null) { this.right.delNode(no); } } }

顺序存储二叉树

顺序存储二叉树的概念

基本说明 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树也可以转换成数组，可看示意图。 要求: 图中的二叉树的结点，要求以数组的方式来存放 arr : [1, 2, 3, 4, 5, 6, 7] 要求在遍历数组 arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历顺序存储二叉树的特点: 顺序二叉树通常只考虑完全二叉树第n个元素的左子节点为 2 * n + 1第n个元素的右子节点为 2 * n + 2第n个元素的父节点为 (n-1) / 2n : 表示二叉树中的第几个元素(按0开始编号如图所示)

顺序存储二叉树遍历

需求: 给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为 1,2,4,5,3,6,7 课后练习：完成对数组以二叉树中序，后序遍历方式的代码.

代码

package tree; import java.util.ArrayList; public class ArrBinaryTreeDemo { public static void main(String[] args) { int[] arr = {1, 2, 3, 4, 5, 6, 7}; // 创建一个ArrayBinaryTree ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr); arrayBinaryTree.preOrder(); // 1,2,4,5,3,6,7 } } // 编写一个ArrayBinaryTree类 class ArrayBinaryTree { private int[] arr; // 存储数据节点的数组 public ArrayBinaryTree(int[] arr) { this.arr = arr; } // 重载preOrder public void preOrder(){ this.preOrder(0); } public void infixOrder(){ this.infixOrder(0); } public void postOrder(){ this.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]); // 向左递归遍历 if ((index) * 2 + 1 < arr.length) { preOrder(2 * index + 1); } if ((index) * 2 + 2 < arr.length) { preOrder(2 * index + 2); } } /** * @param index 数组下标 */ public void infixOrder(int index) { // 如果数组为空，或者arr.length() = 0 if (arr == null || arr.length == 0) { System.out.println("数组为空，不能按照二叉树的中序遍历"); } // 向左递归遍历 if ((index) * 2 + 1 < arr.length) { infixOrder(2 * index + 1); } // 输出当前元素 System.out.println(arr[index]); if ((index) * 2 + 2 < arr.length) { infixOrder(2 * index + 2); } } /** * @param index 数组下标 */ public void postOrder(int index) { // 如果数组为空，或者arr.length() = 0 if (arr == null || arr.length == 0) { System.out.println("数组为空，不能按照二叉树的后序遍历"); } // 向左递归遍历 if ((index) * 2 + 1 < arr.length) { postOrder(2 * index + 1); } // 输出当前元素 System.out.println(arr[index]); if ((index) * 2 + 2 < arr.length) { postOrder(2 * index + 2); } } }

顺序存储二叉树应用实例

八大排序算法中的堆排序，就会使用到顺序存储二叉树。

线索化二叉树

一个问题

将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7 问题分析：

当我们对上面的二叉树进行中序遍历时，数列为 {8, 3, 10, 1, 6, 14 }但是 6, 8, 10, 14 这几个节点的 左右指针，并没有完全的利用上.如果我们希望充分的利用 各个节点的左右指针， 让各个节点可以指向自己的前后节点,怎么办?解决方案-线索二叉树

线索二叉树基本介绍

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

应用案例说明：将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}

思路分析：

遍历线索化二叉树

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

代码

package tree.threadedbinarytree; public class ThreadedBinaryTreeDemo { 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.infixThreadedNodes(); // 测试：以node5为测试 // System.out.println(node4.getLeft()); // System.out.println(node5.getRight()); System.out.println("使用线索化的方式遍历线索化二叉树"); threadedBinaryTree.threadedList(); } } // 定义一个ThreadedBinaryTree 二叉树 class ThreadedBinaryTree { private tree.threadedbinarytree.HeroNode root; // 为了实现线索化，需要创建给要给指向当前结点的前驱节点的指针 // 在递归线索化的过程中，pre总是指向前一个节点 private HeroNode pre = null; public void setRoot(tree.threadedbinarytree.HeroNode root) { this.root = root; } // 遍历线索化二叉树方法 public void threadedList() { // 定义一个变量，存储当前遍历的结点，从root开始 HeroNode node = root; while (node != null) { // 循环找到leftType = 1的结点，第一个找到8的结点 // 后面随着遍历leftType变化，因为当leftType=1的时候，说明该节点是按照线索化处理后的有效节点 while (node.getLeftType() == 0) { node = node.getLeft(); } // 打印当前结点 System.out.println(node); // 如果当前结点右指针指向后继结点，就一直输出 while (node.getRightType() == 1) { // 获取到当前结点的后继节点 node = node.getRight(); System.out.println(node); } // 替换遍历的结点 node = node.getRight(); } } // 重载infixThreadedNodes public void infixThreadedNodes() { this.infixThreadedNodes(root); } /** * 编写对二叉树进行中序线索化的方法 * * @param node 就是当前需要线索化的结点 */ public void infixThreadedNodes(HeroNode node) { // 如果当前结点为空，不需要线索化 if (node == null) { return; } // 1）先线索化左子树 infixThreadedNodes(node.getLeft()); // 2）线索化当前结点 // ① 先处理当前结点前驱节点 if (node.getLeft() == null) { // 让当前结点的左指针指向前驱节点 node.setLeft(pre); // 修改当前结点的左指针的类型,指向前驱节点 node.setLeftType(1); } // ② 处理后继节点 if (pre != null && pre.getRight() == null) { // 让前驱结点的右指针指向当前结点 pre.setRight(node); // 修改前驱节点的右指针类型 pre.setRightType(1); } // ★★★★★★★★五角星每处理一个节点后，让当前结点称为下一个节点的前驱节点 pre = node; // 3）再线索化右子树 infixThreadedNodes(node.getRight()); } // 前序遍历 public void preOrder() { if (this.root != null) { this.root.preOrder(); } else { System.out.println("二叉树为空，无法遍历！"); } } // 中序遍历 public void infixOrder() { if (this.root != null) { this.root.infixOrder(); } else { System.out.println("二叉树为空，无法遍历！"); } } // 后序遍历 public void postOrder() { if (this.root != null) { this.root.postOrder(); } else { System.out.println("二叉树为空，无法遍历！"); } } // 前序遍历查询 public tree.threadedbinarytree.HeroNode preOrderSearch(int no) { if (root != null) { return root.preOrderSearch(no); } else { return null; } } // 中序遍历查询 public tree.threadedbinarytree.HeroNode infixOrderSearch(int no) { if (root != null) { return root.infixOrderSearch(no); } else { return null; } } // 后续遍历查询 public tree.threadedbinarytree.HeroNode postOrderSearch(int no) { if (root != null) { return root.postOrderSearch(no); } else { return null; } } // 删除节点 public void delNode(int no) { if (root != null) { // 如果只有一个root,这里立即判断root是否是需要删除的节点 if (root.getNo() == no) { root = null; } else { // 递归删除 root.delNode(no); } } else { System.out.println("空树，无法删除"); } } } class HeroNode { private int no; private String name; private tree.threadedbinarytree.HeroNode left; // 默认null private tree.threadedbinarytree.HeroNode right; // 默认null // 定义属性区分 // 说明： // 1. 如果leftType == 0 表示指向的是左子树 如果是1表示指向前驱节点 // 2. 如果rightType == 0 表示指向的是右子树 如果是1表示指向后继节点 private int leftType; private int rightType; public void setLeftType(int leftType) { this.leftType = leftType; } public void setRightType(int rightType) { this.rightType = rightType; } public int getLeftType() { return leftType; } public int getRightType() { return rightType; } public HeroNode(int no, String name) { super(); this.no = no; this.name = name; } public int getNo() { return no; } public String getName() { return name; } public tree.threadedbinarytree.HeroNode getLeft() { return left; } public tree.threadedbinarytree.HeroNode getRight() { return right; } public void setNo(int no) { this.no = no; } public void setName(String name) { this.name = name; } public void setLeft(tree.threadedbinarytree.HeroNode left) { this.left = left; } public void setRight(tree.threadedbinarytree.HeroNode right) { this.right = right; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } // 编写前序遍历方法 public void preOrder() { System.out.println(this.toString()); // 先输出父节点 // 递归向左子树前序遍历 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.toString()); // 递归向右子树中序遍历 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.toString()); } // 前序遍历查找 public tree.threadedbinarytree.HeroNode preOrderSearch(int no) { // 比较当前节点是不是 if (this.no == no) { return this; } // 1. 判断当前结点左子节点是否为空，如果不为空，递归前序查找 // 2. 如果左递归前序查找，找到结点，则返回 tree.threadedbinarytree.HeroNode resultNode = null; if (this.left != null) { resultNode = this.left.preOrderSearch(no); } if (resultNode != null) { // 说明在左子树找到结果 return resultNode; } // 3. 否则继续判断，咋判断当前结点的右子节点是否为空，如果不空，继续向右递归前序查找 if (this.right != null) { resultNode = this.right.preOrderSearch(no); } return resultNode; } // 中序遍历查找 public tree.threadedbinarytree.HeroNode infixOrderSearch(int no) { tree.threadedbinarytree.HeroNode resultNode = null; if (this.left != null) { resultNode = this.left.infixOrderSearch(no); } if (resultNode != null) { return resultNode; } if (this.no == no) { return this; } if (this.right != null) { resultNode = this.right.infixOrderSearch(no); } return resultNode; } // 后序遍历查找 public tree.threadedbinarytree.HeroNode postOrderSearch(int no) { tree.threadedbinarytree.HeroNode resultNode = null; if (this.left != null) { resultNode = this.left.postOrderSearch(no); } if (resultNode != null) { return resultNode; } if (this.right != null) { resultNode = this.right.postOrderSearch(no); } if (resultNode != null) { return resultNode; } if (this.no == no) { resultNode = this; } return resultNode; } // 递归删除节点 // 暂时规定： // 1. 如果删除的节点是叶子节点，则删除该节点 // 2. 如果删除的节点是非叶子节点，则删除该子树 public void delNode(int no) { 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.delNode(no); } if (this.right != null) { this.right.delNode(no); } } }