二叉树非递归遍历算法

二叉树的非递归遍历算法有三种：先序遍历、中序遍历和后序遍历。下面分别介绍这三种非递归遍历算法：

先序遍历：使用栈来模拟递归过程。首先将根节点入栈，然后进入循环，循环条件为栈不为空。在循环中，弹出栈顶元素并访问，然后先将右子节点入栈（如果存在），再将左子节点入栈（如果存在）。重复这个过程直到栈为空。

中序遍历：同样使用栈来模拟递归过程。首先将根节点入栈，然后进入循环，循环条件为栈不为空或当前节点不为空。在循环中，先将当前节点及其所有左子节点依次入栈，直到当前节点为空。然后弹出栈顶元素并访问，再将当前节点指向其右子节点，重复上述过程。

后序遍历：需要使用两个栈来实现。首先将根节点入栈1，然后进入循环，循环条件为栈1不为空。在循环中，弹出栈1的栈顶元素并入栈2，然后将当前节点的左子节点和右子节点依次入栈1（如果存在）。重复这个过程直到栈1为空。最后，将栈2中的元素依次出栈并访问，即为后序遍历的结果。

这样，你就可以使用这三种非递归遍历算法来遍历二叉树了。

相关问题

请写出二叉树非递归遍历算法、递归遍历算法 、层次遍历算法的伪代码。

好的，下面是二叉树非递归遍历算法、递归遍历算法、层次遍历算法的伪代码：

二叉树非递归遍历算法（中序遍历）

非递归中序遍历二叉树(root为二叉树根节点)：
1. 将root节点入栈；
2. 当栈不为空时，取出栈顶元素，如果该元素左子树不为空，则将其左子树全部入栈；
3. 如果该元素左子树为空，或者左子树已经被访问过了，则输出该节点的值，并将其右子树入栈；
4. 重复步骤2~3，直到栈为空为止。

二叉树递归遍历算法（先序遍历）

递归先序遍历二叉树(root为二叉树根节点)：
1. 如果root节点为空，直接返回；
2. 输出root节点的值；
3. 递归遍历root节点的左子树；
4. 递归遍历root节点的右子树。

二叉树层次遍历算法

层次遍历二叉树(root为二叉树根节点)：
1. 将root节点入队列；
2. 当队列不为空时，取出队首元素，输出其值；
3. 如果该元素的左子树不为空，则将其左子树入队列；
4. 如果该元素的右子树不为空，则将其右子树入队列；
5. 重复步骤2~4，直到队列为空为止。

以上就是二叉树非递归遍历算法、递归遍历算法、层次遍历算法的伪代码。

请写出二叉树非递归遍历算法的先序遍历、中序遍历、后序遍历的伪代码，递归遍历算法 的先序遍历、中序遍历、后序遍历的伪代码，层次遍历算法的伪代码，求树深的伪代码，求叶子节点数的伪代码，求节点数的伪代码。

好的，下面是关于二叉树遍历和统计的伪代码：

二叉树非递归遍历算法

（1）先序遍历
非递归先序遍历二叉树(root为二叉树根节点)：
1. 创建一个栈stack，将root节点入栈；
2. 当栈不为空时，取出栈顶元素，输出其值；
3. 如果该元素的右子树不为空，则将其右子树入栈；
4. 如果该元素的左子树不为空，则将其左子树入栈；
5. 重复步骤2~4，直到栈为空为止。

（2）中序遍历
非递归中序遍历二叉树(root为二叉树根节点)：
1. 创建一个栈stack，将root节点入栈；
2. 当栈不为空时，取出栈顶元素，如果该元素的左子树为空或者左子树已经被访问过了，则输出该节点的值，并将其右子树入栈；
3. 如果该元素的左子树不为空，则将其左子树入栈；
4. 重复步骤2~3，直到栈为空为止。

（3）后序遍历
非递归后序遍历二叉树(root为二叉树根节点)：
1. 创建一个栈stack，将root节点入栈；
2. 创建一个标志位变量，初始值为null；
3. 当栈不为空时，取出栈顶元素，如果该元素的左右子树都为空，或者其左右子树已经被访问过了，则输出该节点的值，并将标志位变量设为该节点；
4. 如果该元素的右子树不为空且右子树未被访问过，则将其右子树入栈；
5. 如果该元素的左子树不为空且左子树未被访问过，则将其左子树入栈；
6. 如果该元素的左右子树都不为空且左右子树都已经被访问过了，则输出该节点的值，并将标志位变量设为该节点；
7. 重复步骤3~6，直到栈为空为止。

二叉树递归遍历算法

（1）先序遍历
递归先序遍历二叉树(root为二叉树根节点)：
1. 如果root节点为空，直接返回；
2. 输出root节点的值；
3. 递归遍历root节点的左子树；
4. 递归遍历root节点的右子树。

（2）中序遍历
递归中序遍历二叉树(root为二叉树根节点)：
1. 如果root节点为空，直接返回；
2. 递归遍历root节点的左子树；
3. 输出root节点的值；
4. 递归遍历root节点的右子树。

（3）后序遍历
递归后序遍历二叉树(root为二叉树根节点)：
1. 如果root节点为空，直接返回；
2. 递归遍历root节点的左子树；
3. 递归遍历root节点的右子树；
4. 输出root节点的值。

二叉树层次遍历算法

层次遍历二叉树(root为二叉树根节点)：
1. 将root节点入队列；
2. 当队列不为空时，取出队首元素，输出其值；
3. 如果该元素的左子树不为空，则将其左子树入队列；
4. 如果该元素的右子树不为空，则将其右子树入队列；
5. 重复步骤2~4，直到队列为空为止。

求树深

求二叉树深度(root为二叉树根节点)：
1. 如果root节点为空，返回0；
2. 分别递归求左子树和右子树的深度，取其中较大值，加1即为该二叉树的深度。

求叶子节点数

求二叉树叶子节点数(root为二叉树根节点)：
1. 如果root节点为空，返回0；
2. 如果root节点的左右子树都为空，返回1；
3. 分别递归求左子树和右子树的叶子节点数，将其相加即为该二叉树的叶子节点数。

求节点数

求二叉树节点数(root为二叉树根节点)：
1. 如果root节点为空，返回0；
2. 分别递归求左子树和右子树的节点数，将其相加，再加1即为该二叉树的节点数。

以上就是关于二叉树遍历和统计的伪代码。