Java数据结构与算法（三）二叉树的查找和插入

一、树的术语

画一张图来描述二叉树的术语：

二叉树在学术上称为二叉搜索树。二叉搜索树的特征是：一个节点的左子节点的关键值小于这个节点的关键值，右子节点的关键值大于或等于这个节点的关键值：

二、二叉树的插入

2.1、定义Node节点

class TreeNode{
    int value;
    TreeNode leftChild;
    TreeNode rightChild;

    public TreeNode() {
    }

    public TreeNode(int value) {
        this.value = value;
        leftChild = null;
        rightChild = null;
    }   
}

2.2、定义树tree及二叉树的插入

二叉树的插入流程图：

代码实现：

class Tree{
    TreeNode root = null;

    public void insert(TreeNode treenode) {
        if( root == null ) {
            root = treenode;
        }
        else {
            TreeNode current = root;
            TreeNode parent;
            while(true) {
                while(true) {
                    parent = current;
                    if( treenode.value < parent.value ) {
                        current = current.leftChild;
                        if( current == null ) {
                            parent.leftChild = treenode;
                            return;
                        }
                    }
                    else {
                        current = current.rightChild;
                        if( current == null ) {
                            parent.rightChild = treenode;
                            return;
                        }
                    }
                }
            }
        }
    }
}

三、二叉树的查找

二叉树的查找代码编写：

public TreeNode find(int value) {
        TreeNode current = root;
        while(current.value != value) {
            if( value < current.value ) 
                current = current.leftChild;
            else
                current = current.rightChild;
            if( current == null )
                return null;
        }
        return current;
    }
}

四、二叉树的查找和插入测试

public class TreeDemo {
    public static void main(String[] args) {
        Tree tree = new Tree();
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(3);
        tree.insert(node1);
        tree.insert(node2);
        tree.insert(node3);
        TreeNode found = tree.find(3);
        if( found != null ) 
            System.out.println("找到了");
        else 
            System.out.println("找不到");
    }
}

运行结果：
找到了