之前我们实现的符号表中,不难看出,符号表的增删查操作,随着元素个数$N$的增多,其消耗时间也是线性增多的,时间复杂度都是$O(n)$,为了提高运算效率,我们需要学习树这种数据结构

树的基本定义

树是我们计算机中非常重要的一种数据结构,同时使用树这种数据结构,可以描述现实生活中的很多事物,例如说家谱,单元的组织架构等等

树是由$n(n>=1)$个有限节点组成一个具有层次关系的集合,把它叫做是因为它看起来像一棵倒挂的树,也就是说它根是朝上的,而叶朝下的

树具有以下特点:

  1. 每个节点有零个或多个子节点
  2. 没有父节点的节点为根节点
  3. 每一个非根节点只有一个父节点
  4. 每个节点及其后代节点整体上可以看做是一棵树,称为当前节点的父节点的一个子树

树的相关术语

  • 节点的度:一个节点含有的子树的个数称为该节点的度
  • 叶节点:度为$0$的节点称为叶节点,也可以叫做终端节点
  • 分支节点:度不为$0$的节点称为分支节点,也可以叫做非终端节点
  • 节点的层次:从根节点开始,根节点的层次为$1$,根的直接后继层次为$2$,以此类推
  • 节点的层序编号:将树中的节点,按照从上层到下层,同层从左到右的次序排成一个线性序列,把他们编成连续的自然数
  • 树的度:树中所有节点的度的最大值
  • 树的高度(深度):树中节点的最大层次
  • 森林:$m(m>=0)$个互不相交的树的集合,将一棵非空树的根节点删去,树就变成一个森林,给森林增加一个统一的根节点,森林就变成一棵树
  • 孩子节点: 一个节点的直接后继节点称为该节点的孩子节点
  • 双亲节点(父节点):一个节点的直接前驱称为该节点的双亲节点
  • 兄弟节点:同一双亲节点的孩子节点之间互称为兄弟节点

二叉树的基本定义

二叉树就是度不超过$2$的树(每个节点最多有两个子节点)

  • 满二叉树:一个二叉树,如果每一层的节点树都达到最大值,则这个二叉树就是满二叉树

  • 完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的节点都集中在该层最左边的若干位置的二叉树

二叉查找树的创建

二叉树的节点类

根据对图的观察,我们发现二叉树其实就是由一个又一个的节点及其之间的关系组成的,按照面向对象的思想,我们设计一个节点类来描述节点这个事务

节点类API设计
类名Node
构造方法Node(Key key,Value value,Node left,Node right):创建Node对象
成员变量1.public Node left:记录左子节点 2.public Node right:记录右子节点 3.public Key key:存储键 4.public Value value:存储值
代码实现
private class Node<Key, Value> {

    //存储键
    public Key key;
    //存储值
    private Value value;
    //记录左子节点
    public Node left;
    //记录右子节点
    public Node right;

    public Node(Key key, Value value, Node left, Node right) {
      this.key = key;
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }
二叉查找树API设计
类名BinaryTree,Value value>
构造方法BinaryTree():创建BinaryTree对象
成员变量1.private Node root:记录根节点 2.private int N:记录树中元素的个数
成员方法1.public void put(Key key,Value value):向树中插入一个键值对 2.private Node put(Node x,Key key,Value value):给指定树x上,添加一个键值对,并返回添加后的新树 3.public Value get(Key key):根据key,从树中找出对应的值 4.private Value get(Node x,Key key):从指定的树x中,找出key对应的值 5.public void delete(Key key):根据key,删除树中对应的键值对 6.private Node delete(Node x,Key key):删除指定树x上的键为key的键值对,并返回删除后的新树 7.publid int size():获取树中元素的个数
插入方法put实现思想
  1. 如果当前树中没有任何一个节点,则直接把新节点当做根节点使用
  2. 如果当前树不为空,则从根节点开始

    • 如果新节点的$key$小于当前节点的$key$,则继续找当前节点的左子节点
    • 如果新节点的$key$大于当前节点的$key$,则继续找当前节点的右子节点
    • 如果新节点的$key$等于当前节点的$key$,则树中已经存在这样的节点,替换该节点的$value$即可

删除方法delete实现思想
  1. 找到被删除的节点
  2. 找到被删除节点右子树中最小节点minNode
  3. 删除右子树中最小节点
  4. 让被删除节点的左子树成为最小节点minNode的左子树,让被删除节点的右子树称为最小节点minNode的右子树
  5. 让被删除节点的父节点指向最小节点minNode
  • 其实选择右最小节点左最大节点进行替换效果一样

代码实现

BinaryTree

public class BinaryTree<Key extends Comparable<Key>, Value> {

  /**
   * 记录首节点
   */
  private Node root;
  /**
   * 记录树中元素的个数
   */
  public int N;

  private class Node {

    //存储键
    public Key key;
    //存储值
    private Value value;
    //记录左子节点
    public Node left;
    //记录右子节点
    public Node right;

    public Node(Key key, Value value, Node left, Node right) {
      this.key = key;
      this.value = value;
      this.left = left;
      this.right = right;
    }
  }

  /**
   * 获取树中元素的个数
   */
  public int size() {
    return N;
  }

  /**
   * 向树中添加元素key-value
   */
  public void put(Key key, Value value) {
    //其实要向树中插入就是向根节点中插入,所以调用put的重载方法
    root = put(root, key, value);
  }

  /**
   * 重载put方法,向指定的树中添加key-value,并返回添加元素后的新树
   */
  private Node put(Node x, Key key, Value value) {
    //如果这个树为空,则直接创建这个新树,并返回
    if (x == null) {
      //首先元素个数+1
      N++;
      //因为这是一个完全新的树,所以不指向任何一个子树
      return new Node(key, value, null, null);
    }
    //如果这个树不为空,则需要与其键进行比较
    if ((key.compareTo(x.key)) > 0) {
      //如果要插入的这个值大于原来的那个值,则插入到节点的右边
      x.right = put(x.right, key, value);
    } else if ((key.compareTo(x.key)) < 0) {
      //如果要插入的这个值小于原来的那个值,则插入到节点的左边
      x.left = put(x.left, key, value);
    } else {
      //如果要插入的这个值等于原来的那个值,则直接更新原来节点的value即可
      x.value = value;
    }
    //返回新的节点即可
    return x;
  }

  /**
   * 查询树中指定的key对应的value
   */
  public Value get(Key key) {
    //这是从整个树中寻找key,可以调用重载的方法从根节点开始寻找key
    return get(root, key);
  }

  /**
   * 从指定的树x中,查找key对应的值
   */
  public Value get(Node x, Key key) {
    //情况1:例如找key=10,但最大的key=9,相当于找9的右下节点,相当于找到了个null,所以直接返回null
    if (x == null) {
      return null;
    }
    //情况2:如果x!=null,相当于可以继续向下找,则应该判断是大于还是小于,从而判断是向左找还是向右找,直到找到key相等的键,直接返回value
    if ((key.compareTo(x.key)) > 0) {
      //如果比key大,则向右下找,使用递归方法
      return get(x.right, key);
    } else if ((key.compareTo(x.key)) < 0) {
      //如果比key小,则向左下找,使用递归方法
      return get(x.left, key);
    } else {
      //如果key相等,则返回value
      return x.value;
    }
  }

  /**
   * 删除树中key对应的value
   */
  public void delete(Key key) {
    //这是从整个树中删除某个key,所以调用重载方法即可
    delete(root, key);
  }

  /**
   * 删除指定树x中的key对应的value,并返回删除后的树
   */
  public Node delete(Node x, Key key) {
    //情况1:找不到想指定删除的x树,直接返回null
    if (x == null) {
      return null;
    }
    //情况2:能找到指定删除的x树
    if ((key.compareTo(x.key)) > 0) {
      //如果比key大,则向右下找,使用递归方法
      x.right = delete(x.right, key);
    } else if ((key.compareTo(x.key)) < 0) {
      //如果比key小,则向左下找,使用递归方法
      x.left = delete(x.left, key);
    } else {
      //元素个数-1
      N--;
      //如果key相等,则找到该x树,进行删除
      //这时候就要去找x节点的右子树的最小节点也就是最左节点
      //情况1:
      //如果右子树为空,则直接将左子树链接起来
      if (x.right == null) {
        return x.left;
      }
      //如果左子树为空,则直接将右子树链接起来
      if (x.left == null) {
        return x.right;
      }
      //情况2:
      //如果一切正常的话,就要从右边找最小
      Node minNode = x.right;
      while (minNode.left != null) {
        minNode = minNode.left;
      }
      //将minNode与他的父节点断开连接
      Node xRight = x.right;
      while (xRight.left != null) {
        if (xRight.left == minNode) {
          xRight.left = null;
        } else {
          //变换n节点
          xRight = xRight.left;
        }
      }
      //让minNode的左子树变为x的左子树
      minNode.left = x.left;
      //让minNode的右子树变为x的右子树
      minNode.right = x.right;
      //让minNode的父节点变为x的父节点
      x = minNode;
    }
    return x;
  }
}

BinaryTreeTest

public static void main(String[] args) {
    //创建二叉查找树对象
    BinaryTree<Integer, String> tree = new BinaryTree<>();
    //测试插入
    tree.put(1, "GAT5");
    tree.put(2, "PUBG");
    tree.put(3, "LOL");
    tree.put(4, "APEX");
    tree.put(5, "CSGO");
    System.out.println("插入完毕后的元素个数:" + tree.size());
    //测试查找
    System.out.println("键4对应的元素为:" + tree.get(4));
    //测试删除
    tree.delete(3);
    System.out.println("删除后元素对应的个数:" + tree.size());
    System.out.println("删除后键3是否存在,删除成功后应该返回null:" + tree.get(3));
    //如果没找到要删除的元素,则个数不变
  }

二叉查找树其他便捷方法

查找二叉树中最小的键

在某些情况下,我们需要查找出树中存储所有元素的键的最小值,比如我们的树中存储的是学生的排名和姓名数据,那么需要查找出排名最低是多少

public Key min()找出树中最小的键
private Node min(Node x)找出指定树x中,最小键所在的节点位置
/**
   * 查找树中最小的键
   */
  public Key min() {
    return min(root).key;
  }

  /**
   * 重载方法,查找指定树x中最小键所在节点的位置
   */
  private Node min(Node x) {
    //其实就是一直向左,使用递归调用找到最小的节点
    if (x.left != null) {
      return min(x.left);
    } else {
      return x;
    }
  }
查找二叉树中最大的键

在某些情况下,我们需要查找出树中存储所有元素的键的最大值,比如我们的树存储的是学生的成绩和学生的姓名,那么需要查找出最高的分数是多少

public Key max()找出树中最大的键
public Node max(Node x)找出指定树x中,最大键所在的节点
/**
   * 查找树中最大的键
   */
  public Key max() {
    return max(root).key;
  }

  /**
   * 重载方法,查找指定树x中最大键所在节点的位置
   */
  private Node max(Node x) {
    //使用递归调用,一直向右找,直到找到最右的节点
    if (x.right != null) {
      return max(x.right);
    } else {
      return x;
    }
  }
Last modification:June 6th, 2021 at 06:48 pm