数据结构—二叉树的前中后序非递归遍历及层序遍历

约定不等于承诺〃 2022-04-06 06:13 129阅读 0赞

## 数据结构—二叉树的前中后序非递归遍历及层序遍历 ##

之前已经写过一篇关于二叉树的文章,当时是用C语言实现了二叉树的建立以及前中后序递归遍历.  
递归有一个好处就是:实现代码非常简单,也容易看懂.但很多情况先,递归所消耗的资源是与其他方式相比是比较大的,所以几天就来说一下二叉树前中后序遍历的非递归写法(java实现)

**1.节点的数据结构:**

class TreeNode {
            private int data;
            private TreeNode leftChild;
            private TreeNode rightChild;
    
            public TreeNode() {
            }
    
            public TreeNode(int data) {
                this.data = data;
                leftChild = null;
                rightChild = null;
            }
    
            @Override
            public String toString() {
                return " " + data;
            }
        }

**2.非递归前中后遍历**

*  首先大概说一下思路,我们前面之所以用递归的方式去遍历二叉树,是因为递归时 函数调用的层次关系能够保证**记忆性**,即:如果是中序遍历,那么我们遍历完一个节点的左子树后还可以回到这个根节点,然后再去遍历这个节点的右子树.
 *  那么这样的规律我们对应的就能想到**栈**这个数据结构,对应的:在中序遍历时,先将一个节点压栈,在遍历完其左子树后,弹栈并遍历其右子树.下面是其代码实现

/**
         * 非递归前序遍历
         * @param root
         */
        public static void nonRecPreOrder(TreeNode root) {
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode node = root;
            while (node != null || stack.size() > 0) {
                if (node != null) {
                    System.out.print(node);
                    stack.push(node);
                    node = node.leftChild;
                } else {
                    node = stack.pop();
                    node = node.rightChild;
                }
            }
            System.out.println();
        }

方法的入参是二叉树的根节点,这里用Deque这个类来模拟栈(因为Stack这个类在java中已经不推荐使用了).  
先序遍历就是: 判断根节点是否为空,如果不为空,先输出该节点,并将其压栈,然后访问其左子树,接着重复上述的动作,直到一个节点为空时,弹栈(这时就回到了上一个节点),然后获取这个节点的右子树并继续重复开始的动作.在右子树也遍历完之后,节点就回到了该节点(作为左孩子)的双亲节点,然后继续遍历,直到栈空,整颗二叉树被遍历

/**
         * 非递归中序遍历
         * @param root
         */
        public static void nonRecInOrder(TreeNode root) {
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode node = root;
            while (node != null || stack.size() > 0) {
                //存在左子树
                if (node != null) {
                    stack.push(node);
                    node = node.leftChild;
                    //栈非空
                } else {
                    node = stack.pop();
                    System.out.print(node);
                    node = node.rightChild;
                }
            }
            System.out.println();
        }

中序遍历其实和前序遍历差不多,只是输出节点数据的顺序变了一下,即:我们先将节点压栈至最左下处,然后在开始弹栈的时候才输出节点.

/**
         * 非递归后序遍历
         * @param root
         */
        public static void nonRecAftOrder(TreeNode root) {
            Deque<TreeNode> stack = new ArrayDeque<>();
            TreeNode p = root;
            TreeNode preRight = p;
            while (p != null) {
                //将非叶子左子树压栈
                for ( ; p.leftChild != null; p = p.leftChild) {
                    stack.push(p);
                }
                //当前节点没有右子树或者右子树已经输出
                while (p != null && (p.rightChild == null || p.rightChild == preRight)) {
                    System.out.print(p);
                    preRight = p;
                    if (stack.isEmpty()) {
                        return;
                    }
                    p = stack.pop();
                }
                //处理右子树
                stack.push(p);
                p = p.rightChild;
            }
            System.out.println();
        }

非递归后序遍历是比较麻烦的,我们用了额外的一个空间preRight来保存上一个访问的节点, 首先,从根节点开始,将左子树不为空的左子树节点压栈,在遇到最后一个节点后,若其只是一个叶子节点,那么就直接输出然后弹栈返回到上一个节点就OK了,但如果这个没有左子树的节点有右子树呢?那么继续将其压栈,并继续探索其右子树. 紧接着,如果其右子树探索完了,会是什么情况呢? 这个时候preRight 就会保存这个遍历过的右子树节点,然后回到上一个节点,进入内层while循环体就会判断 p.rightChild == preRight ,这就意味着该节点的右子树已经遍历过了,所以输出该节点,然后弹栈到上一个节点.继续找上一个节点的右子树

**3.二叉树的层序遍历**

/**
         * 二叉树的层序遍历
         * @param root
         */
        public static void levelTravel(TreeNode root) {
            Deque<TreeNode> queue = new ArrayDeque<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                System.out.print(node.data + " ");
                if (node.leftChild != null) {
                    queue.offer(node.leftChild);
                }
                if (node.rightChild != null) {
                    queue.offer(node.rightChild);
                }
            }
        }

这里依旧使用了Deque这个类,不过这里可不是表示栈了,而是使用队列.  
其实层序遍历很好理解,就是:将根节点入队后,只要队不为空,就取出队首元素,输出之后,将其非空左子树和非空右子树也如队.这样就可以按层次将二叉树所有节点遍历一遍