黑马程序员技术交流社区

标题: 【上海校区】二叉查找树 [打印本页]

作者: 时间留下最真 时间: 2018-10-25 19:03
标题: 【上海校区】二叉查找树
二叉查找树(Binary Search Tree)，又被称为二叉搜索树。
它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。那么，这棵树就是二叉查找树。如下图所示：

在二叉查找树中：
(01) 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
(02) 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
(03) 任意节点的左、右子树也分别为二叉查找树。
(04) 没有键值相等的节点（no duplicate nodes）。

二叉查找树的Java实现

1. 二叉查找树节点的定义

[Java] 纯文本查看 复制代码

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 遍历

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

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

前序遍历代码

[Java] 纯文本查看 复制代码

private void preOrder(BSTNode<T> tree) {

    if(tree != null) {

        System.out.print(tree.key+" ");

        preOrder(tree.left);

        preOrder(tree.right);

    }

}



public void preOrder() {

    preOrder(mRoot);

}

2.2 中序遍历

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

中序遍历代码

[Java] 纯文本查看 复制代码

private void inOrder(BSTNode<T> tree) {

    if(tree != null) {

        inOrder(tree.left);

        System.out.print(tree.key+" ");

        inOrder(tree.right);

    }

}



public void inOrder() {

    inOrder(mRoot);

}

2.3 后序遍历

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

后序遍历代码

[Java] 纯文本查看 复制代码

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

图片1.png (65.91 KB, 下载次数: 20)

作者: 不二晨 时间: 2018-10-31 14:25

作者: 魔都黑马少年梦 时间: 2018-11-1 16:10

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2