先序线索二叉树的建立（递归，非递归）C语言

建立先序线索二叉树的方法有递归和非递归两种。

1. 递归建立先序线索二叉树：

构建二叉树时，将空节点（NULL）也当成二叉树节点进行处理。具体步骤如下：

// 先序线索二叉树结点结构体
struct ThreadNode {
    char data;                  // 数据域
    struct ThreadNode *lchild;  // 左指针
    struct ThreadNode *rchild;  // 右指针
    int ltag;                   // 左线索标志
    int rtag;                   // 右线索标志
};

// 递归建立先序线索二叉树
ThreadNode *CreateThreadTree() {
    char data;
    ThreadNode *p = NULL;
    scanf("%c", &data);
    if (data == '#') {
        p = NULL;
    } else {
        p = new ThreadNode;
        p->data = data;
        p->ltag = 0;
        p->rtag = 0;
        p->lchild = CreateThreadTree();  // 递归创建左子树
        p->rchild = CreateThreadTree();  // 递归创建右子树
    }
    return p;
}

2. 非递归建立先序线索二叉树：

借助栈来实现。具体步骤如下：

// 非递归建立先序线索二叉树
ThreadNode *CreateThreadTree() {
    char data;
    ThreadNode *p = NULL;
    ThreadNode *stack[100];   // 定义一个栈
    int top = -1;
    scanf("%c", &data);
    while (data != '#') {
        p = new ThreadNode;
        p->data = data;
        p->ltag = 0;
        p->rtag = 0;
        p->lchild = NULL;
        p->rchild = NULL;
        if (top == -1) {  // 栈为空
            stack[++top] = p;
        } else {
            while (stack[top]->rchild != NULL && top >= 0) {  // 找到第一个没有右子节点的栈顶元素
                --top;
            }
            if (top >= 0) {                                  // 如果栈不为空
                if (stack[top]->lchild == NULL) {             // 如果该元素没有左子节点
                    stack[top]->lchild = p;                   // 将新节点作为其左子节点
                    stack[top]->ltag = 1;                      // 标记左线索
                } else {                                      // 如果该元素已经有左子节点
                    stack[top]->rchild = p;                   // 将新节点作为其右子节点
                    stack[top]->rtag = 1;                      // 标记右线索
                }
            }
            stack[++top] = p;                                 // 将新节点入栈
        }
        scanf("%c", &data);
    }
    return stack[0];                                          // 返回栈底元素，即根节点
}

以上是建立先序线索二叉树的 C 语言代码，希望对你有所帮助。