java实现二叉树的遍历（递归和非递归）

刺骨的言语ヽ痛彻心扉 2022-05-30 07:20 162阅读 0赞

源码地址：  
[https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/TreeInfo.java][https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_TreeInfo.java]

现有一颗如下图所示的二叉树：

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

其遍历的各种方式如下：

![这里写图片描述][70 1]  
![这里写图片描述][70 2]

构造一颗如下图所示的二叉树，用java实现其前序，中序，后序遍历

![这里写图片描述][70 3]

注意二叉树节点的定义如下：

public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    
        TreeNode(int x) {
            val = x;
        }
    }

递归实现：

// 用递归的方法进行先序遍历
        public void qinaxuDigui(TreeNode treeNode) {
            qianxuNumList.add(treeNode.val);
            if (treeNode.left != null) {
                qinaxuDigui(treeNode.left);
            }
            if (treeNode.right != null) {
                qinaxuDigui(treeNode.right);
            }
        }
    
        // 用递归的方法进行中序遍历
        public void zhongxuDigui(TreeNode treeNode) {
            if (treeNode.left != null) {
                zhongxuDigui(treeNode.left);
            }
            zhongxuNumList.add(treeNode.val);
            if (treeNode.right != null) {
                zhongxuDigui(treeNode.right);
            }
        }
    
        // 用递归的方法进行后序遍历
        public void houxuDigui(TreeNode treeNode) {
            if (treeNode.left != null) {
                houxuDigui(treeNode.left);
            }
            if (treeNode.right != null) {
                houxuDigui(treeNode.right);
            }
            houxuNumList.add(treeNode.val);
        }

非递归实现：

// 用非递归的方法进行先序遍历
        public void qinaxuFeiDigui(TreeNode treeNode) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (treeNode != null || !stack.isEmpty()) {
                while (treeNode != null) {
                    qianxuNumList.add(treeNode.val);
                    stack.push(treeNode);
                    treeNode = treeNode.left;
                }
                if(!stack.isEmpty()){
                    treeNode = stack.pop();
                    treeNode = treeNode.right;
                }
            }
        }
    
        // 用非递归的方法进行中序遍历
        public void zhongxuFeiDigui(TreeNode treeNode) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (treeNode != null || !stack.isEmpty()) {
                while (treeNode != null) {
                    stack.push(treeNode);
                    treeNode = treeNode.left;
                }
                if (!stack.isEmpty()) {
                    treeNode = stack.pop();
                    zhongxuNumList.add(treeNode.val);
                    treeNode = treeNode.right;
                }
            }
        }
    
        // 用非递归的方法进行后序遍历
        public void houxuFeiDigui(TreeNode treeNode) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (treeNode != null || !stack.isEmpty()) {
                while (treeNode != null) {
                    stack.push(treeNode);
                    treeNode = treeNode.left;
                }
                boolean tag = true;
                TreeNode preNode = null;  // 前驱节点
                while (!stack.isEmpty() && tag == true) {
                    treeNode = stack.peek();
                    if (treeNode.right == preNode) { // 之前访问的为空节点或是栈顶节点的右子节点
                        treeNode = stack.pop();
                        houxuNumList.add(treeNode.val);
                        if (stack.isEmpty()) {
                            return;
                        } else {
                            preNode = treeNode;
                        }
                    } else {
                        treeNode = treeNode.right;
                        tag = false;
                    }
                }
            }
        }

运行结果如下：

![这里写图片描述][70 4]

[https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_TreeInfo.java]: https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/TreeInfo.java
[70]: /images/20220530/f7ffb3476bf3447a99fbb81357fe448e.png
[70 1]: /images/20220530/31ef7d9486cb4cf2bb857c776defabf0.png
[70 2]: /images/20220530/5c3a78906e8b47b492abd99dcc670b05.png
[70 3]: /images/20220530/52731f4ef80441dd97065a713715c76d.png
[70 4]: /images/20220530/e6764d9d1b6c4c25bb019785189570f5.png