设计按先序次序遍历先序线索二叉树T的非递归算法 void preorder(tbnode *T)

按先序次序遍历先序线索二叉树T的非递归算法可以使用栈来实现：

1. 如果T为空，则返回。
2. 创建一个栈S，并将根节点入栈。
3. 当栈不为空时，重复以下步骤：
- 弹出栈顶元素，并输出该元素。
- 如果该元素存在左孩子，则将左孩子入栈。
- 如果该元素存在右孩子，则将右孩子入栈。
4. 遍历结束。

以下是具体实现：

void preorder(tbnode *T) {
    if (T == NULL) {
        return;
    }
    tbnode *p = T;
    stack<tbnode*> S;
    S.push(p);
    while (!S.empty()) {
        p = S.top();
        S.pop();
        cout << p->data << " "; // 输出节点值
        if (p->ltag == Link) { // 如果存在左孩子，则将左孩子入栈
            S.push(p->lchild);
        }
        if (p->rtag == Link) { // 如果存在右孩子，则将右孩子入栈
            S.push(p->rchild);
        }
    }
}

相关问题

按先序次序输入二叉树中结点的值 c语言设计程序实现二叉树的四种遍历算法；

以下是基于链式存储结构的二叉树遍历算法的C语言实现：

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

// 定义二叉树的结构体
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

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

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

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

// 层序遍历
void levelorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode* cur = queue[front++];
        printf("%d ", cur->val);
        if (cur->left != NULL) {
            queue[rear++] = cur->left;
        }
        if (cur->right != NULL) {
            queue[rear++] = cur->right;
        }
    }
}

int main() {
    // 创建二叉树
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    // 遍历二叉树
    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("\n");

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    printf("Postorder traversal: ");
    postorderTraversal(root);
    printf("\n");

    printf("Levelorder traversal: ");
    levelorderTraversal(root);
    printf("\n");

    return 0;
}

这里实现了四种遍历算法，分别是先序遍历、中序遍历、后序遍历和层序遍历。其中，先序遍历、中序遍历和后序遍历都是基于递归实现的，而层序遍历则是基于队列实现的。

利用二叉链表方法编程实现建立二叉树，按照二叉树的先序遍历算法逆序显示遍历访问的次序。C语言代码

下面是二叉链表建立二叉树并按照先序遍历逆序显示的C语言代码：

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

// 二叉树结点结构体
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 先序遍历逆序显示函数
void reverse_preorder(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    // 先访问当前结点
    printf("%d ", root->data);
    // 递归遍历右子树
    reverse_preorder(root->right);
    // 递归遍历左子树
    reverse_preorder(root->left);
}

// 建立二叉树函数
TreeNode* create_tree() {
    int val;
    scanf("%d", &val);
    if (val == -1) {  // 输入-1表示空结点
        return NULL;
    }
    TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));
    root->data = val;
    root->left = create_tree();
    root->right = create_tree();
    return root;
}

int main() {
    TreeNode *root = create_tree();
    printf("先序遍历逆序显示：");
    reverse_preorder(root);
    printf("\n");
    return 0;
}

在该程序中，我们利用了二叉链表的方法建立了一棵二叉树，并定义了一个先序遍历逆序显示函数 `reverse_preorder()`。该函数先访问当前结点、再递归遍历右子树、最后递归遍历左子树，实现了先序遍历算法的逆序输出。最后在 `main()` 函数中调用 `create_tree()` 建立二叉树，再调用 `reverse_preorder()` 函数输出先序遍历逆序显示的结果。