二叉树（链式存储）

二叉树（链式存储）

1、树数据结构与数组和链表的区别

1. 数组存储方式的分析

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

2. 链式存储方式的分析

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

   

3. 树存储方式的分析

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

   

2、树的示意图及常用术语

/*
树的常用术语(结合示意图理解):
1) 节点
2) 根节点
3) 父节点
4) 子节点
5) 叶子节点 (没有子节点的节点)
6) 节点的权(节点值)
7) 路径(从 root 节点找到该节点的路线)
8) 层
9) 子树
10) 树的高度(最大层数)
11) 森林 :多颗子树构成森林
*/

3、二叉树的概念

1. 树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树（注： <=2）
2. 二叉树的子节点分为左节点和右节点
3. 示意图

4. 如果该二叉树的所有叶子节点都在 最后一层，并且**结点总数= 2^n -1 **（等比数列求和） , n 为层数，则我们称为满二叉树

5. 完全二叉树是这样的二叉树：

   ①完全二叉树的倒数第二行及之前的行，都与满二叉树相同。

   ②倒数第一行右半部分可以是空的，也可以是满的，但不能有单个的出现！

   ③倒数第一行左半部分可以是空的，也可以是满的，也可有单个的出现，但有且只能有一个单个，且必须是它父亲的左孩子！

   …………

   这我们就知道了，满二叉树就是完全二叉树的特殊情况！

4、二叉树遍历的说明

1. 使用 前序，中序和后序对下面的二叉树进行遍历.
   1. 前序遍历: 先输出父节点，再遍历左子树和右子树 （根左右）
   2. 中序遍历: 先遍历左子树，再输出父节点，再遍历右子树 （左根右）
   3. 后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点 （左右根）
   4. 小结: 看输出父节点的顺序（即遍历父节点是在前面，中间还是后面），就确定是前序，中序还是后序

5、二叉树遍历实验

1. 应用实例的说明和思路

2. 代码实现

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("前序遍历");// 1  2   3   5   4binaryTree.PreOrder();System.out.println("中序遍历");// 2  1   5   3   4binaryTree.infixOrder();System.out.println("后序遍历");// 2  5   4   3   1binaryTree.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("二叉树为空， 无法遍历");}}
}class HeroNode{private int no;private String name;private HeroNode left;//默认nullprivate HeroNode right;//默认nullpublic 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;}@Overridepublic 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);}
}

6、二叉树-查找指定节点

1. 要求：
   1. 请编写前序查找，中序查找和后序查找的方法。
   2. 并分别使用三种查找方式，查找 herono = 5 的节点
   3. 并分析各种查找方式，分别比较了多少次
   4. 思路分析图解

2. 代码实现（只放了新加的，前面的见上一个代码块）

HeroNode类：//前序遍历查找
public HeroNode  preOrderSearch(int no){System.out.println("进入前序遍历查找");/*要查看查找了几次，得在判断当前节点的上面，因为在判断左右子树的上面的话，很多次都只是判断左右有没有节点，并不是在查找并且要判断找没找到最终的还是这一步，即便是左递归或者右递归，每个节点都是通过该句来判断是否为目标节点（或者说这就是跳出递归的出口）*///比较当前节点是不是if (this.no == no){return this;}//这个引用是为了接收每次递归的结果（包括要查找的那个）HeroNode resNode = null;//1、判断当前节点的左子树是否为空， 如果不为空， 则递归前序查找//2、如果左递归前序查找，找到节点，则返回if (this.left != null){//注意： 要把以左子树为根节点遍历的结果赋给resNoderesNode = this.left.preOrderSearch(no);}//如果resNode不为空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;}System.out.println("进入中序遍历查找");//如果做递归找到，则返回，如果没有就和当前节点比较， 如果是就返回当前节点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;}//如果左右子树都没有找到， 就比较当前节点是不是System.out.println("进入后序遍历查找");if (this.no == no){return this;}return resNode;
}BinaryTree类：//前序遍历查找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;}}main里面： //前序遍历查找
//        System.out.println("前序遍历方式~~~~~");
//        HeroNode resNode = binaryTree.preOrderSearch(15);
//        if (resNode != null){
//            System.out.printf("找到了， 信息为 no=%d  name=%s",resNode.getNo(),resNode.getName());
//        }else {
//            System.out.printf("没有找到 no=%d 的英雄",15);
//        }//中序遍历查找
//        System.out.println("中序遍历方式~~~~~");
//        HeroNode resNode = binaryTree.infixOrderSearch(15);
//        if (resNode != null){
//            System.out.printf("找到了， 信息为 no=%d  name=%s",resNode.getNo(),resNode.getName());
//        }else {
//            System.out.printf("没有找到 no=%d 的英雄",15);
//        }//后序遍历查找System.out.println("后序遍历方式~~~~~");HeroNode resNode = binaryTree.postOrderSearch(5);if (resNode != null){System.out.printf("找到了， 信息为 no=%d  name=%s",resNode.getNo(),resNode.getName());}else {System.out.printf("没有找到 no=%d 的英雄",5);}

7、二叉树-删除节点

1. 要求：（不考虑删除该节点后是否要把左或右孩子补上来）

   1. 如果删除的节点是叶子节点，则删除该节点
   2. 如果删除的节点是非叶子节点，则删除该子树.
   3. 测试，删除掉 5 号叶子节点 和 3 号子树.
   4. 完成删除思路分析

   

   (注： 首先处理的那步，还包含要删除的节点是根节点的情况，按照要求就是把二叉树置空（这条语句写在BinaryTree类里）

   ​ 对于第一步，其实就是判断当前节点的左孩子或者右孩子是否为我们要删除的节点，因为如果我们是判断当前节点是否要删除的话，那就删不掉了（因为当引用指向要删除的节点的时候，我们无法得到他的父节点）

   )

   5. 代码实现（其它的代码见上一个代码块）

   HeroNode类：//递归删除节点//1.如果删除的节点是叶子节点， 则删除该节点//2.如果删除的节点是非叶子节点，则删除该子树（注：是子树）public void delNode(int no){//如果当前节点的左子节点不为空， 并且左子节点 就是要删除的节点， 就将this.left = null; 并且就返回（结束递归删除）if (this.left != null && this.left.no == no){this.left = null;return;}//如果当前节点的右子节点不为空， 并且右子节点 就是要删除的节点， 就将this.right = null; 并且就返回（结束递归删除）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);}}BinaryTree类：//删除节点public void delNode(int no){if (root != null){//这里立即判断是不是只有一个root节点，或者root是不是就是要删除的节点if (root.getNo() == no){root = null;}else {//递归删除root.delNode(no);}}else {System.out.println("空树！！ 不能删除~");}}BinaryTreeDemo类：//删除节点
   System.out.println("删除前， 前序遍历");//1 2 3 5 4
   binaryTree.PreOrder();
   binaryTree.delNode(5);
   System.out.println("删除后， 前序遍历");//1 2 3 4
   binaryTree.PreOrder();
   

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！