第 10 章 树结构的基础部分
1、二叉树
1.1、为什么需要二叉树
1.1.1、数组存储方式的分析
- 优点： 通过下标方式访问元素， 速度快。 对于有序数组， 还可使用二分查找提高检索速度
- 缺点： 如果要检索具体某个值， 或者插入值(按一定顺序)会整体移动，效率较低
1.1.2、链式存储方式的分析
- 优点： 在一定程度上对数组存储方式有优化(比如： 插入一个数值节点， 只需要将插入节点， 链接到链表中即可，删除效率也很好)。
- 缺点： 在进行检索时， 效率仍然较低， 比如(检索某个值， 需要从头节点开始遍历)
1.1.3、树存储方式的分析
- 能提高数据存储， 读取的效率, 比如利用 二叉排序树(Binary Sort Tree)， 既可以保证数据的检索速度， 同时也可以保证数据的插入， 删除， 修改的速度。 【示意图，后面详讲】
1.2、树的常用术语
- 节点
- 根节点
- 父节点
- 子节点
- 叶子节点 (没有子节点的节点)
- 节点的权(节点值)
- 路径(从 root 节点找到该节点的路线)
- 层
- 子树
- 树的高度(最大层数)
- 森林 :多颗子树构成森林
1.3、二叉树的概念
- 树有很多种， 每个节点最多只能有两个子节点的一种形式称为二叉树，二叉树的子节点分为左节点和右节点
- 如果该二叉树的所有叶子节点都在最后一层， 并且结点总数= 2^n -1， n 为层数， 则我们称为满二叉树
- 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层， 而且最后一层的叶子节点在左边连续， 倒数第二层的叶子节点在右边连续， 我们称为完全二叉树
1.4、二叉树的遍历
1.4.1、代码思路
- 前序遍历:先输出父节点， 再遍历左子树和右子树
- 中序遍历: 先遍历左子树，再输出父节点， 再遍历右子树
- 后序遍历: 先遍历左子树， 再遍历右子树， 最后输出父节点
1.4.2、前 中 后序遍历
- 定义二叉树节点
//先创建 HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; // 默认null private HeroNode right; // 默认null 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); } }
- 定义二叉树：二叉树需要一个根节点 root 作为整个树的入口
//定义 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("二叉树为空，无法遍历"); } } }
1.4.3、代码测试
- 测试代码
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("前序遍历"); // 1,2,3,5,4 binaryTree.preOrder(); // 测试 System.out.println("中序遍历"); binaryTree.infixOrder(); // 2,1,5,3,4 System.out.println("后序遍历"); binaryTree.postOrder(); // 2,5,4,3,1 }
- 程序运行结果
前序遍历 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=宋江]
1.4.4、总结
- 看输出父节点的顺序， 就确定是前序， 中序还是后序
- 前序遍历递归图解
- 中序遍历递归图解
- 后序遍历递归图解
1.5、二叉树的查找
1.5.1、代码思路
- 将二叉树的前、中、后序遍历改为查找即可
- 编码思路：
- 如果查找到目标节点，直接返回，结束递归
- 如果找不到，继续递归执行前（中、后）序查找
1.5.2、前 中 后序查找
- 定义二叉树节点
//先创建 HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; // 默认null private HeroNode right; // 默认null 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 HeroNode preOrderSearch(int no) { // 比较当前结点是不是 if (this.no == no) { return this; } // 1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找 // 2.如果左递归前序查找，找到结点，则返回 HeroNode resNode = null; if (this.left != null) { resNode = this.left.preOrderSearch(no); } if (resNode != null) {// 说明我们左子树找到 return resNode; } // 1.左递归前序查找，找到结点，则返回，否继续判断， // 2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找 if (this.right != null) { resNode = this.right.preOrderSearch(no); } return resNode; } // 中序遍历查找 public HeroNode infixOrderSearch(int no) { // 判断当前结点的左子节点是否为空，如果不为空，则递归中序查找 HeroNode resNode = null; if (this.left != null) { resNode = this.left.infixOrderSearch(no); } if (resNode != null) { return resNode; } // 如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点 if (this.no == no) { return this; } // 否则继续进行右递归的中序查找 if (this.right != null) { resNode = this.right.infixOrderSearch(no); } return resNode; } // 后序遍历查找 public HeroNode postOrderSearch(int no) { // 判断当前结点的左子节点是否为空，如果不为空，则递归后序查找 HeroNode resNode = null; if (this.left != null) { resNode = this.left.postOrderSearch(no); } if (resNode != null) {// 说明在左子树找到 return resNode; } // 如果左子树没有找到，则向右子树递归进行后序遍历查找 if (this.right != null) { resNode = this.right.postOrderSearch(no); } if (resNode != null) { return resNode; } // 如果左右子树都没有找到，就比较当前结点是不是 if (this.no == no) { return this; } return resNode; } }
- 定义二叉树：二叉树需要一个根节点 root 作为整个树的入口
//定义 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("空树，不能删除~"); } } // 前序遍历查找 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 this.root.postOrderSearch(no); } else { return null; } } }
1.5.3、测试代码
- 测试代码：测试前序、中序、后序查找
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("前序遍历方式~~~"); HeroNode resNode = binaryTree.preOrderSearch(4); if (resNode != null) { System.out.printf("找到了，信息为 no=%d name=%s\n", resNode.getNo(), resNode.getName()); } else { System.out.printf("没有找到 no = %d 的英雄\n", 4); } System.out.println(); // 中序遍历查找 System.out.println("中序遍历方式~~~"); resNode = binaryTree.infixOrderSearch(5); if (resNode != null) { System.out.printf("找到了，信息为 no=%d name=%s\n", resNode.getNo(), resNode.getName()); } else { System.out.printf("没有找到 no = %d 的英雄\n", 5); } System.out.println(); // 后序遍历查找 System.out.println("后序遍历方式~~~"); resNode = binaryTree.postOrderSearch(6); if (resNode != null) { System.out.printf("找到了，信息为 no=%d name=%s\n", resNode.getNo(), resNode.getName()); } else { System.out.printf("没有找到 no = %d 的英雄\n", 6); } System.out.println(); }
- 程序运行结果
前序遍历方式~~~ 找到了，信息为 no=4 name=林冲 中序遍历方式~~~ 找到了，信息为 no=5 name=关胜 后序遍历方式~~~ 没有找到 no = 6 的英雄
1.6、二叉树的删除
1.6.1、二叉树删除的要求
- 如果删除的节点是叶子节点， 则删除该节点
- 如果删除的节点是非叶子节点， 则删除该子树
1.6.2、代码思路
- 由于树的本质还是单向链表：
- 单向链表无法实现自删除，我们需要定位至待删除节点的前一个节点，才能执行删除
- 同样，如果我们直接定位至二叉树中待删除的节点，那么其父节点信息便会丢失，所以我们一定要定位至待删除节点的父节点
编码思路：
先判断根节点 root 是不是待删除的节点，如果是，则删除根节点，否则开始执行递归
判断当前节点（this）的左节点是否为待删除的节点，如果是，删除 this.left ，然后返回，结束递归
判断当前节点（this）的左节点是否为待删除的节点，如果是，删除 this.right，然后返回，结束递归
否则继续执行左递归，左递归执行完后，执行右递归
1.6.3、二叉树的递归删除
- 定义二叉树节点
//先创建 HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; // 默认null private HeroNode right; // 默认null 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 + "]"; } // 递归删除结点 // 1.如果删除的节点是叶子节点，则删除该节点 // 2.如果删除的节点是非叶子节点，则删除该子树 public void delNode(int no) { // 思路 /* * 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点. * 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) * 3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) * 4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除 5. 如果第4步也没有删除结点，则应当向右子树进行递归删除. * */ // 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) if (this.left != null && this.left.no == no) { this.left = null; return; } // 3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) if (this.right != null && this.right.no == no) { this.right = null; return; } // 4.我们就需要向左子树进行递归删除 if (this.left != null) { this.left.delNode(no); } // 5.则应当向右子树进行递归删除 if (this.right != null) { this.right.delNode(no); } } }
- 定义二叉树：二叉树需要一个根节点 root 作为整个树的入口
1.6.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 [no=1, name=宋江] HeroNode [no=2, name=吴用] HeroNode [no=3, name=卢俊义] HeroNode [no=5, name=关胜] HeroNode [no=4, name=林冲] 删除节点 5 后，前序遍历 HeroNode [no=1, name=宋江] HeroNode [no=2, name=吴用] HeroNode [no=3, name=卢俊义] HeroNode [no=4, name=林冲] 删除子树 3 后，前序遍历 HeroNode [no=1, name=宋江] HeroNode [no=2, name=吴用]
1.7、二叉树的全部代码
- 叶子节点的定义
//先创建 HeroNode 结点 class HeroNode { private int no; private String name; private HeroNode left; // 默认null private HeroNode right; // 默认null 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); } // 前序遍历查找 public HeroNode preOrderSearch(int no) { // 比较当前结点是不是 if (this.no == no) { return this; } // 1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找 // 2.如果左递归前序查找，找到结点，则返回 HeroNode resNode = null; if (this.left != null) { resNode = this.left.preOrderSearch(no); } if (resNode != null) {// 说明我们左子树找到 return resNode; } // 1.左递归前序查找，找到结点，则返回，否继续判断， // 2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找 if (this.right != null) { resNode = this.right.preOrderSearch(no); } return resNode; } // 中序遍历查找 public HeroNode infixOrderSearch(int no) { // 判断当前结点的左子节点是否为空，如果不为空，则递归中序查找 HeroNode resNode = null; if (this.left != null) { resNode = this.left.infixOrderSearch(no); } if (resNode != null) { return resNode; } // 如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点 if (this.no == no) { return this; } // 否则继续进行右递归的中序查找 if (this.right != null) { resNode = this.right.infixOrderSearch(no); } return resNode; } // 后序遍历查找 public HeroNode postOrderSearch(int no) { // 判断当前结点的左子节点是否为空，如果不为空，则递归后序查找 HeroNode resNode = null; if (this.left != null) { resNode = this.left.postOrderSearch(no); } if (resNode != null) {// 说明在左子树找到 return resNode; } // 如果左子树没有找到，则向右子树递归进行后序遍历查找 if (this.right != null) { resNode = this.right.postOrderSearch(no); } if (resNode != null) { return resNode; } // 如果左右子树都没有找到，就比较当前结点是不是 if (this.no == no) { return this; } return resNode; } // 递归删除结点 // 1.如果删除的节点是叶子节点，则删除该节点 // 2.如果删除的节点是非叶子节点，则删除该子树 public void delNode(int no) { // 思路 /* * 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点. 2. * 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) 3. * 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) 4. * 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除 5. 如果第4步也没有删除结点，则应当向右子树进行递归删除. * */ // 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除) if (this.left != null && this.left.no == no) { this.left = null; return; } // 3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除) if (this.right != null && this.right.no == no) { this.right = null; return; } // 4.我们就需要向左子树进行递归删除 if (this.left != null) { this.left.delNode(no); } // 5.则应当向右子树进行递归删除 if (this.right != null) { this.right.delNode(no); } } }
- 二叉树的定义
//定义 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("二叉树为空，无法遍历"); } } // 前序遍历查找 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 this.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("空树，不能删除~"); } } }
1.8、课后练习
如果要删除的节点是非叶子节点， 现在我们不希望将该非叶子节点为根节点的子树删除， 需要指定规则, 假如规定如下:
如果该非叶子节点 A 只有一个子节点 B， 则子节点 B 替代节点 A
如果该非叶子节点 A 有左子节点 B 和右子节点 C， 则让左子节点 B 替代节点 A。
请大家思考， 如何完成该删除功能，后面在讲解二叉排序树时， 在给大家讲解具体的删除方法
