编写先序遍历的非递归算法，显示二叉树的先序序列

先序遍历的非递归算法可以使用栈来实现。具体步骤如下：

1. 将根节点入栈。
2. 当栈不为空时，执行以下操作：
a. 弹出栈顶节点，并将其值输出。
b. 如果该节点有右子节点，则将右子节点入栈。
c. 如果该节点有左子节点，则将左子节点入栈。
3. 遍历结束。

下面是一个示例代码：

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    stack<TreeNode*> s;
    s.push(root);
    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();
        cout << node->val << " ";
        if (node->right != nullptr) {
            s.push(node->right);
        }
        if (node->left != nullptr) {
            s.push(node->left);
        }
    }
}

假设有如下二叉树：

    1
   / \
  2   3
 / \   \
4   5   6

使用上述算法遍历该二叉树的先序序列为：1 2 4 5 3 6。

相关问题

C语言实现编写二叉树的递归遍历算法，实现：给定一棵二叉树的扩展先序遍历序列，创建这棵二叉树 1输出二叉树的先序遍历的结点序列 2输出二叉树的先序遍历的结点序列 3输出二叉树的先序遍历的结点序列 4输出二叉树的叶子结点 5统计二叉树的结点个数

下面是C语言实现二叉树的递归遍历算法的代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

//创建二叉树
TreeNode *createTree(char *str, int *index) {
    if (str[*index] == '#' || str[*index] == '\0') {
        return NULL;
    }
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = str[*index];
    (*index)++;
    root->left = createTree(str, index);
    (*index)++;
    root->right = createTree(str, index);
    return root;
}

//先序遍历
void preOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%c ", root->data);
    preOrder(root->left);
    preOrder(root->right);
}

//中序遍历
void inOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%c ", root->data);
    inOrder(root->right);
}

//后序遍历
void postOrder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%c ", root->data);
}

//输出叶子结点
void printLeaves(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        printf("%c ", root->data);
    }
    printLeaves(root->left);
    printLeaves(root->right);
}

//统计结点个数
int countNodes(TreeNode *root) {
    if (root == NULL) {
        return 0;
    }
    return countNodes(root->left) + countNodes(root->right) + 1;
}

int main() {
    char str[] = "ABD##E##CF#H##G##";
    int index = 0;
    TreeNode *root = createTree(str, &index);

    printf("先序遍历：");
    preOrder(root);
    printf("\n");

    printf("中序遍历：");
    inOrder(root);
    printf("\n");

    printf("后序遍历：");
    postOrder(root);
    printf("\n");

    printf("叶子结点：");
    printLeaves(root);
    printf("\n");

    printf("结点个数：%d\n", countNodes(root));

    return 0;
}

程序的输出结果如下：

先序遍历：A B D E C F H G 
中序遍历：D B E A F C H G 
后序遍历：D E B H G F C A 
叶子结点：D E H G 
结点个数：7

其中，二叉树的扩展先序遍历序列为"ABD##E##CF#H##G##"，其中"#"表示空结点。在程序中，我们首先根据扩展先序遍历序列创建了二叉树，然后分别进行了先序、中序、后序遍历，并输出了叶子结点和结点个数。

c语言编程通过键盘输入二叉树的先序遍历顺序从而建立一棵二叉树，再采用递归算法实现显示出二叉树先序、中序和后序遍历顺序，最后采用非递归算法实现二叉树的先序遍历的代码

在C语言中，构建二叉树并进行遍历的过程通常涉及用户输入节点值，创建结构体表示节点，并实现递归和非递归遍历函数。以下是构建二叉树及遍历的基本步骤：

1. 定义二叉树节点结构：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

2. 用户输入先序遍历序列：

int preorder[100]; // 假设数组大小足够存储
int n; // 输入的节点数
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
    scanf("%d", &preorder[i]);
}

3. 创建二叉树并设置根节点（这里假设第一个元素作为根节点）：

TreeNode* root = createTree(preorder, n, 0);

`createTree` 函数是一个辅助函数，用于递归地创建二叉树。

4. 实现递归遍历函数（如先序遍历）：

void preorderTraversal(TreeNode* node) {
    if (node != NULL) {
        printf("%d ", node->val); // 先访问根
        preorderTraversal(node->left);
        preorderTraversal(node->right);
    }
}

5. 非递归遍历（如先序遍历）可以使用栈数据结构，但这里直接给出核心部分：

void nonRecursivePreorder(TreeNode* root) {
    if (root == NULL)
        return;

    stack<TreeNode*> s;
    s.push(root);

    while (!s.empty()) {
        TreeNode* node = s.top();
        s.pop();

        printf("%d ", node->val); // 访问当前节点

        if (node->right) {
            s.push(node->right);
        }

        if (node->left) {
            s.push(node->left);
        }
    }
}

6. 中序和后序遍历类似，只需调整访问节点和压入栈的顺序。