二叉树 - fyzn12

二叉树的简单介绍

二叉树的定义

二叉树是(n>=0)个节点的有限集合，他或者(n==0)时为空树，或者（n>0时）由一个根节点及两颗互不相交的分别称为跟的左子树和右子树的二叉树组成。

2 二叉树的遍历

2.1 前序遍历

递归实现的算法分析

前序遍历二叉树的递归定义为：若二叉树为空树则遍历结束，否则
1. 访问根节点
2. 前序遍历根节点的左子树
3. 前序遍历根节点的右子树

———————————————— 算法实现 ————————————–

public class Tree {
    private class Bitree<T>{
        T data;
        Bitree lchild;
        Bitree rchild;
        public Bitree(T data,Bitree lchild,Bitree rchild){
            this.data = data;
            this.lchild = lchild;
            this.rchild = rchild;
        }
    }
    private void preorder(Bitree bt){
        //设置递归终止条件
        if (bt==null){
            return;
        }
        //输出 跟节点
        System.out.println(bt.data);
        //前序遍历左子树
        preorder(bt.lchild);
        //前序遍历右子树
        preorder(bt.rchild);
    }
}

2.2 中序遍历

递归实现的算法分析

中序遍历二叉树的递归定义为：若二叉树为空树则遍历结束，否则
1. 中序遍历根节点的左子树
2. 访问跟节点
3. 中序遍历根节点的右子树

———————————————— 算法实现 ————————————–

public void inorder(Bitree bt){
        //设置递归终止条件
        if (bt==null){
            return;
        }
        //1 中序遍历根节点的左子树
        inorder(bt.lchild);
        //2 访问根节点
        System.out.println(bt.data);
        //3 中序遍历根节点的右子树
        inorder(bt.rchild);

    }

2.3 后序遍历

递归实现的算法分析

后序遍历二叉树的递归定义为：若二叉树为空树则遍历结束，否则
1. 后序遍历根节点的左子树
2. 后序遍历根节点的右子树 3. 访问根节点

———————————————— 算法实现 ————————————–

public void postorder(Bitree bt) {
        //递归终止条件
        if (bt == null) {
            return;
        }
        //后序遍历根节点的左子树
        postorder(bt.lchild);
        //后序遍历根节点的右子树
        postorder(bt.rchild);
        //访问根节点
        System.out.println(bt.data);

    }

2.4 二叉树非递归遍历

递归算法简洁精炼、可读性好、易读懂，但其执行效率较低；

2.4.1 前序遍历非递归算法实现

思想：从二叉树的根结点开始，沿左子树一直深入到最左下结点时止，在深入过程中访问遇到的所有结点，并把所遇到的结点的非空右结点孩子进栈；当左子树节点全部处理完之后，从栈顶退出当前最近访问过结点的右孩子，再按上述过程遍历该结点的右子树；如此反复，直到栈空时为止。

———————– 算法实现 ————————————–

  
    /**
     * @Param:
     * @description:非递归算法的前序遍历
     * @Return
     */
    public void nrpreorder(Bitree bt) {
        //定义存储遍历过程中结点的非空右孩子存储的栈
        Stack<Bitree> stack = new Stack<>();
		
       while(stack.size()>0 || bt != null){
            /*当左结点不为空时一直深入到最左下结点*/
            while (bt != null) {
                System.out.println(bt.data);//访问根节点
                if (bt.rchild != null) {
                    stack.push(bt.rchild);  //将右结点存入栈中
                }
                //继续搜索左结点
                bt = bt.lchild;
            }
            if (!stack.isEmpty()) {
                bt = stack.pop();
            }
        }
    }

2.4.2 中序遍历非递归算法实现

思想：沿左子树向下搜索过程中先将所遇结点进栈，待遍历完左子树返回时从栈中退出结点并访问，然后再遍历右子树。

———————– 算法实现 ————————————–

  
 public void nrinorder(Bitree bt){
        //定义存储遍历过程中结点的非空右孩子存储的栈
        Stack<Bitree> stack = new Stack<>();
        while(stack.size()>0 || bt != null){
            while (bt != null){
                stack.push(bt);
                bt = bt.lchild;
            }
            if (!stack.isEmpty()){
                bt = stack.pop();
                System.out.println(bt.data);
                bt = bt.rchild;
            }
        }
    }

具体实战：算法篇给定一个二叉树，返回它的中序遍历。

  
 public  List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        boolean check = true;
        while (stack.size()>0 || root != null){
            while (root != null){
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()){
                root = stack.pop();
                list.add(root.val);
                System.out.println(root.val);
                root = root.right;
            }
        }
        return list;
    }

2.4.3 后序遍历非递归算法实现

 
    public void nrpostorder(TreeNode root) {
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        //保存根节点的的值
        int val = root.val;
        stack1.push(root);
        while (!stack1.isEmpty()) {
            root = stack1.pop();
            if (root.right != null) {
                stack2.push(root.right);
            }
            if (root.left != null) {
                stack2.push(root.left);
            }
        }
        while (!stack2.isEmpty()) {
            System.out.print(stack2.pop().val);
        }
        System.out.println(val);

    }

3 二叉树的层次遍历

所谓层次遍历是指从二叉树的根结点开始从上到下逐层遍历该二叉树，在同一层中从左到右依次访问各个结点。
由层次遍历的定义可知，层次遍历是从根结点，开始访问，然后访问他的左孩子和右孩子…。即在访问完某个结点之后，一般不能马上访问他的左孩子和右孩子（除根结点等特殊情况外），需要把它的左右孩子信息保存起来。这种操作正好与队列的操作特点吻合，所以可以利用一个队列结构来实现层次遍历，其做法是：

首先将根结点入队列；
当队列不空，从队列中取出队头结点访问他，并在其左右结点非空时，把它的左孩子和右孩子结点一次入队列；

反复执行2.直到队列为空；

public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
    // write code here
    ArrayList<ArrayList<Integer>> result  = new ArrayList<>();
    if(root!=null){
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            Queue<TreeNode> que2 = new LinkedList<>();
            while(!que.isEmpty()){
                TreeNode tmp = que.poll();
                list.add(tmp.val);
                if(tmp.left!=null){
                    que2.offer(tmp.left);
                }      
                if(tmp.right!=null){
                     que2.offer(tmp.right);
                }
            } 
            result.add(list);   
            que = que2;
        }
    }
    return result;
}

4 平衡二叉树的判断

public int depth(TreeNode root){
        if(root == null) return 0;
        int left = depth(root.left);
        if(left == -1) return -1;
        int right = depth(root.right);
        if(right==-1)return -1;
        if(left - right < (-1) || left-right>1)return -1;
        else return 1+ (left>right?left:right);
    }
    public boolean IsBalanced_Solution(TreeNode root) {
        return depth(root)!=-1;
    }