二叉树的基本知识

二叉树的基本知识

二叉树的基本知识

二叉树基本种类

结点结点的度树的深度k满二叉树完全二叉树 二叉树的存储方式

顺序存储链式存储 二叉树三种遍历方式

前序遍历中序遍历后序遍历递归实现三种遍历迭代实现三种遍历

二叉树基本种类 结点

根结点，可以单独成树即该根结点没有孩子；也可以有孩子；
叶子结点简称叶子，又称终端结点，顾名思义，该结点不是根结点且没有孩子；
子结点如上图所示，子结点不是根结点且它有孩子。

结点的度

结点的度就是其孩子的个数，如上图，根结点度为2，子结点度为2，叶子结点度为0.

树的深度k

1.k>=1，树有几层，就有多深;
2.树的结点总数为 2 k 2^k 2k-1;
3.第k层的结点数为 2 k − 1 2^{k-1} 2k−1.

满二叉树

顾名思义，分两种情况：
1.该树只有根结点；
2.该树所有非叶子结点的度为2。

完全二叉树

完全二叉树定义为：
除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的结点都是处于左边。

二叉树的存储方式 顺序存储

所谓顺序存储就是存储在数组中，一段连续的内存地址，然后通过下标去索引目标结点。

链式存储

链式存储和双向链表差不多，首先创造一个结点对象，该对象有三个属性，分别是值，left指针，right指针

public class Node {
    int val;
    Node left;
    Node right;
    public  Node(){

    }
    public Node(int val, Node left, Node right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

二叉树三种遍历方式

前序遍历

前序遍历顺序为中左右：
上图使用前序遍历：12485367

中序遍历

中序遍历顺序为左中右：
上图使用中序遍历：84251637

后序遍历

后序遍历顺序为左右中：
上图使用后序遍历：84526731

递归实现三种遍历

1.写递归时一定别忘了递归终止条件；
2.递归的过程就是不断地进入下一层递归，当遇到终止条件，返回上一层，执行下一条语句，当该层语句执行完后也会返回上一层；
3.注意递归返回的位置；
4.可以看到递归的过程和进出栈类似，其实，递归的底层是栈实现的。

public class Ergodic {
    //前序遍历
    public ArrayList preReverse(Node root){
        ArrayList result = new ArrayList<>();
        preOrder(root,result);
        return result;//在java中引用类型的实参会被改动
    }
    public void preOrder(Node root,ArrayList result){
        if(root!=null) {
            result.add(root.val);//中
            preOrder(root.left, result);//左
            preOrder(root.right, result);//右
        }
    }
    //中序遍历
    public ArrayList midReverse(Node root){
        ArrayList res=new ArrayList<>();
        midOrder(root,res);
        return res;
    }
    public void midOrder(Node root,ArrayList res){
        if(root!=null){
            midOrder(root.left,res);//左
            res.add(root.val);//中
            midOrder(root.right, res);//右
        }
    }
    //后序遍历
    public ArrayList postReverse(Node root){
        ArrayList res=new ArrayList<>();
        midOrder(root,res);
        return res;
    }
    public void postOrder(Node root,ArrayList res){
        if(root!=null){
            postOrder(root.left,res);//左
            postOrder(root.right,res);//右
            res.add(root.val);//中
        }
    }
}

迭代实现三种遍历

1.使用递归算法可以实现二叉树三种遍历，而递归底层使用栈实现；因此我们可以直接使用栈来实现三种遍历；
2.栈的原理是后进先出，因此将后遍历的结点先push入栈中；当结点为空时，执行pop();
3.将push的结点用数组保存其数值。

public class Iteration {
    //前序遍历;入栈顺序：中右左
    public ArrayList preOrder(Node root){
        ArrayList res = new ArrayList<>();
        Stack stack=new Stack<>();
        if(root==null){
            return res;
        }
        stack.push(root);//中
        while(!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(node.val);
            if(node.right!=null){//右
                stack.push(node.right);
            }
            if(node.left!=null){//左
                stack.push(node.left);
            }
        }
        return res;
    }
    //中序遍历；入栈顺序：左，右
    public ArrayList midOrder(Node root){
        ArrayList res=new ArrayList<>();
        Stack stack =new Stack<>();
        if(root==null){
            return res;
        }
        Node node=root;
        while(node!=null||!stack.isEmpty()) {//当栈为空，node为空时，遍历结束
            if (node != null) {//将左孩子全部推进栈中
                stack.push(node);
                node = node.left;
            } else {
                node = stack.pop();
                res.add(node.val);
                node = node.right;//考虑右分支
            }
        }
        return res;
    }
    //后序遍历与前序遍历入栈顺序相反；入栈顺序：中，左，右，出栈顺序：中，右，左；翻转数组
    public ArrayList postOrder(Node root){
        ArrayList res=new ArrayList<>();
        Stack stack =new Stack<>();
        if(root==null){
            return res;
        }
        stack.push(root);//中
        while(!stack.isEmpty()) {
            Node node = stack.pop();
            res.add(node.val);
            if(node.left!=null){//左
                stack.push(node.left);
            }
            if(node.right!=null){//右
                stack.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
}