二叉树的深度优先遍历与广度优先遍历

喜欢ヅ旅行 2023-02-19 15:20 14阅读 0赞

二叉树的遍历是非常常见的面试题，如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历（前中后序遍历都是深度优先遍历的思想，即DFS）。其中，前中后序，表示的是节点与它的左右子树节点遍历打印的先后顺序。

*  前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
 *  中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
 *  后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

![20200716164830727.png][]

实际上，二叉树的前、中、后序遍历就是一个递归的过程。比如，前序遍历，其实就是先打印根节点，然后再递归地打印左子树，最后递归地打印右子树。

### 二叉树前中后序遍历的递归写法 ###

写递归代码的关键，就是看能不能写出递推公式，而写递推公式的关键就是，如果要解决问题 A，就假设子问题 B、C 已经解决，然后再来看如何利用 B、C 来解决 A。所以，我们可以把前、中、后序遍历的递推公式都写出来。

//前序遍历的递推公式：
    preOrder(r) = print r->preOrder(r->left)->preOrder(r->right)
    
    //中序遍历的递推公式：
    inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
    
    //后序遍历的递推公式：
    postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r

有了递推公式，代码写起来就简单多了，以下为二叉树前中后序遍历的递归写法代码。

public class BinaryTree<T extends Comparable<T>> { 
    
        /** * 根结点 */
        private TreeNode<T> root;
    
        boolean isEmpty() { 
            return root == null;
        }
        
     	T getValue(TreeNode<T> treeNode) { 
            return treeNode == null ? null : treeNode.getData();
        }
    
        public TreeNode<T> getRoot() { 
            return root;
        }
    
        public void setRoot(TreeNode<T> root) { 
            this.root = root;
        }
    
        public boolean isExist(T data) { 
            if (data == null) { 
                throw new IllegalArgumentException("..");
            }
            if (isEmpty()) { 
                throw new IllegalArgumentException("..");
            }
            return find(getRoot(), data) != null;
        }
    
        /** * 查找指定数据所在的节点 */
        public TreeNode<T> find(TreeNode<T> treeNode, T data) { 
            if (data == null) { 
                throw new IllegalArgumentException("..");
            }
            if (treeNode == null) { 
                return null;
            }
            if (treeNode.getData().equals(data)) { 
                return treeNode;
            }
            TreeNode<T> leftNode = find(treeNode.getLeft(), data);
            TreeNode<T> rightNode = find(treeNode.getRight(), data);
            return leftNode == null ? rightNode : leftNode;
        }
    
        /** * 前序遍历二叉树 * 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。 */
        void preOrderTraverse(TreeNode<T> treeNode) { 
            if (treeNode == null) { 
                return;
            }
            System.out.print(treeNode.getData() + ",");
            if (treeNode.getLeft() != null) { 
                preOrderTraverse(treeNode.getLeft());
            }
            if (treeNode.getRight() != null) { 
                preOrderTraverse(treeNode.getRight());
            }
        }
    
        /** * 中序遍历二叉树，根左右 * 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。 */
        void inOrderTraverse(TreeNode<T> treeNode) { 
            if (treeNode == null) { 
                return;
            }
            if (treeNode.getLeft() != null) { 
                inOrderTraverse(treeNode.getLeft());
            }
            System.out.print(treeNode.getData() + ",");
            if (treeNode.getRight() != null) { 
                inOrderTraverse(treeNode.getRight());
            }
        }
    
        /** * 后序遍历二叉树 * 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。 */
        void postOrderTraverse(TreeNode<T> treeNode) { 
            if (treeNode == null) { 
                return;
            }
            if (treeNode.getLeft() != null) { 
                postOrderTraverse(treeNode.getLeft());
            }
            if (treeNode.getRight() != null) { 
                postOrderTraverse(treeNode.getRight());
            }
            System.out.print(treeNode.getData() + ",");
        }
    
    
        /** * 求二叉树的深度 * 深度 = MAX(左子树深度, 右子树深度） + 1 */
        int getTreeDepth(TreeNode<T> treeNode) { 
            if (treeNode == null) { 
                return 0;
            }
            int leftDepth = 0, rightDepth = 0;
            if (treeNode.getLeft() != null) { 
                leftDepth = getTreeDepth(treeNode.getLeft());
            } else if (treeNode.getRight() != null) { 
                rightDepth = getTreeDepth(treeNode.getRight());
            }
            return  (leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1);
        }
    }

### 二叉树前中后序遍历的非递归写法 ###

递归与非递归转换的原理，首先，有一点是明确的：**非递归写法一定会用到栈**。

非递归前序遍历过程的过程如下：

1.  先将根节点入栈
2.  访问栈顶节点，将其出栈并打印
3.  如果根节点存在右孩子，则将右孩子入栈
4.  如果根节点存在左孩子，则将左孩子入栈（注意一定是右孩子先入栈，然后左孩子入栈）
5.  重复2-4

/** * 前序遍历二叉树,非递归写法 根左右 * 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。 */
    void preOrderTraverseIterative(TreeNode<T> treeNode) { 
        if (treeNode == null) { 
            return;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        stack.push(treeNode);
        while (!stack.isEmpty()) { 
            TreeNode<T> node = stack.peek();
            System.out.print(node.getData() + ",");
            stack.pop();
            if (node.getRight() != null) { 
                stack.push(node.getRight());
            }
            if (node.getLeft() != null) { 
                stack.push(node.getLeft());
            }
        }
    }

中序遍历的递归定义：先左子树，后根节点，再右子树。如何写非递归代码呢？一句话：让代码跟着思维走。我们的思维是什么？思维就是中序遍历的路径。假设，你面前有一棵二叉树，现要求你写出它的中序遍历序列。如果你对中序遍历理解透彻的话，你肯定先找到左子树的最下边的节点。

非递归中序遍历过程的过程如下：

1.  先将根节点入栈
2.  将当前节点的所有左孩子入栈，直到左孩子为空
3.  访问栈顶元素，如果栈顶元素存在右孩子，则继续第2步
4.  重复第2、3步，直到栈为空并且所有的节点都被访问

/** * 中序遍历二叉树, 非递归写法, 左根右（入栈时就是右根左） * 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。 根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点， 直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下： 对于任一结点P， 1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理； 2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子； 3)直到P为NULL并且栈为空则遍历结束 */
    void inOrderTraverseIterative(TreeNode<T> treeNode) { 
        if (treeNode == null) { 
            return;
        }
        TreeNode<T> node = treeNode;
        Stack<TreeNode<T>> stack = new Stack<>();
        while (!stack.isEmpty() || node != null) { 
            while (node != null) { 
                stack.push(node);
                node = node.getLeft();
            }
            if (!stack.isEmpty()) { 
                node = stack.peek();
                System.out.print(node.getData() + ",");
                stack.pop();
                node = node.getRight();
            }
        }
    }

非递归后序遍历过程的过程如下：

1.  根节点入栈
2.  得到栈顶元素的值，先不访问，判断栈顶元素是否存在右孩子，如果存在并且没有被访问，则先将右孩子入栈再将左孩子（如果有）入栈，否则，就访问栈顶元素
3.  重复1-2两步

/** * 后序遍历二叉树 非递归写法 左右根 * 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。 * * 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子， * 则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。 * 若非上述两种情况， * 则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点 * 前面被访问。 */
    void postOrderTraverseIterative(TreeNode<T> treeNode) { 
        if (treeNode == null) { 
            return;
        }
        Stack<TreeNode<T>> stack = new Stack<>();
        stack.push(treeNode);
        TreeNode<T> preNode = null, currentNode = null;
        while (!stack.isEmpty()) { 
            currentNode = stack.peek();
            //如果没有子节点，则可以访问
            boolean noChild = (currentNode.getLeft() == null && currentNode.getRight() == null);
            boolean rightChildAccessed = (preNode != null && preNode == currentNode.getRight());
            boolean leftChildAccessedWithoutRightChild = (preNode != null && preNode == currentNode.getLeft() && currentNode.getRight() == null);
    
            if (noChild || rightChildAccessed || leftChildAccessedWithoutRightChild) { 
                System.out.print(currentNode.getData() + ",");
                preNode = currentNode;
                stack.pop();
            } else { 
                if (currentNode.getRight() != null) { 
                    stack.push(currentNode.getRight());
                }
                if (currentNode.getLeft() != null) { 
                    stack.push(currentNode.getLeft());
                }
            }
        }
    }

### 二叉树层序遍历 ###

**与树的前中后序遍历的DFS思想不同，层次遍历用到的是BFS思想。一般DFS用递归去实现（也可以用栈实现），而BFS需要用队列去实现**。层次遍历要求每一层都是从左到右的遍历输出，借助于一个队列。先将根节点入队，当前节点是队头节点，将其出队并访问，如果当前节点的左节点不为空将左节点入队，如果当前节点的右节点不为空将其入队。所以出队顺序也是从左到右依次出队。

层次遍历的步骤是：

1.  对于不为空的结点，先把该结点加入到队列中
2.  从队中拿出结点，如果该结点的左右结点不为空，就分别把左右结点加入到队列中
3.  重复以上操作直到队列为空

以下为层序遍历的示例代码，Java中Queue是一个接口，实现由LinkedList实现。

/** * 层序遍历二叉树，用到了FIFO的队列 */
    void levelOrderTraverse(TreeNode<T> treeNode) { 
        if (treeNode == null) { 
            return;
        }
        LinkedList<TreeNode<T>> queue = new LinkedList<>();
        //将根节点入队
        queue.offer(treeNode);
        while (!queue.isEmpty()) { 
        	//队头元素出队并访问
            TreeNode<T> node = queue.poll();
            System.out.print(node.getData() + ",");
            //当前元素的左孩子不为空，则入队之
            if (node.getLeft() != null) { 
                queue.offer(node.getLeft());
            }
            //当前元素的右孩子不为空，则入队之
            if (node.getRight() != null) { 
                queue.offer(node.getRight());
            }
        }
    }

### 根据深度优先遍历结果确定一棵二叉树 ###

先说结论，根据二叉树的前序及中序遍历结果、中序及后序遍历结果都可以确定唯一一棵二叉树。

以前序 + 中序遍历可以唯一确定一棵二叉树为例，先给两个序列：

*  前序序列：1，2，4，8，5，3，6，7
 *  中序序列：8，4，2，5，1，6，3，7

下面来分析下：

1.  前序序列中的第一个肯定是根节点，知道了1是根节点后，我们去中序序列中找到1
2.  中序序列中1前面的 8，4，2，5这4个肯定是左子树，6，3，7是右子树。接下来关键的一步要想明白，我们要找到前序序列中的左子树的部分  
    ，这部分就是左子树的前序序列找到了我们就能递归的下去。
3.  由于我们在中序序列中知道了左子树有4个节点，那么我们根据前序序列的特性就可以得知。在根节点1后面的4个节点就是我们的左子树了。综上可以得到左子树的前序序列是：2，4，8，5。左子树的中序序列是：8，4，2，5。
4.  重复上面的步骤

/** * 前序 + 中序遍历可以唯一确定一棵二叉树 */
    static <T> TreeNode<T> createBinaryTreeByPreInOrder(List<T> preOrderDataList, List<T> inOrderDataList) { 
        if (preOrderDataList == null || inOrderDataList == null) { 
            throw new IllegalArgumentException("...");
        }
        if (preOrderDataList.size() != inOrderDataList.size()) { 
            throw new IllegalArgumentException("...");
        }
        if (preOrderDataList.size() == 0) { 
            return null;
        }
        T rootData = preOrderDataList.get(0);
        TreeNode<T> root = new TreeNode<>(rootData);
        int inOrderRootIndex = inOrderDataList.indexOf(rootData);
    
        List<T> leftChildInOrderList = inOrderDataList.subList(0, inOrderRootIndex);
        List<T> leftChildPreOrderList = preOrderDataList.subList(1, inOrderRootIndex + 1);
    
        List<T> rightChildInOrderList = inOrderDataList.subList(inOrderRootIndex + 1, inOrderDataList.size());
        List<T> rightChildPreOrderList = preOrderDataList.subList(inOrderRootIndex + 1, preOrderDataList.size());
    
        root.left = createBinaryTreeByPreInOrder(leftChildPreOrderList, leftChildInOrderList);
        root.right = createBinaryTreeByPreInOrder(rightChildPreOrderList, rightChildInOrderList);
    
        return root;
    }
    
    /** * 后序 + 中序遍历可以唯一确定一棵二叉树 */
    static <T> TreeNode<T> createBinaryTreeByPostInOrder(List<T> postOrderDataList, List<T> inOrderDataList) { 
    
        if (postOrderDataList == null || inOrderDataList == null) { 
            throw new IllegalArgumentException("...");
        }
        if (postOrderDataList.size() != inOrderDataList.size()) { 
            throw new IllegalArgumentException("...");
        }
        if (postOrderDataList.size() == 0) { 
            return null;
        }
        T rootData = postOrderDataList.get(postOrderDataList.size() - 1);
        int rootNodeInOrderIndex = inOrderDataList.indexOf(rootData);
        if (rootNodeInOrderIndex < 0) { 
            throw new IllegalArgumentException("...");
        }
        TreeNode<T> root = new TreeNode<>(rootData);
        List<T> leftChildInOrderList = inOrderDataList.subList(0, rootNodeInOrderIndex);
        List<T> leftChildPostOrderList = postOrderDataList.subList(0, rootNodeInOrderIndex);
    
        List<T> rightChildInOrderList = inOrderDataList.subList(rootNodeInOrderIndex + 1, inOrderDataList.size());
        List<T> rightChildPostOrderList = postOrderDataList.subList(rootNodeInOrderIndex, postOrderDataList.size() - 1);
    
        root.left = createBinaryTreeByPostInOrder(leftChildPostOrderList, leftChildInOrderList);
        root.right = createBinaryTreeByPostInOrder(rightChildPostOrderList, rightChildInOrderList);
    
        return root;
    }

[20200716164830727.png]: https://img-blog.csdnimg.cn/20200716164830727.png