树的遍历【先序遍历】- 递归和非递归实现

太过爱你忘了你带给我的痛 2022-05-12 06:12 211阅读 0赞

## 代码 ##

#### 遍历该树 ####

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

package com.uj.nsnc.test;
    
    import org.junit.Test;
    
    import java.util.Stack;
    
    public class BinaryTreeTravel { 
    
        class Node{
    
            public Node left;
            public Node right;
            public int value;
    
            Node(Node left, Node right, int value) {
                this.left = left;
                this.right = right;
                this.value = value;
            }
        }
    
        @Test
        public void testBinaryTreeTravel(){
    
            Node node4 = new Node(null,null,2);
            Node node5 = new Node(null,null,1);
            Node node3 = new Node(null, node5, 3);
            Node node2 = new Node(null, node4, 2);
            Node node1 = new Node(node2, node3, 1);
    
            PreOrderTravel(node1);
            PreOrderTravelByStack(node1);
        }
    
        /*=== 先序遍历 - 递归实现==*/
        private void PreOrderTravel(Node tree){
            if (tree == null) {
                return;
            }
            PreOrderTravel(tree.left);
            System.out.println(tree.value);
            PreOrderTravel(tree.right);
        }
        /*==== 先序遍历 - 非递归实现===*/
        private void PreOrderTravelByStack(Node tree){
            if(tree==null)
                return;
            Node temp = tree;
            Stack<Node> stack = new Stack<>();
            while (!stack.empty() || temp!=null) {
                /*====左子树压入栈===*/
                while (temp != null) {
                    stack.push(temp);
                    temp = temp.left;
                }
                Node node = stack.pop();
                System.out.println(node.value);
                /*=== 当前节点的右子树 ===*/
                temp = node.right;
            }
        }
    }

## 分析 ##

递归和非递归`相似点`？

1.  递归使用`函数栈`
2.  非递归方式使用一个`栈`

为什么是`栈`？

1.  遍历一个树，要实现可以回到遍历过的 `节点`。  
    
    
     *  再次回来是为了，完整遍历`当前节点` 的左右子树
2.  递归方式会回到一个点`3次`， 手动栈 是 `两次`
3.  此外，`3次` 可以用在很多场景。

[70]: /images/20220512/88c930cba9bc42c78c5d8c6e148673c1.png