你的位置:首页 > Java教程

[Java教程][javaSE] 数据结构(二叉查找树


二叉查找树(Binary Search Tree),又被称为二叉搜索树,它是特殊的二叉树,左子树的节点值小于右子树的节点值。

 

定义二叉查找树

定义二叉树BSTree,它保护了二叉树的根节点BSTNode类型的mRoot,定义内部类BSTNode

包含二叉树的几个基本信息:

key——关键字用来对二叉查找树的节点进行排序

left——指向当前节点的左孩子

right——指向当前节点的右孩子

parent——指向当前节点的父节点

 

定义插入节点方法insert(T key),参数:T key要插入的对象

创建节点对象,实例化BSTNode对象,构造参数:T对象

定义重载方法insert(BSTree bsTree,BSTNode bstNode)方法,参数:BSTree树对象,BSTNode节点对象

插入节点,分两步,

1.找到节点的父节点位置

2.插入节点到父节点的左位置或者右位置

public class BSTree<T extends Comparable<T>> {  private BSTNode<T> mRoot;  /**   * 定义二叉树   *   * @author taoshihan   * @param <T>   *   */  public class BSTNode<T extends Comparable<T>> {    public T key;    public BSTNode parent, left, right;    public BSTNode(T key, BSTNode parent, BSTNode left, BSTNode right) {      this.key = key;      this.parent = parent;      this.left = left;      this.right = right;    }  }  public void insert(BSTree bsTree, BSTNode bstNode) {    BSTNode parent = null;    BSTNode x = bsTree.mRoot;    // 查找bstNode的插入位置,x的指针指对    while (x != null) {      parent = x;// 把x的位置作为节点的父类      int flag = bstNode.key.compareTo(x.key);      if (flag < 0) {        x = x.left;      }else{        x=x.right;      }    }    // 插入    bstNode.parent = parent;    if(parent==null){      bsTree.mRoot=bstNode;    }else{      int flag = bstNode.key.compareTo(parent.key);      if (flag < 0) {        parent.left = bstNode;      } else {        parent.right = bstNode;      }        }  }  /**   * 插入根节点   *   * @param key   */  public void insert(T key) {    BSTNode<T> z = new BSTNode<T>(key, null, null, null);    // 如果新建结点失败,则返回。    if (z != null)      insert(this, z);  }  /*   * 打印"二叉查找树"   *   * key    -- 节点的键值   * direction -- 0,表示该节点是根节点;   *        -1,表示该节点是它的父结点的左孩子;   *        1,表示该节点是它的父结点的右孩子。   */  private void print(BSTNode<T> tree, T key, int direction) {        if(tree != null) {      if(direction==0)  // tree是根节点        System.out.printf("%2d is root\n", tree.key);      else        // tree是分支节点        System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction==1?"right" : "left");      print(tree.left, tree.key, -1);      print(tree.right,tree.key, 1);    }  }  public void print(BSTree<T> tree) {    if (tree.mRoot != null){      print(tree.mRoot, tree.mRoot.key, 0);    }  }  /**   * @param args   */  public static void main(String[] args) {    BSTree tree = new BSTree();    tree.insert(3);    tree.insert(1);    tree.insert(2);    tree.insert(5);    tree.insert(4);    tree.insert(6);    tree.print(tree);  }}

 

输出:

3 is root
1 is 3's left child
2 is 1's right child
5 is 3's right child
4 is 5's left child
6 is 5's right child