递归和非递归实现二叉树前序遍历

本文主要是介绍递归和非递归实现二叉树前序遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.前序遍历就是根、左、右，按着这个顺序，先说递归实现

//创建Node节点

public class Node {private int data;  private Node left;private Node right;public Node(int data, Node left, Node right){  this.data = data;  this.left = left;  this.right = right;  } public int getData(){return this.data;}public Node getLeft(){return this.left;}public Node getRight(){return this.right;}
}

//初始化数据public static Node init(){Node J = new Node(8, null, null);  Node H = new Node(4, null, null);  Node G = new Node(2, null, null);  Node F = new Node(7, null, J);  Node E = new Node(5, H, null);  Node D = new Node(1, null, G);  Node C = new Node(9, F, null);Node B = new Node(3, D, E);  Node A = new Node(6, B, C);  return A;  //返回根节点  
}

//递归实现public static void preOrder(Node root){list.add(root.getData());if(root.getLeft() != null) preOrder(root.getLeft());if(root.getRight() != null) preOrder(root.getRight());}

//然后调用

static ArrayList<Integer> list = new ArrayList<Integer>();public static void main(String[] args) {//递归实现Node node = init();preOrder(node);System.out.println(list.toString());	
}

2.非递归的使用，是将使用栈来存储的，先进后出，后劲先出。

/*** 非递归实现二叉树的前序遍历，* @param root*/public static ArrayList<Integer> preOrderNot(Node root){Stack<Node> stack = new Stack<Node>();ArrayList<Integer> list2 = new ArrayList<Integer>();if (root == null) {return list2;}stack.push(root);while (!stack.isEmpty()) {Node current = stack.pop();//出队list2.add(current.getData());//加入到list中if(current.getRight() != null) stack.push(current.getRight());//右子树入队if(current.getLeft() != null) stack.push(current.getLeft());//左子树入队}return list2;
	}

//调用

public static void main(String[] args) {		//非递归实现System.out.println(preOrderNot(node).toString());
}

这篇关于递归和非递归实现二叉树前序遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---