【数据结构】二叉树的原理及实现

1.什么是数？

• 树这种数据结构在计算机中是非常重要的，是一种非线性数据结构。一些数据库的底层与快速索引都离不开树这种数据结构。
• 树是有很多节点组成的具有一定层次关系的集合。最上面的可以看成是树的头，下面的很多节点就在这个头的基础上不断的向下延伸，类似一颗倒挂的树。
• 树是由n>=0个结点的有限集，当n=0的时候，这个树被叫做空树。当n>1的时候，表明它是一颗非空的树，在一颗非空的树里面。

• 树的特点

  • 在每一个节点会有0个或者0个以上的子节点
  • 没有父节点的节点被称为根节点
  • 非根节点只有一个父节点
  • 每个节点的子节点整体上来看像一颗倒挂的树，也被称为父节点子树。

• 树的专业术语

  • 节点：是指数据元素和指向子树的分支
  • 根节点：在非空树中没有前驱结点的结点，被称为根节点（注意，只有一个根节点）
  • 节点的度：结点所拥有子树个数
  • 树的度：树里的各个节点度的最大值
  • 父节点：A是B的父节点
  • 子节点：B是A的子节点
  • 叶子节点：当度等于0的时候被称为叶子节点。
  • 路径：从根节点找该节点的路径，比如要找K节点。路径为：A->C->G->K
  • 层：同一个层面为一层。如A为1层，BC为2层

2.二叉树基本概念

• 什么是二叉树

  • 树有很多种，但是每一个结点最多只有两个子节点的树，被称作为二叉树。
  • 二叉树的子节点又分成左节点与右节点
  • 二叉树又分为满二叉树与完全二叉树

• 满二叉树

  • 概念为：如果这颗二叉树的所有叶子节点都在该树的最后一层的话，并且节点的总数=2^n-1（n为层数）。
  • 节点总数=2^4-1=15

• 完全二叉树

  • 概念：当前二叉树所有的叶子节点再倒数第一层或者是倒数第二层当中，而且的话最后一层的叶子节点是在左边连续的，而在倒数第二层的叶子节点是右边连续的。

  • 如果把G节点删除的话，它就不属于完全二叉树了，因为它的叶子结点已经是不连续了。

• 二叉排序树

  • 概念：也叫作二叉查找树。二叉排序树的任何一个非叶子节点，都要求他的左子节点的值要比当前的节点值小，右子节点值要比当前的节点值大。

  • 排序树的左子树不为空，那么左子树的所有节点都小于他根节点的值

  • 他的右子树不为空，那么右子树的所有节点的值都大于它根节点的值

3.二叉树的前中后续遍历

• 二叉树的遍历

  • 在学数组的时候，需要查找某一个值的时候，是不是需要遍历数据来查找的。

• 那在树结构查找某一个值的时候，它与线性结构不一样，没有办法从头开始遍历，那它是如何进行遍历的呢？

我们可以把上图的树分成根节点、左子树和右子树。再根据根节点什么时候被访问，我们就把二叉树遍历分成三种方式

• 前序遍历：首先访问根节点，然后先是访问左子树，最后才到右子树。
  • 6 4 2 1 3 5 9 8 11
• 中序遍历：首先访问左子树，然后到根节点，最后才到右子树。
  • 1 2 3 4 5 6 8 9 11
• 后序遍历：首先访问左子树，然后到右子树，最后到根节点。
  • 1 3 2 6 4 8 11 9 6

4.排序二叉树实战

public class BinaryTree {

    //创建根节点
    public Node root;

    /**
     * 查看二叉树
     * @return
     */
    public Node getRoot(){
        return root;
    }

    /**
     * 求二叉树的最大深度
     * @param root
     * @return
     */
    public int maxDep(Node root){
        //根节点是否为空
        if(root == null) return 0;
        return Math.max(maxDep(root.left),maxDep(root.right))+1;
    }

    /**
     * 查找二叉树节点
     * @param id
     * @return
     */
    public String get(Node root,int id){
        //判断根节点是否为null
        if(root == null){
            return "";
        }
        //判断传入的ID是否是小于根节点
        if(id < root.id){
            return get(root.left,id);
        }
        //判断传入的ID是否大于根节点
        if(id > root.id){
            return get(root.right,id);
        }
        return root.name;
    }

    /**
     * 二叉树添加节点
     * @param node
     */
    public void add(Node node){
        //先判断根是否为null
        if(root == null){
            root = node;
        }else{
            root.add(node);
        }
    }

    /**
     * 前序遍历
     */
    public void preTraversal(){
        getRoot().preTraversal();
    }

    /**
     * 中序遍历
     */
    public void infixTraversal(){
        getRoot().infixTraversal();
    }

    /**
     * 后续遍历
     */
    public void postTraversal(){
        getRoot().postTraversal();
    }

    static class Node{
        //定义ID
        private int id;
        //定义name
        private String name;
        //定义左节点
        private Node left;
        //定义右节点
        private Node right;
        //初始化节点的值
        public Node(int id,String name){
            this.id = id;
            this.name = name;
        }

        /**
         * 添加节点
         * @param node
         */
        public void add(Node node){
            //首先先判断node是否为null
            if(node == null){
                return;
            }
            //判断是否比根小,向左插入
            if(node.id<this.id){
                if(this.left == null){
                    this.left = node;
                }else{
                    this.left.add(node);
                }
            }
            //判断是否比根大，向右插入
            if(node.id>this.id){
                if(this.right == null){
                    this.right = node;
                }else{
                    this.right.add(node);
                }
            }
        }

        /**
         * 前序遍历
         */
        public void preTraversal(){
            //输出根节点
            System.out.println("id:"+this.id+",name:"+this.name);
            //输出左节点
            if(this.left!=null){
                this.left.preTraversal();
            }
            //输出右节点
            if(this.right!=null){
                this.right.preTraversal();
            }
        }

        /**
         * 中序遍历
         */
        public void infixTraversal(){
            //输出左节点
            if(this.left!=null){
                this.left.infixTraversal();
            }
            //输出根节点
            System.out.println("id:"+this.id+",name:"+this.name);
            //输出右节点
            if(this.right!=null){
                this.right.infixTraversal();
            }
        }

        /**
         * 后续遍历
         */
        public void postTraversal(){
            //输出左节点
            if(this.left!=null){
                this.left.postTraversal();
            }
            //输出右节点
            if(this.right!=null){
                this.right.postTraversal();
            }
            //输出根节点
            System.out.println("id:"+this.id+",name:"+this.name);
        }
    }

    public static void main(String[] args) {

        BinaryTree binaryTree = new BinaryTree();

        int [] arr = {4,2,9,7,1,5};
        // 向树中添加元素
        for (int i = 0; i < arr.length; i++) {
            binaryTree.add(new Node(arr[i], "李祥"+i));
        }

        // 前序遍历
        System.out.println("前序遍历：");
        binaryTree.preTraversal();
        // 中序遍历
        System.out.println("中序遍历：");
        binaryTree.infixTraversal();
        // 后序遍历
        System.out.println("后序遍历：");
        binaryTree.postTraversal();

        //快速查找二叉树中的元素
        System.out.println("查找节点为 2 的元素:"+binaryTree.get(binaryTree.getRoot(), 2));

        //查询二叉树的最大深度
        System.out.println("二叉树的最大深度:"+binaryTree.maxDep(binaryTree.getRoot()));
    }

}