【数据结构与算法】十八二叉树遍历 DFS 深度优先迭代算法

水深无声 2022-07-20 15:27 186阅读 0赞

# **【数据结构与算法】十八 二叉树遍历 DFS 深度优先 迭代算法** #

# **DFS - Depth-First-Search** 迭代算法 #

栈是实现递归的最常用的结构，利用一个栈来记下尚待遍历的结点或子树，以备以后访问，可以将递归的深度优先遍历改为迭代的算法。

1.  非递归前序遍历：遇到一个结点，就访问该结点，并把此结点推入栈中，然后下降去遍历它的左子树。遍历完它的左子树后，从栈顶托出这个结点，并按照它的右链接指示的地址再去遍历该结点的右子树结构。  
    ![这里写图片描述][20160708235142350]
2.  非递归中序遍历：遇到一个结点，就把它推入栈中，并去遍历它的左子树。遍历完左子树后，从栈顶托出这个结点并访问之，然后按照它的右链接指示的地址再去遍历该结点的右子树。
    
    ![这里写图片描述][20160708235236330]
3.  非递归后序遍历：遇到一个结点，把它推入栈中，遍历它的左子树。遍历结束后，还不能马上访问处于栈顶的该结点，而是要再按照它的右链接结构指示的地址去遍历该结点的右子树。遍历遍右子树后才能从栈顶托出该结点并访问之。另外，需要给栈中的每个元素加上一个特征位，以便当从栈顶托出一个结点时区别是从栈顶元素左边回来的(则要继续遍历右子树)，还是从右边回来的(该结点的左、右子树均已周游)。特征为Left表示已进入该结点的左子树，将从左边回来；特征为Right表示已进入该结点的右子树，将从右边回来。
    
    ![这里写图片描述][20160708235253772]

# **Java实现** #

package com.cn.mark.algorithm.binarytree;
    
    
    import java.util.Stack;
    
    /**
     * 深度优先遍历 迭代算法 stack
     * 前
     * 中
     * 后
     */
    public class BSTDFSStack {
        
    
        TreeNode root = null;
    
        class TreeNode {
            int value;
            int position;
            TreeNode left = null, right = null;
    
            TreeNode(int value, int position) {
                this.value = value;
                this.position = position;
            }
        }
    
        /**
         * 暴露添加方法
         * @param value
         * @param position
         */
        public void add(int value, int position) {
            if (root == null) {
                root = new TreeNode(value, position);
            } else {
                add(value, position, root);
            }
        }
    
        /**
         * 内部add方法
         * @param value
         * @param position
         * @param node
         */
        private void add(int value, int position, TreeNode node) {
            if (node == null)
                throw new RuntimeException("treenode cannot be null");
            if (node.value == value)
                return; //ignore the duplicated value
            if (value < node.value) {
                if (node.left == null) {
                    node.left = new TreeNode(value, position);
                } else {
                    add(value, position, node.left);
                }
            } else {
                if (node.right == null) {
                    node.right = new TreeNode(value, position);
                } else {
                    add(value, position, node.right);
                }
            }
        }
    
        /**
         * 前序深度 遍历算法
         * @param node
         */
        private void preorder(TreeNode node) {
            Stack s = new Stack();
            TreeNode currentNode = root;
            while (currentNode != null) {
                System.out.print(currentNode.value);
                if (currentNode.right != null)
                    s.push(currentNode.right);
                if (currentNode.left != null)
                    currentNode = currentNode.left;
                else if (s.empty())
                    currentNode = null;
                else {
                    currentNode = (TreeNode) s.peek();
                    s.pop();
                }
    
            }
        }
    
        /**
         * 中序深度 遍历算法
         * @param node
         */
        private void midorder(TreeNode node) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (node != null) {
                while (node != null) {
                    if (node.right != null)
                        stack.push(node.right);// 当前节点右子入栈
                    stack.push(node);// 当前节点入栈
                    node = node.left;
                }
                node = stack.pop();
                while (!stack.empty() && node.right == null) {
                    System.out.print(node.value);
                    node = stack.pop();
                }
                System.out.print(node.value);
                if (!stack.empty())
                    node = stack.pop();
                else
                    node = null;
            }
        }
    
    
        /**
         * 后序深度 遍历算法
         * @param node
         */
        private void postorder(TreeNode node) {
            TreeNode q = node;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (node != null) {
                for (; node.left != null; node = node.left)// 左子树入栈
                    stack.push(node);
                while (node != null && (node.right == null || node.right == q)) {
       // 当前节点无右子或右子已经输出
                    System.out.print(node.value);
                    q = node;// 记录上一个已输出节点
                    if (stack.empty())
                        return;
                    node = stack.pop();
                }
                stack.push(node);// 处理右子
                node = node.right;
            }
        }
    
        public static void main(String[] args) {
            BSTDFSStack bst = new BSTDFSStack();
            int a[] = {
       3, 7, 8, 4, 2, 5, 9, 0, 6, 1};
            for (int i = 0; i < a.length; i++) {
                bst.add(a[i], i);
            }
    
            System.out.print("preorder :");
            bst.preorder(bst.root);
            System.out.println();
    
            System.out.print("midorder :");
            bst.midorder(bst.root);
            System.out.println();
    
            System.out.print("postorder :");
            bst.postorder(bst.root);
            System.out.println();
    
    
        }
    
    }

# **运行结果** #

![这里写图片描述][20160708233140238]

[20160708235142350]: /images/20220720/f419a385713b4f8291dc82effd2c056d.png
[20160708235236330]: /images/20220720/c823d6423109421185a821b544e3791f.png
[20160708235253772]: /images/20220720/9f5ccd5bec2845f0acf6a2c71a07f456.png
[20160708233140238]: /images/20220720/c07534887595450b9b3ef4093f93d9d4.png