BinaryTree Overview

why we Need it？ 🤑

我们前面学习了那么多的数据结构增删改查都有优化了还需要再学习一个奇怪的树结构的数据处理方式呢？

🆗 follow me！

我们先进行一个比较

数组（数组存储方式的分析）

优点：

通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。

缺点：

如果要检索具体某个值，或者插入值( 按一定顺序 ) 会整体移动，效率较低 [示意图]

链表（链式存储方式的分析）

优点：

在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，

删除效率也很好)。

缺点：

缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历) 【示意图】

SO 这时候我们就开始YY了当我们进行业务数据的处理里时，就可能会考虑到，我到底用那个方式好呢？当然撒刁才做选择！！！！我tm都要（大家底下评论666🤙 ），这时树结构就腾空出“事”了！！

树存储方式的分析

能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

二叉树的概念

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。

二叉树的子节点分为左节点和右节点
示意图
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树
使用前序，中序和后序对下面的二叉树进行遍历.
- 前序遍历: 先输出父节点，再遍历左子树和右子树。

 Java



 1
2
3
4
5
6
7
8
9
void preTrav() {
      System.out.println(this);
      if (this.left != null) {
        this.left.preTrav();
      }
      if (this.right != null) {
        this.right.preTrav();
      }
    }

中序遍历: 先遍历左子树，再输出父节点，再遍历右子树。

 Java



 1
2
3
4
5
6
7
8
9
void inordTrav() {
     if (this.left != null) {
       this.left.inordTrav();
     }
     System.out.println(this);
     if (this.right != null) {
       this.right.inordTrav();
     }
   }

后序遍历：先遍历左子树，再遍历右子树，再输出父节点。

 Java



 1
2
3
4
5
6
7
8
9
void postTrav() {
      if (this.left != null) {
        this.left.inordTrav();
      }
      if (this.right != null) {
        this.right.inordTrav();
      }
      System.out.println(this);
    }

树的术语

节点

根节点

父节点

子节点

叶子节点 (没有子节点的节点)

节点的权(节点值)

路径(从 root 节点找到该节点的路线)

层

子树

树的高度(最大层数)

森林 :多颗子树构成森林

二叉树遍历应用实例(前序,中序,后序)

代码

Java

package DataStructures.tree;

/**
 * @author yichangkong
 * @create 2020-05-18-15:45
 */
public class BinaryTreeDome {

  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);

    binaryTree.preorderTraversal();
  }

  static class BinaryTree {
    private HeroNode root;

    public void setRoot(HeroNode root) {
      this.root = root;
    }

    // 前序
    void preorderTraversal() {
      if (this.root != null) {
        this.root.preTrav();
      } else {
        System.out.println("二叉树为空！");
      }
    }
    // 中序
    void inOrderTraversal() {
      if (this.root != null) {
        this.root.inordTrav();
      } else {
        System.out.println("二叉树为空！");
      }
    }

    // 后序
    void postOrderTraversal() {
      if (this.root != null) {
        this.root.postTrav();
      } else {
        System.out.println("二叉树为空！");
      }
    }
  }

  /** @Description 子节点 @Param no 编号 name 姓名 left 左节点 right 右节点 @Date 2020/5/18 @Time 15:49 */
  static class HeroNode {
    int no;
    String name;
    HeroNode left;
    HeroNode right;

    public HeroNode(int no, String name) {
      super();
      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 "HordNote{" + "no=" + no + ", name='" + name + '\'' + '}';
    }

    /** @Description preorderTraversal： 先输出父节点，再遍历左子树和右子树 @Param [] @Return void */
    void preTrav() {
      System.out.println(this);
      if (this.left != null) {
        this.left.preTrav();
      }
      if (this.right != null) {
        this.right.preTrav();
      }
    }
    /** @Description inOrderTraversal： 先遍历左子树，再输出父节点，再遍历右子树 @Param [] @Return void */
    void inordTrav() {
      if (this.left != null) {
        this.left.inordTrav();
      }
      System.out.println(this);
      if (this.right != null) {
        this.right.inordTrav();
      }
    }

    /** @Description postOrderTraversal： 先遍历左子树，再遍历右子树，最后输出父节点 @Param [] @Return void */
    void postTrav() {
      if (this.left != null) {
        this.left.inordTrav();
      }
      if (this.right != null) {
        this.right.inordTrav();
      }
      System.out.println(this);
    }
  }
}