二叉树的先序非递归遍历算法思想

二叉树的先序非递归遍历算法思想如下：

1. 创建一个空栈，用于存储待访问的节点。
2. 初始化当前节点为根节点。
3. 循环执行以下步骤，直到栈为空：
1. 访问当前节点，并将其值输出或存储。
2. 如果当前节点有右子节点，则将右子节点入栈。
3. 如果当前节点有左子节点，则将左子节点入栈。
4. 弹出栈顶元素作为当前节点，继续循环。

在这个算法中，我们通过栈来模拟递归的过程。先序遍历的顺序是根节点 -> 左子树 -> 右子树，所以我们首先访问根节点，然后将右子节点入栈，再将左子节点入栈。这样，在遍历完左子树之后，我们可以按栈的顺序依次访问右子树的节点。

这种非递归的遍历算法可以保证每个节点都被访问且仅被访问一次，时间复杂度为 O(n)，其中 n 是二叉树的节点个数。

相关问题

先序非递归遍历算法遍历二叉树 ​中序非递归遍历算法遍历二叉树 ​后序非递归遍历算法遍历二叉树 ​层序遍历二叉树

好的，我可以给您介绍一下二叉树的四种非递归遍历算法以及层序遍历。

先序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 当栈不为空时，取出栈顶元素并访问它。
3. 将当前节点的右子节点（如果存在）入栈，再将左子节点（如果存在）入栈。
4. 重复步骤2-3，直到栈为空。

中序非递归遍历算法：
1. 新建一个栈，将根节点入栈。
2. 如果当前节点不为空，则将当前节点的左子节点全部入栈，并将当前节点置为左子节点。
3. 如果当前节点为空，则取出栈顶元素并访问它，将当前节点置为它的右子节点。
4. 重复步骤2-3，直到栈为空。

后序非递归遍历算法：
1. 新建两个栈：s1和s2，将根节点入s1。
2. 当s1不为空时，取出栈顶元素并将其压入s2中。
3. 将当前节点的左子节点（如果存在）入s1，再将右子节点（如果存在）入s1。
4. 重复步骤2-3，直到s1为空。
5. 依次访问s2中的元素即可得到后序遍历结果。

层序遍历算法：
1. 新建一个队列，将根节点入队。
2. 当队列不为空时，取出队首元素并访问它。
3. 将当前节点的左子节点（如果存在）入队，再将右子节点（如果存在）入队。
4. 重复步骤2-3，直到队列为空。

二叉树的创建（用先序递归算法创建） 2、二叉树的先序递归遍历 3、二叉树的中序递归遍历 4、二叉树的后序递归遍历 5、二叉树的中序非递归遍历（调用栈实现 6、求二叉树的节点总数 7、求二叉树的叶子节点总数 8、求二叉树的深度 输入结点信息，能完成所有功能，有适当的注释使用C语言

首先，我们来理解如何用C语言通过先序递归算法创建二叉树：

// 定义二叉树结点结构
typedef struct TreeNode {
    int val;
    struct TreeNode *left; // 左孩子指针
    struct TreeNode *right; // 右孩子指针
} TreeNode;

// 创建二叉树函数 (先序遍历)
TreeNode* createTree(int value[], int start, int end) {
    if (start > end) return NULL; // 如果索引超出范围，返回空节点
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); // 分配内存
    root->val = value[start]; // 设置当前值
    root->left = createTree(value, start + 1, end); // 递归左子树
    root->right = createTree(value, start + 2, end); // 递归右子树
    return root;
}

接下来，是四种基本的二叉树递归遍历：

1. **先序遍历**: 访问根 -> 左 -> 右

   void preOrderTraversal(TreeNode* node) {
       if (node != NULL) {
           printf("%d ", node->val); // 访问节点
           preOrderTraversal(node->left); // 左子树
           preOrderTraversal(node->right); // 右子树
       }
   }

2. **中序遍历**: 左 -> 访问根 -> 右

   void inOrderTraversal(TreeNode* node) {
       if (node != NULL) {
           inOrderTraversal(node->left);
           printf("%d ", node->val);
           inOrderTraversal(node->right);
       }
   }

3. **后序遍历**: 左 -> 右 -> 访问根

   void postOrderTraversal(TreeNode* node) {
       if (node != NULL) {
           postOrderTraversal(node->left);
           postOrderTraversal(node->right);
           printf("%d ", node->val);
       }
   }

4. **中序非递归遍历**（利用栈实现）：

   void iterativeInOrderTraversal(TreeNode* root) {
       stack<TreeNode*> s;
       TreeNode* curr = root;
       while (curr || !s.empty()) {
           while (curr) {
               s.push(curr);
               curr = curr->left;
           }
           curr = s.top(); // 弹出栈顶元素
           s.pop();
           printf("%d ", curr->val);
           curr = curr->right;
       }
   }

对于计算节点总数、叶子节点总数和深度，我们可以分别添加以下函数：

- 节点总数（包括根节点）
- ```c
int countNodes(TreeNode* node) {
if (node == NULL) return 0;
return 1 + countNodes(node->left) + countNodes(node->right);
}

   
- 叶子节点总数
- ```c
   int countLeaves(TreeNode* node) {
       if (node == NULL) return 0;
       if (node->left == NULL && node->right == NULL) return 1; // 判断是否为叶子节点
       return countLeaves(node->left) + countLeaves(node->right);
   }

- 深度（假设根节点深度为0）
- ```c
int depth(TreeNode* node) {
if (node == NULL) return 0;
return 1 + MAX(depth(node->left), depth(node->right));
}

请注意，`MAX`是一个宏或者函数，用于获取两个整数的最大值。以上代码仅作为示例，并未包含错误处理和边界检查，实际编写时需要完善。