请写出二叉树非递归遍历算法的先序遍历、中序遍历、后序遍历的伪代码,递归遍历算法 的先序遍历、中序遍历、后序遍历的伪代码,层次遍历算法的伪代码,求树深的伪代码,求叶子节点数的伪代码,求节点数的伪代码。
时间: 2023-07-24 16:32:34 浏览: 112
好的,下面是关于二叉树遍历和统计的伪代码:
1. 二叉树非递归遍历算法
(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,直到栈为空为止。
```
2. 二叉树递归遍历算法
(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节点的值。
```
3. 二叉树层次遍历算法
```
层次遍历二叉树(root为二叉树根节点):
1. 将root节点入队列;
2. 当队列不为空时,取出队首元素,输出其值;
3. 如果该元素的左子树不为空,则将其左子树入队列;
4. 如果该元素的右子树不为空,则将其右子树入队列;
5. 重复步骤2~4,直到队列为空为止。
```
4. 求树深
```
求二叉树深度(root为二叉树根节点):
1. 如果root节点为空,返回0;
2. 分别递归求左子树和右子树的深度,取其中较大值,加1即为该二叉树的深度。
```
5. 求叶子节点数
```
求二叉树叶子节点数(root为二叉树根节点):
1. 如果root节点为空,返回0;
2. 如果root节点的左右子树都为空,返回1;
3. 分别递归求左子树和右子树的叶子节点数,将其相加即为该二叉树的叶子节点数。
```
6. 求节点数
```
求二叉树节点数(root为二叉树根节点):
1. 如果root节点为空,返回0;
2. 分别递归求左子树和右子树的节点数,将其相加,再加1即为该二叉树的节点数。
```
以上就是关于二叉树遍历和统计的伪代码。
阅读全文