二叉树先序、中序、后序、层次遍历递归以及非递归算法实现

た入场券 2021-10-15 05:29 366阅读 0赞

最近写了一下关于二叉树的三种遍历算法的递归以及非递归实现，以及层次遍历算法实现

先序遍历递归实现

/** * 先序遍历，根》左》右 */
        public void beforeTraverse(TreeNode root) { 
            if (root == null) { 
                return;
            }
            System.out.print(root.val + "->");
            if (root.left != null) { 
                beforeTraverse(root.left);
            }
            if (root.right != null) { 
                beforeTraverse(root.right);
            }
        }

先序遍历非递归实现

/** * 通过栈遍历二叉树，先序（思想就是：入栈即记录） */
        public List<String> beforeTraverseByStack(TreeNode root) { 
            List<String> list = new ArrayList<>(); // 接受结果
            if (root == null) { 
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            // 先序遍历（根 》左 》右），先遍历所有左结点，将他们放到栈中
            while (root != null) { 
                // 遍历的所有左结点都要加入到结果集中
                list.add(root.value);
                stack.push(root);
                root = root.left;
            }
            while (!stack.empty()) { 
                TreeNode node = stack.pop();
                if (node.right != null) { 
                    // 入栈及记录
                    list.add(node.right.value);
                    TreeNode push = stack.push(node.right);
                    while (push.left != null) { 
                        // 入栈及记录
                        list.add(push.left.value);
                        stack.push(push.left);
                        push = push.left;
                    }
                }
            }
            return list;
        }

中序遍历递归实现

/** * 中序遍历，左》根》右 */
        public void middleTraverse(TreeNode root) { 
            if (root.left != null) { 
                middleTraverse(root.left);
            }
            System.out.print(root.val + "->");
            if (root.right != null) { 
                middleTraverse(root.right);
            }
        }

中序遍历非递归实现

/** * 通过栈遍历二叉树，中序（思想就是：出栈即记录） */
        public List<String> middleTraverseByStack(TreeNode root) { 
            List<String> list = new ArrayList<>(); // 接受结果
            if (root == null) { 
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            // 中序遍历（左 》根 》右），先遍历所有左结点，将他们放到栈中
            while (root != null) { 
                stack.push(root);
                root = root.left;
            }
            while (!stack.empty()) { 
                // 出栈及记录
                TreeNode node = stack.pop();
                list.add(node.value);
                if (node.right != null) { 
                    TreeNode push = stack.push(node.right);
                    while (push.left != null) { 
                        stack.push(push.left);
                        push = push.left;
                    }
                }
            }
            return list;
        }

后序遍历递归实现

/** * 后序遍历，左》右》根 */
        public void afterTraverse(TreeNode root) { 
            if (root.left != null) { 
                afterTraverse(root.left);
            }
            if (root.right != null) { 
                afterTraverse(root.right);
            }
            System.out.print(root.val + "->");
        }

后序遍历非递归实现

/** * 通过栈遍历二叉树，后序 */
        public List<String> afterTraverseByStack(TreeNode root) { 
            List<String> list = new ArrayList<>(); // 接受结果
            if (root == null) { 
                return list;
            }
            Stack<TreeNode> stack = new Stack<>();
            Stack<TreeNode> stack2 = new Stack<>(); //这个栈用于保存二叉树元素结点（按顺序，根+右+左）
            // 后序遍历（左 》右 》根），先将所有右结点加入到两个栈中
            while (root != null) { 
                stack.push(root);
                stack2.push(root);
                root = root.right;
            }
            while (!stack.empty()) { 
                TreeNode pop = stack.pop();
                if (pop.left != null) { 
                    TreeNode push = stack.push(pop.left);
                    stack2.push(pop.left);
                    while (push.right != null) { 
                        stack.push(push.right);
                        stack2.push(push.right);
                        push = push.right;
                    }
                }
            }
    
            // 将stack2中一个一个弹出，放到结果集中（这里就是利用了后序，倒着遍历的特点）
            while (!stack2.empty()) { 
                list.add(stack2.pop().value);
            }
            return list;
        }

层次遍历算法实现

/** * 层次（顺序）遍历，一层一层，从左向右 * 需要引入队列这种数据结构，队列：先进先出，头进尾出 * 因为既需要找到一个结点的左结点又需要找到右结点 */
        public List<String> orderTraverse(TreeNode root) { 
            // 使用集合代替队列，先进先出（出队列就是移除第0个元素）
            List<TreeNode> list = new ArrayList<>();
            List<String> result = new ArrayList<>();    // 接受结果
            if (root == null) { 
                return result;
            }
            list.add(root);
            while (!list.isEmpty()) { 
                TreeNode node = list.remove(0);
                result.add(node.val);
                if (node.left != null) { 
                    list.add(node.left);
                }
                if (node.right != null) { 
                    list.add(node.right);
                }
            }
            return result;
        }

总的来说，非递归算法就是引入辅助数据结构栈（或者其他），利用他们特殊的结构先进后出（其他）的特点，完成按要求的遍历

关于树的很多算法都是由他们变形而来的，但还是需要灵活的转变思维才能解决相应的问题