根据前序和中序非递归创建二叉树

Question

怎样才能创建二叉树？传入参数T后，T不断被改变，我只想创建T的子树。然后以T为头节点。
struct BTNode
{
char data;

BTNode lchild ;
BTNode *rchild; //左右孩子指针
} ;
typedef BTNode *BT;
/由先序和中序非递归创建二叉树*/
void CreatBT2(BT &T, string preStr, string inStr)
{
stack stack;
int index1,index2,preStrflag[N];
int i=0,j=0,k,m;
preStr = preStr + '#'; //由于先序序列采用字符串形式，末尾加上#便于处理
while (preStr[j] != '#')
{/*while循环将先序对应的数组全部标记为0*/
preStrflag[j]=0;
j++;
}
if (preStr.length() == 0 || inStr.length() == 0)
{/*处理特殊情况*/
T = NULL;
return;
}
else
{/*依次对先序序列中的每个字符进行存储，若一个*/
T = new BTNode;
T->data = preStr[i];

    preStrflag[i]=1;    
    i++;
    stack.push(T);
     while (preStr[i] != '#')
    {
        preStrflag[i]=1;
        index1 = inStr.find(preStr[i]);
        index2 = inStr.find(preStr[i-1]);
        if (index1< index2)
        {/*处理：如果在先序中为...AB...,中序中为..B..A..*/                
            T=T->lchild;      
            T=new BTNode;
            T->data = preStr[i];    
            stack.push(T);
        }
        else if (index1 == index2 + 1)
        {/*处理：如果在先序中为...AB...,中序中为..AB..*/
            T=T->rchild;
            T=new BTNode;
            T->data = preStr[i];
            stack.push(T);
        }
        else
        {/*处理：如果在先序中为...AB...,中序中为..A..B..*/
            k = inStr.find(preStr[i])-1;
            m = preStr.find(inStr[k]);
            while (preStrflag[m] == 0)
            {/*在中序中依次往前遍历，查找第一个已存在树中的字符*/
                k--;
                m = preStr.find(inStr[k]);
            }                   
            while (inStr[k] != T->data){
            T= stack.top();
            stack.pop();
            }
            T=T->rchild;
            T=new BTNode;
            T->data = preStr[i];
            stack.push(T);
        }
        i++;
    }
}

}

Answer 1

你可以看一下我的博客，里面有一个Java方式的解决方法，希望能帮到你