数据结构--树

树

树的几个概念

高度：节点到叶子节点的最长路径(边数)
深度：根节点到这个节点所经历的边的数量
层数：深度 + 1
图片说明

二叉树

每个节点最多只有左右2个节点

满二叉树

除了叶子节点外，每个节点都有左右两个节点

完全二叉树

叶子节点都在最底下两层，最后一层的叶子节点都靠左排列

二叉树的遍历

前序遍历 遍历根节点 -> 左节点 -> 右节点

    public void pre(TreeNode root){
        if (root == null) return;
        System.out.println(root.data);
        pre(root.left);
        pre(root.right)
    }

中序遍历 遍历左节点 -> 根节点 -> 右节点

    public void middle(TreeNode root){
        if (root == null) return;
        middle(root.left);
        System.out.println(root.data);
        middle(root.right)
    }

后序遍历 遍历左节点 -> 右节点 -> 根节点

    public void after(TreeNode root){
        if (root == null) return;
        after(root.left);
        after(root.right)
        System.out.println(root.data);
    }

二叉查找树(二叉搜索树)

左节点都小于根节点，右节点都大于根节点

package com.xx;

public class Tree {
    Node root;
    public void pre(Node tree){
        if (tree == null) return;
        System.out.println(tree.data);
        pre(tree.left);
        pre(tree.right);
    }

    public void middle(Node tree){
        if (tree == null) return;
        middle(tree.left);
        System.out.println(tree.data);
        middle(tree.right);
    }

    public void after(Node tree){
        if (tree == null) return;
        after(tree.left);
        after(tree.right);
        System.out.println(tree.data);
    }

    public Node find(int value){
        Node curr = root;
        while(curr != null){
            if (value < curr.data){
                curr = curr.left;
            }else if (value > curr.data) {
                curr = curr.right;
            }else {
                return curr;
            }
        }
        return null;
    }

    public void insert(int data){
        if (root == null){
            root = new Node(data);
            return;
        }

        Node curr = root;
        while (curr != null){
            if (data < curr.data){
                if (curr.left == null){
                    curr.left = new Node(data);
                    return;
                }
                curr = curr.left;
            }else{
                if (curr.right == null){
                    curr.right = new Node(data);
                    return;
                }
                curr = curr.right;
            }
        }
    }

    public void delete(int data){
        Node curr = root;
        Node pp = null;
        while (curr != null && curr.data != data){
            pp = curr;
            if (data > curr.data) {
                curr = curr.right;
            }else{
                curr = curr.left;
            }
        }
        if (curr == null){
            return;
        }

        if(curr.left != null && curr.right != null){
            Node minP = curr.right;
            Node minPP = curr;
            while (minP.left != null){
                minPP = minP;
                minP = minPP.left;
            }
            curr.data = minP.data;
            curr = minP;
            pp = minPP;
        }

        // 删除节点是叶子节点或者仅有一个子节点
        Node child; // p 的子节点
        if (curr.left != null){
            child = curr.left;
        }
        else if (curr.right != null) {
            child = curr.right;
        }
        else {
            child = null;
        }

        // 删除的是根节点
        if (pp == null) {
            root = child;
        }
        else if (pp.left == curr) {
            pp.left = child;
        }
        else {
            pp.right = child;
        }
    }


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

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