二叉树

二叉树（Binary Tree）是n（n>=0）个节点的有限集合，该集合或者为空集，或者有一个根节点和两颗互不相交的分别称为根节点的左子树和右子树的二叉树组成。

特点

• 每个节点最多有两颗子树。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一个子树，也要区分是左子树还是右子树。

在一棵二叉树中，如果分支节点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

对一棵具有n个结点的二叉树按层编号，如果编号为i（1<= i <=n）的结点与同样深度的满二叉树编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

image.png

二叉树的性质

• 在二叉树的第i层上至多有 2^(i-1)个结点
• 深度为k的二叉树至多有2^k - 1个结点
  如果有一层 至多有 2^0 - 1 = 1个结点
  如果有二层 至多有 1+2 = 2^2 - 1 个结点
• 具有n个结点的完全二叉树的深度为[log(2)n] +1 ([x] 不大于x的最大整数)
  -如果对一棵有n个结点的完全二叉树的结点按层编号，对任一结点i
  1、如果 i= 1则结点i是二叉树的根
  2、如果2i>n 则结点无左结点
  3、如果2i+1>n 则结点i无右结点

二叉树的遍历

• 前序遍历

image.png

 public void preOrderTraverse(){
        preOrderTraverse(root);
    }
    //前序遍历  根 --> 左 --->右
    public void preOrderTraverse(Node root){
        if (root == null)return;
        System.out.println(root.val);
        preOrderTraverse(root.left);
        preOrderTraverse(root.right);
    }

• 中序遍历

image.png

// 左-->根--->右
    public void inOrderOrderTraverse(){
        inOrderOrderTraverse(root);
    }
    public void inOrderOrderTraverse(Node root){
        if (root == null)return;
        inOrderOrderTraverse(root.left);
        System.out.println(root.val);
        inOrderOrderTraverse(root.right);
    }

• 后续遍历

  
  image.png

//左--->右--->中
public void postOrderOrderTraverse(){
        postOrderOrderTraverse(root);
    }
    public void postOrderOrderTraverse(Node root){
        if (root == null)return;
        postOrderOrderTraverse(root.left);
        postOrderOrderTraverse(root.right);
        System.out.println(root.val);
    }

//结点类

   private class Node{
        private String val;
        private Node left,right;

        public Node(String val) {
            this.val = val;
        }
    }

二叉查找树

一棵二叉查找树（BST）是一个二叉树，其中每个结点都含有一个Comparable的键（以及相关的值）且每个节点的键都大于其左子树的任意结点的键而小于右子树的任意结点的键。

image.png

• 结点类

适合查找树
private class Node{
        private Key key;    //按照key来排序
        private Value val;  // 相关联的值
        private Node left,right;  //左右子结点
        private int size;         //结点个数
        public Node(Key key, Value val, int size) {
            this.key = key;
            this.val = val;
            this.size = size;
        }
    }

• 插入子节点

    public void put(Key key,Value val){
        if (key == null)throw new IllegalArgumentException("calls put() with a null key");
        if (val == null){
            delete(key); // 删除没有值的结点
            return;
        }
        root = put(root,key,val);
    }
    //递归插入
    private Node put(Node x,Key key,Value val){
        if (x == null)return new Node(key,val,1);
        int cmp = key.compareTo(x.key);  // 比较一个结点的键
        if (cmp < 0)x.left = put(x.left,key,val);  // 小 则往左插入
        else if(cmp > 0)x.right = put(x.right,key,val); // 大 则往右插入
        else x.val = val;                                             // 相等则更新
        x.size = 1+size(x.left)+size(x.right);              //重新计算相关的结点的size
        return x;
    }

image.png

• 获取键对应的值

    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x,Key key){
        if (key == null)throw new IllegalArgumentException("calls get() with a null key");
        if (x == null) return null;
        //二叉树的分叉查找
        int cmp = key.compareTo(x.key);
        // 左子树
        if (cmp < 0)return get(x.left,key);
        // 右子树
        else if(cmp > 0)return get(x.right,key);
        else return x.val;
    }

• 最大键和最小键
  如果根结点的左连接为null，那么一棵树的二叉查找树中最小的键解释根节点；如果非空，那么树中的最小键就是左子树中的最小键。同样道理适用于最大键

public Key min(){
        if (isEmpty()) throw new NoSuchElementException("calls min() with empty symbol table");
        return min(root).key;
    }

    private Node min(Node x){
        if (x.left == null)return x;
        else return min(x.left);
    }

    //最大
    public Key max(){
        if (isEmpty()) throw new NoSuchElementException("calls max() with empty symbol table");
        return max(root).key;
    }

    private Node max(Node x){
        if (x.right == null) return x;
        else return max(x.right);
    }

• 删除最大键和最小键

二叉查找树中最难实现的是delete()方法。即从符号表中删除一个键值对。
删除最小键所对应的键值对，就是不断深入跟结点的左子树直至出现一个空链接，然后将指向该节点的链接指向该节点的右子树。

 public void deleteMin(){
        if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
        root = deleteMin(root);
    }
    private Node deleteMin(Node x){
        if (x.left == null) return x.right; // 借宿递归
        x.left = deleteMin(x.left);  // 进入递归
        x.size = size(x.left)+size(x.right)+1;
        return x;
    }
   public void deleteMax(){
       if (isEmpty()) throw new NoSuchElementException("Symbol table underflow");
       root = deleteMax(root);
   }
    private Node deleteMax(Node x){
        if (x.right == null)return x.left;
        x.right = deleteMax(x.right);
        x.size = size(x.left)+size(x.right)+1;
        return x;
    }

• 删除指定的键的键值对
  在删除一个x结点后 需要用它的后续结点填补位置。因x可能有一个右子节点和左子结点。其右子节点就是其右子树中最小的结点。因此具体的补位顺序如下：
  1、将指向即将被删除的结点的链接保存为t
  2、将x指向它的后继结点min(t.right)
  3、将x的右链接指向deleteMin(t.right),也就是在删除后所有结点仍然都大于x.key的子二叉查找树
  4、将x的左连接设为t.left

    public void delete(Key key) {
        if (key == null) throw new IllegalArgumentException("calls delete() with a null key");
        root = delete(root, key);
    }
    private Node delete(Node x,Key key){
        if (x == null) return null;
        int cmp = key.compareTo(x.key);
        if (cmp < 0)x.left = delete(x.left,key);
        else if (cmp > 0)x.right = delete(x.right,key);  // 查找到要删除的键
        else {
            if (x.right == null)return x.left;
            if (x.left == null)return x.right;
            Node t =x;
            x = min(t.right);
            x.right = deleteMin(t.right );
            x.left = t.left;
        }
        x.size = size(x.left)+size(x.right);
        return x;
    }