数据结构-02-二叉查找树

参考博客 ： https://www.cnblogs.com/skywang12345/p/3603935.html

数据结构在线生成工具 ： https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

1. 二叉查找树简介

• 二叉查找树(Binary Search Tree)，又被称为二叉搜索树。

• 它是特殊的二叉树

  • 对于二叉树，假设x为二叉树中的任意一个节点，x节点中包含关键字key,节点x的key值记位key[x] 。
  • 如果 y 是 x 的左子树中的一个节点，则key[y] <= key[x] ;
  • 如果 y 是 x的右子树中的一个节点，则key[y] >= key[x];

那么，这棵树就是二叉查找树。如下图所示：

性质：在二叉查找树中

• 如果任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
• 任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
• 任意节点的左，右子树也分别为二叉查找树。（递归的思想）
• 没有键值相等的节点（no duplicate nodes）。

2. 二叉查找树的Java实现

2.1 定义

// T extends Comparable<T> 说明泛型T必须实现了Comparable接口
// <T extends Comparable<? super T>>　说明泛型T或者其父类必须实现了Comparable接口
public class BSTree<T extends Comparable<T>> {

    private BSTNode<T> mRoot;    // 根结点

    
    public class BSTNode<T extends Comparable<T>> {
        T key;                // 关键字(键值)
        BSTNode<T> left;      // 左孩子
        BSTNode<T> right;     // 右孩子
        BSTNode<T> parent;    // 父结点

        // 构造函数
        public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
            this.key = key;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }
}

注意：

• BSTree是二叉树，它保护了二叉树的根节点mRoot;
• mRoot是BSTNode类型，而BSTNode是而二叉查找树的节点，它是BSTree的内部类。
• BSTNode 包含了以下几个基本信息：
  • (01) key – 它是关键字，是用来对二叉查找树的节点进行排序的。
    (02) left – 它指向当前节点的左孩子。
    (03) right – 它指向当前节点的右孩子。
    (04) parent – 它指向当前节点的父结点。

2.2 遍历

• 这里讲解前序遍历、中序遍历、后序遍历3种方式。

前序遍历

若二叉树非空，则执行以下操作：
(01) 访问根结点；
(02) 先序遍历左子树；
(03) 先序遍历右子树。

// 前序遍历
private void preOrder(BSTNode<T> tree){
    if (tree != null){
        System.out.println(tree.key + " ");
        preOrder(tree.left);
        preOrder(tree.right);
    }
}

private void preOrder(){
    preOrder(mRoot);
}

中序遍历

若二叉树非空，则执行以下操作：
(01) 中序遍历左子树；
(02) 访问根结点；
(03) 中序遍历右子树。

// 中序遍历
private void inOrder(BSTNode<T> tree){
    if (tree != null){
        inOrder(tree.left);
        System.out.println(tree.key + " ");
        inOrder(tree.right);
    }
}

private void inOrder(){
    inOrder(mRoot);
}

后序遍历

若二叉树非空，则执行以下操作：
(01) 后序遍历左子树；
(02) 后序遍历右子树；
(03) 访问根结点。

// 后序遍历
private void postOrder(BSTNode<T> tree) {
    if(tree != null)
    {
        postOrder(tree.left);
        postOrder(tree.right);
        System.out.print(tree.key+" ");
    }
}

public void postOrder() {
    postOrder(mRoot);
}

看看下面这颗树的各种遍历方式：

对于上面的二叉树而言，
(01) 前序遍历结果： 3 1 2 5 4 6
(02) 中序遍历结果： 1 2 3 4 5 6
(03) 后序遍历结果： 2 1 4 6 5 3

2.3 查找

• 递归版本的查找

/*
 * (递归实现)查找"二叉树x"中键值为key的节点
 */
private BSTNode<T> search(BSTNode<T> x, T key) {
    if (x==null)
        return x;

    int cmp = key.compareTo(x.key);
    if (cmp < 0)
        return search(x.left, key);
    else if (cmp > 0)
        return search(x.right, key);
    else
        return x;
}

public BSTNode<T> search(T key) {
    return search(mRoot, key);
}

• 非递归实现

/*
 * (非递归实现)查找"二叉树x"中键值为key的节点
 */
private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) {
    while (x != null) {
        int cmp = key.compareTo(x.key);

        if (cmp < 0)
            x = x.left;
        else if (cmp > 0)
            x = x.right;
        else
            return x;
    }
    return x;
}

public BSTNode<T> iterativeSearch(T key) {
    return iterativeSearch(mRoot, key);
}

打赏