C++非递归建立二叉树：基于输入字符串的算法实现

清欢

发布时间：2026-10-14 | 2人浏览过

原创

在使用C++处理数据结构时，往往需要动态构建二叉树。传统递归方法简洁但可能面临栈溢出风险，本文将展示如何利用显式栈和状态标记机制，通过输入字符串非递归地建立二叉树。

核心思路与状态机设计

非递归构建二叉树的关键在于模拟递归调用的过程，记录当前结点的访问状态。我们定义一个标记变量 flag 来指示当前操作目标：

flag = 1：表示当前需要创建左孩子节点。
flag = 2：表示当前需要创建右孩子节点。
flag = 3：表示当前节点的左右孩子均处理完毕（包括空指针），需要执行出栈操作，回溯至父节点继续后续逻辑。

算法以先序遍历的顺序读取输入字符，当字符为 ‘#’ 时表示空节点，否则创建一个新节点并链接到栈顶元素。

准备条件与数据结构

在编写代码前，需确保已定义好二叉树节点结构 BTree 及指针类型 PBTree。主要依赖以下组件：

输入缓冲区：存储用户输入的字符串，通常包含数据字符和用于标识空子树的特殊符号（如‘#’）。
内存栈：数组形式的栈 stack[20]，用于保存指向树节点的指针，模拟函数调用栈。
辅助指针：temp 用于暂存栈顶元素以进行父子链接，pNew 用于动态分配新节点。

具体操作步骤与代码实现

第1步：初始化根节点与栈

首先从输入字符串中读取第一个字符，若不为结束符，则分配内存创建根节点，并将其入栈。设置栈顶指针 top 初始值为1（第一个位置被占据），并将 flag 设为1，表示接下来要处理根节点的左子树。

第2步：循环处理输入字符构建节点

进入 while(i < len) 循环，根据 flag 的值分支处理：

创建左孩子 (flag == 1)：
如果当前字符是 ‘#’，说明左子树为空，将 flag 置为 2 以等待处理右孩子。
如果不是 ‘#’，分配新节点 pNew，将其值赋为当前字符。将新节点链接到栈顶元素 temp->lchild，并将 pNew 压入栈中。保持 flag = 1 继续寻找下一层的左孩子。
创建右孩子 (flag == 2)：
如果当前字符是 ‘#’，说明右子树为空，将 flag 置为 3，触发后续的出栈逻辑。
如果不是 ‘#’，同样分配新节点 pNew，链接到栈顶元素的 rchild，压入栈中，并将 flag 重置为 1，开始构建右孩子的左子树。

第3步：处理回溯与出栈逻辑

当 flag == 3 时，表明当前节点（即刚刚创建的节点或其空的占位）的子树探索已完成。此时执行出栈操作：temp = stack[--top]。随后检查栈中剩余元素，如果栈顶下的元素其右孩子等于当前弹出的 temp，说明也已完成右子树构建，继续出栈，直到找到一个非右孩子的祖先或栈底。最后将 flag 设为 2，准备处理该祖先节点的右孩子，并递减索引 i 以便重新判断当前字符是否适用于新的父节点。

整个过程清晰地展现了非递归建树的逻辑流，无需深层次的系统栈即可生成复杂的树结构。以下是完整的 C++ 实现代码：

PBTree create()
{
    char ch[20];
    scanf("%s",ch);
    int len = strlen(ch);
    
    PBTree stack[20]; /* 用来存储结点地址的栈 */ 
    int top = 0; /* 栈顶指针 */
    int flag = 1; /* 1表示现在需要创建左孩子，2表示需要创建右孩子，3表示左右孩子都已经创建完成 */
    int i = 0;
    
    PBTree temp;
    PBTree root = (PBTree)malloc(sizeof(BTree));
    root->data = ch[i++];
    root->lchild = NULL;
    root->rchild = NULL;
    stack[top ++] = root;
    
    while(i < len)
    {
        PBTree pNew = NULL;
        if(1 == flag) /* 创建左孩子 */
        {
            if('#' == ch[i])
                flag = 2;
            else
            {
                pNew = (PBTree)malloc(sizeof(BTree));
                pNew->lchild = NULL;
                pNew->rchild = NULL;
                pNew->data = ch[i];
                temp = stack[top - 1];
                temp->lchild = pNew;
                stack[top++] = pNew;
                flag = 1;
            }
        }
        else if(2 == flag) /* 创建右孩子 */
        {
            if('#' == ch[i])
                flag = 3;
            else
            {
                pNew = (PBTree)malloc(sizeof(BTree));
                pNew->lchild = NULL;
                pNew->rchild = NULL;
                pNew->data = ch[i];
                temp = stack[top - 1];
                temp->rchild = pNew;
                stack[top++] = pNew;
                flag = 1;
            }
        }
        else /* 左右孩子已经创建完成，需要出栈*/
        {
            temp = stack[--top];
            while(top > 1 && stack[top - 1]->rchild == temp)
                --top;
            flag = 2;
            --i;
        }
        ++i;
    }
    return root;
}