树 - 实现二叉排序树（Java）

链表实现二叉树的类型声明（Java）：

/**
 * 树结构
 */
public class TreeNode {

    int value;
    TreeNode leftTreeNode = null;
    TreeNode rightTreeNode = null;

    public TreeNode(int value) {
        this.value = value;
        this.leftTreeNode = null;
        this.rightTreeNode = null;
    }
}

二叉树的构建

public class BinaryTree {

    private TreeNode rootNode;//二叉树的根节点

    public BinaryTree(int[] data) {
        for (int i = 0; i < data.length; i++) {
            addNodeToTree(data[I]);
        }
    }

    //将指定的值加入到二叉树中的适当的节点
    private void addNodeToTree(int value) {
        TreeNode currentNode = rootNode;
        if (rootNode == null) {//表示没有根节点，建立根节点
            rootNode = new TreeNode(value);
            return;
        }
        //建立二叉树
        while (true) {
            if (value < currentNode.value) {//在左子树
                if (currentNode.leftTreeNode == null) {
                    currentNode.leftTreeNode = new TreeNode(value);
                    return;
                } else {
                    currentNode = currentNode.leftTreeNode;
                }
            } else {//在右子树
                if (currentNode.rightTreeNode == null) {
                    currentNode.rightTreeNode = new TreeNode(value);
                    return;
                } else {
                    currentNode = currentNode.rightTreeNode;
                }
            }
        }
    }
}

调用（Kotlin写法）：

var data: IntArray = intArrayOf(6, 3, 5, 9, 7, 8, 4, 2)
BinaryTree(data)

二叉树构建过程分解：

第一步：i = 0 ，value = 6 ， rootNode = null 创建一个value=6的节点，rootNode = 6 第二步：i = 1 ，value = 3 ， rootNode值为6，value < rootNode ，放rootNode的左侧，而rootNode.leftTreeNode = null 所以创建一个value=3的节点,赋值给rootNode的leftTreeNode 第三步：i = 2 ，value = 5 ， rootNode值为6，value < rootNode ，放rootNode的左侧，然而 rootNode.leftTreeNode有值 =3 ，则value 与 rooNode.leltTreeNode进行比较。将rooNode.leltTreeNode 赋值给currtentNode ,此次循环执行完成，重新进入循环，此时currtentNode = 3 ，value > currtentNode.value 则创建一个value=5的节点,赋值给currtentNode的rightTreeNode 第四步：i = 3 ，value = 9 ， rootNode值为6，value > rootNode ，放rootNode的右侧，rootNode.rightTreeNode = null 创建一个value=3的节点,赋值给rootNode的rightTreeNode 第五步：i = 4 ，value = 7 ， rootNode值为6，value > rootNode ，放rootNode的右侧，然而 rootNode.rightTreeNode 有值，则value 与 rootNode.rightTreeNode进行比较，将rootNode.rightTreeNode 赋值给currtentNode ,此次循环执行完成，重新进入循环，此时currtentNode = 9 ，value < currtentNode.value 则创建一个value=7的节点,赋值给currtentNode的leftTreeNode 第六步：i = 5 ，value = 8 ， rootNode值为6，value > rootNode ，放rootNode的右侧，然而 rootNode.rightTreeNode 有值，则value 与 rootNode.rightTreeNode进行比较，将rootNode.rightTreeNode 赋值给currtentNode ,此次循环执行完成，重新进入循环，此时currtentNode = 9 ，value < currtentNode.value 然而currtentNode.leftTreeNode有值 = 7 ，所以将currentNode.leftTreeNode赋值给currentNode, 此次循环执行完成，重新进入循环，此时currtentNode = 7 ，value > currtentNode.value 则创建一个value=8的节点,赋值给currtentNode的rightTreeNode 第七步：i = 6 ，value = 4 ， rootNode值为6，value < rootNode ，放rootNode的左侧，然而 rootNode.leftTreeNode有值，则value 与 rooNode.leltTreeNode进行比较，将rooNode.leltTreeNode 赋值给currtentNode ,此次循环执行完成，重新进入循环，此时currtentNode = 3 ，value > currtentNode.value ，而currtentNode.value = 5，则重新将currtentNode.value 赋值给currtentNode,此次循环执行完成，重新进入循环，此时currtentNode = 5 ，value < currtentNode.value 则创建一个value=4的节点,赋值给currtentNode的leftTreeNode 第八步：i = 7 ，value = 2 ， rootNode值为6，value < rootNode ，放rootNode的左侧，然而 rootNode.leftTreeNode有值，则value 与 rooNode.leltTreeNode进行比较，将rooNode.leltTreeNode 赋值给currtentNode ,此次循环执行完成，重新进入循环，此时currtentNode = 3 ，value < currtentNode.value 则创建一个value=2的节点,赋值给currtentNode的rightTreeNode