[Java][华为云Java编程创造营][学习笔记][技能栈基本要求之数据结构][树][二叉树]

1，什么是树

• 

• 日常生活中很多事物都可以用树来描述，例如书的目录，工作单位的组织架构等等。

• 树是计算机中非常重要的一种数据结构，树存储方式可以提高数据存储、读取的效率，比如利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入、删除、修改的速度。

2，树的相关术语

• 结点：包含一个数据元素及若干指向子树分支的信息
• 结点的度：一个结点拥有子树的数目称为结点的度
• 叶子结点：也称为终端结点，没有子树的结点或者度为零的结点
• 分支结点：也称为非终端结点，度不为零的结点称为非终端结点
• 结点的层次：从根结点开始，根结点的层次为1，根的直接后继层次为2，以此类推
• 树的度：树中所有结点的度的最大值
• 树的深度：树中结点的最大层次
• 树具有以下特点：
  • 每个结点有多个或零个子结点
  • 没有父结点的结点称为根结点，没有子结点的结点称为叶结点
  • 每一个非根结点只有一个父结点
  • 每个结点及其后代结点整体上可以看做是一棵树，称为当前结点为根的子树
• 

3，二叉树的基本定义

• 二叉树就是度不超过2的树，其每个结点最多有两个子结点
• 二叉树的结点分为左结点和右结点
• 

满二叉树

• 二叉树的每一层的结点树都达到最大值，则这个二叉树就是满二叉树
• 一颗深度为n的满二叉树，有2^n-1个结点
• 

完全二叉树

• 叶子结点只能出现在最下层和次下层，最后一层的叶子结点在左边连续，倒数第二层的叶子结点在右边连续，我们称为完全二叉树
• 

4，二叉查找树的创建

二叉树的结点类：

class Node<Key, Value>
{
    private Key key;//存储键
    private Value value;//存储值
    private Node left;//左子结点
    private 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设计：

public class BinaryTree<Key, Value>
{
    private Node root;//根结点
    private int num;//树中元素的个数

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

    public void put(Key key, Value value)
    {
    }//添加元素

    public Node put(Node x, Key k, Value v)
    {
    }//向指定的树x中添加元素并返回新树

    public Value get(Key key)
    {
    }//查询树中指定key对应的value

    public Value get(Node x, Key key)
    {
    }//从指定的树x中，查找key对应的值

    public void delete(Key key)
    {
    }//删除树中key对应的value

    //从指定树x中，删除key对应的value，并返回新树
    public Node delete(Node x, Key key)
    {
    }
}

二叉查找树的实现

查找二叉树中最下和最大的键

• 比如二叉树中用来记录某公司员工薪资和员工姓名数据，或者某班级学生们的排名和姓名数据。如何快速找出排名最高和最低的同学数据？

//找出树中最小的键
public key min();
//找出树中，最小键所在的结点
public Node min(Node x);
//找出树中，最大的键
public key max();
//找出树中，最大键所在的结点
public Node max(Node x);

插入put方法的实现思路

• 情况1：当前树中没有任何一个结点，直接将新插入的结点当作根结点

  • 

• 情况2：当前树不为空，则从根结点开始

  • 如果新结点的key小于当前结点的key，则继续找当前结点的左子结点
  • 如果新结点的Key大于当前结点的key，则继续找当前结点的右子结点
  • 如果新结点的key等于当前结点的key，则书中已经存在这样的结点，替换该结点的value值即可。
  • 

查询get方法实现思路

• 从根结点开始
  • 如果要查询的key小于当前结点的key，则继续找当前结点的左子结点
  • 如果要查询的key大于当前结点的key，则继续找当前结点的右子结点
  • 如果要查询的key等于当前结点的key，则树中返回当前结点的value

删除delete方法实现思路

• 找到被删除结点
• 找到被删除结点右子树中的最小结点minNode
• 删除右子树中的最小结点
• 让被删除结点的左子树成为最小结点minNode的左子树，让被删除结点的右子树成为最小结点minNode的右子树
• 让被删除结点的父结点指向最小结点minNode
• 

5，二叉树的基础遍历

• 

• 前序遍历

  • 先访问根结点，再访问左子树，最后访问右子树
  • 遍历结果：EBADCGFH

• 中序遍历

  • 先访问左子树，再访问根结点，最后访问右子树
  • 遍历结果：ABCDEFGH

• 后序遍历

  • 先访问左子树，再访问右子树，最后访问根结点
  • 遍历结果：ACDBFHGE