查找二叉树

假设一个数组{ 6, 3, 7, 2, 5, 1, 3, 9 }，使用java语言来创建一个二叉搜索树

首先创建一个节点类

/**
 * 查找二叉树的节点
 *
 */
public class BSTNode {

    private int key;
    public int data;
    public BSTNode parent;
    public BSTNode lchild;
    public BSTNode rchild;

    public BSTNode(int data) {
        this.data = data;
    }

    public int getKey() {
        return key;
    }

    public void setKey(int key) {
        this.key = key;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public BSTNode getParent() {
        return parent;
    }

    public void setParent(BSTNode parent) {
        this.parent = parent;
    }

    public BSTNode getLchild() {
        return lchild;
    }

    public void setLchild(BSTNode lchild) {
        this.lchild = lchild;
    }

    public BSTNode getRchild() {
        return rchild;
    }

    public void setRchild(BSTNode rchild) {
        this.rchild = rchild;
    }

}

创建查找二叉树

二叉树创建完成后，进行一次中序遍历，如果结果是有序的表示创建成功

/**
 * 构建二叉搜索树
 * 
 * { 6, 3, 7, 2, 5, 1, 3, 9 }
 *
 *                          6
 *               3                   7
 *       2             5                     9
 *1
 *遇到已存在的元素就不创建节点，上面这棵树就是要创建的二叉树，它的中序遍历结果为
 *  1 2 3 5 6 7 9       
 */
public class BSTree {

    public BSTNode root;

    public BSTNode putNode(int data) {
        BSTNode node = null;
        BSTNode parent = null;
        // 创建根节点
        if (root == null) {
            node = new BSTNode(data);
            root = node;
            return node;
        }
        // 从根节点开始遍历比较节点的data与新data的大小，遇到空节点结束
        node = root;                       // node是指针，开始时指向根节点
        while (isEmpty(node)) {
            parent = node;                 // 每到一个节点就记录该节点的父节点
            if (data > node.data) {        // 如果新data大于当前节点的data，就往右节点去比较
                node = node.rchild;     
            } else if (data < node.data) { // 如果新data小于当前节点的data，就往左节点去比较
                node = node.lchild;
            } else {
                return null;
            }
        }

        // 准备添加的新节点
        node = new BSTNode(data);    
        if(data > parent.data) {
            parent.rchild = node;
        }
        
        if(data < parent.data) {
            parent.lchild = node;
        }
        
        node.parent = parent;
        return node;
    }

    /**
     * 中序遍历
     */

    public void inOrder(BSTNode node) {
        if (node == null) {
            return;
        } else {
            inOrder(node.lchild);
            System.out.print(node.data + " ");
            inOrder(node.rchild);
        }
    }

    public boolean isEmpty(BSTNode node) {
        if (node != null) {
            return true;
        } else {
            return false;
        }
    }
    
    
    public static void main(String[] args) {
        BSTree bsTree = new BSTree();
        int[] arr = { 6, 3, 7, 2, 5, 1, 3, 9 };
        for(int x: arr) {
            bsTree.putNode(x);
        }
        bsTree.inOrder(bsTree.root);
    }
}