二叉查找树

叉查找树(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) {/size/color if(tree != null)

{
    postOrder(tree.left);
    postOrder(tree.right);
    System.out.print(tree.key+" ");
}

}

public void postOrder() {

postOrder(mRoot);

}

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

图片1.png

评论

暂无评论