二叉树的遍历查找删除

为什么需要树这种数据结构

数组存储方式的分析优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低

链式存储方式的分析优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历)

树存储方式的分析能提高数据存储，读取的效率, 比如利用 二叉排序树(Binary Sort Tree)，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。【示意图,后面详讲】案例: [7, 3, 10, 1, 5, 9, 12]

二叉树的概念

树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
二叉树的子节点分为左节点和右节点。
如果该二叉树的所有叶子节点都在最后一层，并且结点总数= 2^n -1 , n 为层数，则我们称为满二叉树。
如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树

前序遍历: 先输出父节点，再遍历左子树和右子树
中序遍历: 先遍历左子树，再输出父节点，再遍历右子树
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点
小结: 看输出父节点的顺序，就确定是前序，中序还是后序

public class BinaryTree {
    public Node root;

    public static void main(String[] args) {

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5, "wangwu");
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        BinaryTree tree = new BinaryTree();
        tree.root = node1;
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
//           1
//        /    \
//       2      3
//      / \    / \
//     4   5  6   7
        System.out.println("先根遍历：");
        // 1245367
        tree.preOrder();
        System.out.println("中根遍历：");
        // 4251637
        tree.infixOrder();
        System.out.println("后根遍历：");
        // 4526731
        tree.postOrder();
        System.out.println("先根查找：");
        tree.preOrderSearch(5);
        System.out.println("中根查找");
        tree.infixOrderSearch(5);
        System.out.println("后根查找：");
        tree.postOrderSearch(5);
        System.out.println("删除叶子节点5");
        tree.delNode(5);
        tree.preOrder();
        System.out.println("删除非叶子节点2");
        tree.delNode(3);
        tree.preOrder();
    }

    public void preOrder() {
        if (root == null) {
            return;
        }
        root.preOrder();
    }

    public void postOrder() {
        if (root == null) {
            return;
        }
        root.postOrder();
    }

    public void infixOrder() {
        if (root == null) {
            return;
        }
        root.infixOrder();
    }

    public void preOrderSearch(int no) {
        if (root == null) {
            return;
        }
        System.out.println(root.preOrderSerach(no));
    }

    public void infixOrderSearch(int no) {
        if (root == null) {
            return;
        }
        System.out.println(root.infixOrderSearch(no));
    }

    public void postOrderSearch(int no) {
        if (root == null) {
            return;
        }
        System.out.println(root.postOrderSearch(no));
    }

    /**
     * 如果根节点为null,直接返回，如果根节点就是要删除的节点，直接把根节点置为null
     * 如果要删除的节点是叶子节点，直接把叶子节点删除
     * 如果要删除的节点是非叶子节点，则直接把该子树全部删除
     *
     * @param no
     */
    public void delNode(int no) {
        if (root != null) {
            if (root.no == no) {
                root = null;
                return;
            } else {
                root.delNode(no);
            }
        } else {
            System.out.println("当前树为空");
        }
    }
}

/**
 * 先根遍历将打印节点值放最前，后根遍历将打印节点值放最后，中根遍历将打印节点值放中间
 */
class Node {
    public int no;
    public String name;
    public Node left;
    public Node right;

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

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public void preOrder() {
        System.out.println(this.no);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this.no);
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this.no);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public String preOrderSerach(int no) {
        if (this.no == no) {
            return this.name;
        }
        if (this.left != null) {
            String s = this.left.preOrderSerach(no);
            if (s != null) {
                return s;
            }
        }
        if (this.right != null) {
            String s = this.right.preOrderSerach(no);
            if (s != null) {
                return s;
            }
        }
        return null;
    }

    public String postOrderSearch(int no) {
        if (this.left != null) {
            String s = this.left.postOrderSearch(no);
            if (s != null) {
                return s;
            }
        }
        if (this.right != null) {
            String s = this.right.postOrderSearch(no);
            if (s != null) {
                return s;
            }
        }
        if (this.no == no) {
            return this.name;
        }
        return null;
    }

    public String infixOrderSearch(int no) {
        if (this.left != null) {
            String s = this.left.infixOrderSearch(no);
            if (s != null) {
                return s;
            }
        }
        if (this.no == no) {
            return this.name;
        }
        if (this.right != null) {
            String s = this.right.infixOrderSearch(no);
            if (s != null) {
                return s;
            }
        }

        return null;
    }

    /**
     * 如果左子树不等于null且左子树就是要删除的子树，则将左子树置为null
     * 如果右子树不等于null且右子树就是要删除的子树，则将右子树置为null
     * 如果左右子树都不是待删除的节点，则分别向左子树向右子树递归删除
     *
     * @param no
     */
    public void delNode(int no) {
        if (this.left != null) {
            if (this.left.no == no) {
                this.left = null;
                return;
            }

            if (this.right != null) {
                if (this.right.no == no) {
                    this.right = null;
                    return;
                }
            }

            if (this.left != null) {
                this.left.delNode(no);
            }
            if (this.right != null) {
                this.right.delNode(no);
            }
        }
    }
}