二叉树

二叉搜索树

1. 复杂度计算

二叉树进行查找时, 第一次在根节点判断，第二次在第二层节点判断, 树的高度是多少就会判断多少次。树高\(h\)与节点个数\(N\)的关系为：\(h=\log_{2} (N+1)\), 所以复杂度为：\(O(logN)\)。

2. 定义二叉树、插入节点及三种遍历

/**
 * BinaryTree
 */
public class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }

    class Node {
        int data;
        Node left;
        Node right;

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

    /**
     * insert node
     */
    public void insert(int value) {
        Node newNode = new Node(value);
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            Node parentNode = null;
            while (current != null) {
                parentNode = current;
                if (current.data > value) {
                    current = current.left;
                    if (current == null) {
                        parentNode.left = newNode;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parentNode.right = newNode;
                    }
                }
            }
        }
    }

    /**
     * get tree hight, 主要使用递归求解
     */
    public int getHight(Node current) {
        if (current == null) {
            return 0;
        } else {
            int leftHight = getHight(current.left);
            int rightHight = getHight(current.right);
            int max = leftHight;
            if (rightHight > leftHight) {
                max = rightHight;
            }
            return max + 1;
        }
    }

    /**
     * find Max
     */
    public int getMax() {
        Node current = root;
        Node MaxNode = null;
        while (current != null) {
            MaxNode = current;
            current = current.right;
        }
        return MaxNode.data;
    }

    /**
     * find Min
     */
    public int getMin() {
        Node current = root;
        Node minNode = null;
        while (current != null) {
            minNode = current;
            current = current.left;
        }
        return minNode.data;
    }

    /**
     * inOrder
     */
    public void inOrder(Node current) {
        if (current != null) {
            inOrder(current.left);
            System.out.print(current.data + " ");
            inOrder(current.right);
        }
    }

    /**
     * preOrder
     */
    public void preOrder(Node current) {
        if (current != null) {
            System.out.print(current.data + " ");
            preOrder(current.left);
            preOrder(current.right);
        }
    }

    /**
     * postOrder
     */
    public void postOrder(Node current) {
        if (current != null) {
            postOrder(current.left);
            postOrder(current.right);
            System.out.print(current.data + " ");
        }
    }
}

3. 测试代码

/**
 * test BinaryTree
 */
public class test {
    public static void main(String[] args) {
        BinaryTree bt = new BinaryTree();
        int[] arr = new int[] { 4, 2, 1, 3, 6, 5, 8 };
        for (int i = 0; i < arr.length; i++) {
            bt.insert(arr[i]);
        }

        bt.inOrder(bt.root);
        System.out.println();
        bt.preOrder(bt.root);

        int treehight = bt.getHight(bt.root);
        System.out.println("Tree hight: " + treehight);

        int maxNumber = bt.getMax();
        System.out.println("Max number: " + maxNumber);
        
        int minNumber = bt.getMin();
        System.out.println("Min number: " + minNumber);
    }
}

二叉树

原文：https://www.cnblogs.com/maverickos/p/13179511.html