二叉树——前序、中序、后序、序级遍历详解（递归非递归）

terry 2年前 (2023-09-27) 阅读数 66 #数据结构与算法

级别遍历

序级遍历。从名字就知道它是一层一层的。我们知道节点有一个左节点和一个右节点。每一层的通过都与左右节点有很大的关系。这意味着我们选择的数据结构不能单向钻取，但应该考虑平衡。所以我们决定使用队列来实现。

对于队列，先进先出。当根节点入队时，队列中最先出现的顺序在第二级左右（假设存在）。 第二层每次执行都会将添加到队列中，那么所有添加的节点都在第二层后面。
同样，假设开始pop并遍历第n层的节点，每个节点将左右两个节点推入。但队列是先进先出的。它将被放置在订单的末尾（下一级）。直到最后一个跳到n。 层，n+1层仍然整齐地排成一排。这实现了层序列的效果。

实现的代码也很容易理解：

public void cengxu(node t) {//层序遍历
	Queue<node> q1 = new ArrayDeque<node>();
	if (t == null)
		return;
	if (t != null) {
		q1.add(t);
	}
	while (!q1.isEmpty()) {
		node t1 = q1.poll();
		if (t1.left != null)
			q1.add(t1.left);
		if (t1.right != null)
			q1.add(t1.right);
		System.out.print(t1.value + " ");
	}
	System.out.println();
}

前中后序遍历（递归）

其实和dfs的思路类似。使用递归实现。前面详细介绍了递归算法。我们使用的三阶遍历使用相同的递归。大家都知道，递归是一个来回的过程。三阶遍历只是利用不同的片段来捕获递归中来回过程中的输出，从而达到前（中序和后序）遍历的结果。

预序递归

预序规则为根节点--->左子树--->右子树。在调用递归之前，我们对节点进行操作。预排序时，首先访问节点（出口）。左递归和右递归更喜欢左递归。 直至没有剩余结。会停止。访问顺序大致为：

public void qianxu(node t)// 前序递归 前序遍历：根结点 ---> 左子树 ---> 右子树
{
	if (t != null) {
		System.out.print(t.value + " ");// 当前节点
		qianxu(t.left);
		qianxu(t.right);
	}
}

顺序递归

有了先序的经验，我们可以很好地利用递归来实现顺序转换。按顺序遍历的规则是：左子树--->根节点--->右子树。所以我们访问节点的顺序必须改变。

等到递归是对于正好有两个子节点（没有子节点）的节点来说，来回移动到的过程。只需要访问左节点一次，访问根节点并访问右节点。就这些。
还有如果两边都有结。每个节点必须按顺序满足遍历规则。首先，我们从根开始访问左节点。当我们到达左节点时，左节点就变成是的子树，也必须满足的遍历要求。所以首先我们需要访问左节点的左节点（如果存在的话）。所以如果你这么想，你就明白了规则。但它太复杂了。然后我们使用递归。因为它的子问题与根节点问题相同，所以的范围只是缩小了。所以我们用递归的思维来解决。
则递归逻辑为：考虑特殊情况（特殊则直接访问），不递归，否则递归访问左子树（让左子树执行同样的功能，特殊则停止递归输出，搜索直到不特殊）最左边的节点。）——>节点输出——>递归访问右子树。

代码为：

public void zhongxu(node t)// 中序遍历 中序遍历：左子树---> 根结点 ---> 右子树
{
	if (t != null) {
		zhongxu(t.left);
		System.out.print(t.value + " ");// 访问完左节点访问当前节点
		zhongxu(t.right);
	}
}

序后递归

和之前的分析类似，继续是左子树--->右子树--->根节点-递归前序

`先方法（技术）`

非递归预序。我们使用堆栈属性而不是递归，因为递归有时在效率方面并不令人满意。使用堆栈，我们到达的订单将首先支付。那么如何添加订单呢？递归有左递归和右递归。然而，当使用栈时，则需要相反的操作，因为如果被推到左边，被推到右边，就会出现以下后果：所以如果我们要使用递归的思想，我们必须先将右节点放入栈中，然后再将左节点插入栈中。下次取该节点即可得到左节点。然后，该节点将右侧节点移至堆栈，并将左侧节点移至堆栈。然后继续循环，直到结束，先取出左节点。达到与递归序列相同的效果。每次弹出后，将左右节点相加并直接写入（访问），完成前序非递归遍历。

public void qianxu3(node t)// 非递归前序 栈 先左后右  t一般为root
{
	Stack<node> q1 = new Stack<node>();
	if (t == null)
		return;
	if (t != null) {
		q1.push(t);
	}
	while (!q1.empty()) {
		node t1 = q1.pop();
		if (t1.right != null) {
			q1.push(t1.right);
		}
		if (t1.left != null) {
			q1.push(t1.left);
		}
		System.out.print(t1.value + " ");
	}
}

`方法2（传统）`

方法2与非递归遍历方法类似，只不过需要修改输出时间，入栈时可以输入访问节点。有关详细信息，请参阅序列转换分析。

public void qianxu2(node t) {
		Stack<node> q1 = new Stack();	
		while(!q1.isEmpty()||t!=null)
		{
			if (t!=null) {
				System.out.print(t.value+" ");
				q1.push(t);				
				t=t.left;
			}
			else {
				t=q1.pop();
				t=t.right;
			}
		}
	}

`非递归顺序`

非递归顺序和预序之间有区别。我们的订单最多的顺序是：左结，根结，右结。那么我们在遍历完根节点之后就不能释放前一个节点了，因为后面还会用到它。所以首先你必须使用托盘来存放。它的规则大致是：

堆栈按顺序存储左节点的所有点，直到最左边的点到达堆栈顶部。
开始，丢弃弹匣顶部并访问。（例如第一卷2）。如果存在正确的节点。然后将右结添加到堆叠，然后将右结以相同的方向向下和向左传递，直到结束。（这里 5 和 7 没有左节点，所以它们不会相加）但是如果 15 被滚动。在23上打一个右结。然后找到左侧节点23，将其添加到栈顶。就这样循环，直到弹匣空了。

可行性分析：中间的顺序是左-中-右。参观完左侧。当当前点被抛出时，意味着已经访问过左侧（或者是左侧），所以必须先访问当前点的右侧。然后这个的右节点将其视为根节点，重复相同的操作（因为右节点必须满足先左后右的顺序）。这实际上模拟了一个递归过程，你必须自己思考。？使用类似于之前中序和前序第二次的方法进入推送和弹出，但是加上了额外的标签次，节点只有在第二次访问后才能释放。（第一次访问是入栈，第二次是当子树解析完毕即将出栈时（尚未出栈））。

`方法一（传统方法）`

当前面的前序和中间的顺序先向左移动时，这两个顺序是

前序：❙›>›中序移动到堆叠向左推动堆叠——>将左侧存储在堆叠中——>将中心存储在堆叠中——>向右推动堆叠——>将右子放入和取出——>右侧托盘上推入时可预先排序堆叠
中间顺序：中压->左压——>左弹出——>中弹出 ——>右推入栈——>右子进出——>出栈右跳按照出栈顺序，完成中间顺序

而在后序转换中：有这样的规则：

栈中，第一次访问的
即将跳出栈。第二次访问，
如果正确的子项存在，则将正确的子项推入堆栈而不弹出。如果不是合适的孩子，第一次访问。访问是从堆栈中提取的。
如此循环往复，直到栈为空

实现代码为（用map记录节点出现的次数）：

public void houxu2(node t) {
	Stack<node> q1 = new Stack();	
	Map<Integer,Integer >map=new HashMap<>();
	while(!q1.isEmpty()||t!=null)
	{
		if (t!=null) {
			q1.push(t);
			map.put(t.value, 1); //t.value标记这个值节点出现的次数
			t=t.left;
		}
		else {
			t=q1.peek();
			if(map.get(t.value)==2) {//第二次访问，抛出
				q1.pop();
				System.out.print(t.value+" ");
				t=null;//需要往上走
			}
			else {
				map.put(t.value, 2);
				t=t.right;
			}
			
		}
	}
}

`方法二（双栈）：`

另一种方法是使用两个堆栈进行处理。之前的方法，我们是用托盘压左右两侧。继续实现预购过渡效果。但这种方法很难遵循。

我们同样的方法来分析，如果我们先按左，再按右，那么我们得到的顺序就会和之前的顺序完全相反（顺序是：中，右），左侧倒置正好是左、右、中）对称外观的顺序。也就是说，使用另一个堆栈来执行序列并反转的顺序！如果继续这个过程，我们用另一个栈来存储并存储它第一次入栈，相当于反转。实现代码为：

public void houxu3(node t)// q1和q2 q1要先右后左，先遍历右侧，q1先装右侧就把右侧放到前面，左侧放在上面（栈顶）
{
	Stack<node> q1 = new Stack();
	Stack<node> q2 = new Stack();
	if (t == null)
		return;
	if (t != null) {
		q1.push(t);
	}
	while (!q1.isEmpty()) {
		node t1 = q1.pop();
		q2.push(t1);
		if (t1.left != null) {
			q1.push(t1.left);
		}
		if (t1.right != null) {
			q1.push(t1.right);
		}
	}
	while (!q2.isEmpty()) {
		node t1 = q2.pop();
		System.out.print(t1.value + " ");
	}
}