数据结构---二叉树

二叉树的举例

遍历

广度优先遍历

广度优先遍历（Breadth-first-order）：尽可能先访问距离根最近的节点，也称为层序遍历

练习

leetCode102

思路

/*
                1
              /   \
             2     3
           /   \  /  \
          4    5 6    7
          头[]尾
          1 2 3 4 5 6 7
*/

实现

public class E01Leetcode102 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4),
            2,
                new TreeNode(5)),
        1,
                 new TreeNode(new TreeNode(6),
            3,
                 new TreeNode(7))
        );
​
        System.out.println(testMethod(root));
        Queue<TreeNode> queue = new LinkedList<>();
    }
    public static List<List<TreeNode>> testMethod(TreeNode root){
        if(root == null){
            return null;
        }
        List<List<TreeNode>> list = new ArrayList<>();
        LinkedListQueue<TreeNode> queue = new LinkedListQueue();
        queue.offer(root);
        int index = 1;
        while (!queue.isEmpty()){
            int temp = 0;
            List<TreeNode> leve = new ArrayList<>();
            for(int i = 0; i < index; i++){
                TreeNode n = queue.poll();
                leve.add(n);
                if(n.left != null){
                    queue.offer(n.left);
                    temp++;
                }
                if(n.right != null){
                    queue.offer(n.right);
                    temp++;
                }
            }
            index = temp;
            list.add(leve);
        }
        return list;
    }
}

深度优先遍历

规则

1.深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点）

前序遍历：先访问该节点，然后是左子树，最后是右子树

中序遍历：先访问左子树，然后是该节点，最后是右子树

后序遍历：先访问左子树，然后是右子树，最后是该节点

实现

前序遍历

LinkedList<TreeNode> list = new LinkedList();
TreeNode curr = root;
​
while(curr != null || !list.isEmpty){
    if(curr != null){
        System.out.println(curr.val);
        list.push(curr);
        curr = curr.left;
    }else{
        TreeNode pop = list.pop();
        curr = pop.left
    }
}

中序遍历

LinkedList<TreeNode> list = new LinkedList();
TreeNode curr = root;
​
while(curr != null || !list.isEmpty){
    if(curr != null){
        list.push(curr);
        curr = curr.left;
    }else{
        TreeNode pop = list.pop();
        curr = pop.left
        System.out.println(pop.val);
    }
}

后续遍历

    static void preOrderEst2(TreeNode node){
        TreeNode curr = node;
        LinkedList<TreeNode> list = new LinkedList<>();
        TreeNode pop = null;
        while(curr != null || !list.isEmpty()){
            if(curr != null){
                list.push(curr);
                curr = curr.left;
            }else{
                TreeNode peek = list.peek();
                if(peek.right == null || pop == peek.right){
                    pop = list.pop();
                    System.out.println("回" + pop.val);
                }else {
                    curr = peek.right;
                }
            }
        }
    }

同时解决所有深度优先遍历

    static void preOrderEst3(TreeNode node){
        TreeNode curr = node;
        LinkedList<TreeNode> list = new LinkedList<>();
        TreeNode pop = null;
        while(curr != null || !list.isEmpty()){
            //待处理的左子树
            if(curr != null){
                list.push(curr);
                System.out.println("前" + curr.val);
                curr = curr.left;
            }else{
                //右子树为空的时候
                TreeNode peek = list.peek();
                if(peek.right == null){
                    System.out.println("中" + peek.val);
                    pop = list.pop();
                    System.out.println("后" + pop.val);
                //右子树处理完毕
                }else if(pop == peek.right){
                    pop = list.pop();
                    System.out.println("后" + pop.val);
                // 待处理的右子树
                }else{
                    System.out.println("中" + peek.val);
                    curr = peek.right;
                }
            }
        }
    }