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

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

代码

遍历该树

这里写图片描述

  1. package com.uj.nsnc.test;
  3. import org.junit.Test;
  5. import java.util.Stack;
  7. public class BinaryTreeTravel { 
  9.     class Node{
  11.         public Node left;
  12.         public Node right;
  13.         public int value;
  15.         Node(Node left, Node right, int value) {
  16.             this.left = left;
  17.             this.right = right;
  18.             this.value = value;
  19.         }
  20.     }
  22.     @Test
  23.     public void testBinaryTreeTravel(){
  25.         Node node4 = new Node(null,null,2);
  26.         Node node5 = new Node(null,null,1);
  27.         Node node3 = new Node(null, node5, 3);
  28.         Node node2 = new Node(null, node4, 2);
  29.         Node node1 = new Node(node2, node3, 1);
  31.         PreOrderTravel(node1);
  32.         PreOrderTravelByStack(node1);
  33.     }
  35.     /*=== 先序遍历 - 递归实现==*/
  36.     private void PreOrderTravel(Node tree){
  37.         if (tree == null) {
  38.             return;
  39.         }
  40.         PreOrderTravel(tree.left);
  41.         System.out.println(tree.value);
  42.         PreOrderTravel(tree.right);
  43.     }
  44.     /*==== 先序遍历 - 非递归实现===*/
  45.     private void PreOrderTravelByStack(Node tree){
  46.         if(tree==null)
  47.             return;
  48.         Node temp = tree;
  49.         Stack<Node> stack = new Stack<>();
  50.         while (!stack.empty() || temp!=null) {
  51.             /*====左子树压入栈===*/
  52.             while (temp != null) {
  53.                 stack.push(temp);
  54.                 temp = temp.left;
  55.             }
  56.             Node node = stack.pop();
  57.             System.out.println(node.value);
  58.             /*=== 当前节点的右子树 ===*/
  59.             temp = node.right;
  60.         }
  61.     }
  62. }

分析

递归和非递归相似点？

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

为什么是栈？

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

发表评论

表情：
评论列表 （有 0 条评论，271人围观）

还没有评论，来说两句吧...

相关阅读