创建如图的二叉链表 实现树的先序遍历

为了创建如图所示的二叉链表，我们需要先定义二叉树的结构体类型，包括数据域和左右孩子指针。然后按照先序遍历的顺序依次创建每个节点，并将其插入到相应的位置上。具体实现过程如下：

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

#define MAXSIZE 100

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 创建二叉树
void CreateBiTree(BiTree *T) {
    int data;
    scanf("%d", &data);
    if (data == -1) { // 输入-1表示该节点为空
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = data;
        CreateBiTree(&((*T)->lchild)); // 递归创建左子树
        CreateBiTree(&((*T)->rchild)); // 递归创建右子树
    }
}

// 先序遍历的非递归算法
int PreOrder(BiTree T) {
    BiTree p, stack[MAXSIZE];
    int top = 0;
    p = T;
    if (T == NULL) {
        printf("二叉树为空\n");
        return 0;
    }
    while (p || top != 0) {
        while (p) {
            printf("%5d", p->data);
            stack[++top] = p;
            p = p->lchild;
        }
        if (top != 0) { // 栈不为空，出栈访问右孩子
            p = stack[top--];
            p = p->rchild;
        }
    }
    return 1;
}

int main() {
    BiTree T;
    printf("请按先序遍历的顺序输入二叉树的节点数据，-1表示该节点为空：\n");
    CreateBiTree(&T);
    printf("先序遍历的结果为：\n");
    PreOrder(T);
    return 0;
}