Description

括号表示法表示的二叉树字符串 A(B(D,F(E,)),C(G(,H),I))，建立这棵树，并用先序、中序和后序遍历输出结果。

Input Format

输入树的括号表示法

Output Format

输出 先序遍历的顺序


int main()
{
 char *str;
cin>>str;
 BTNode *bt=CreateBTNode(str);
  DispBTNode1(bt);
 return 0;
}


void DispBTNode1(BTNode *t)//递归先序遍历
{
 if(t!=NULL)
 {
  printf("%c",t->data);
  DispBTNode1(t->lchild);
  DispBTNode1(t->rchild);
 }
}

A(B(D,F(E,)),C(G(,H),I))

ABDFECGHI
DBEFAGHCI
DEFBHGICA

Hint

若ch='('：表示前面刚创建的p结点存在着孩子结点，需将其进栈，以便建立它和其孩子结点的关系（如果一个结点刚创建完毕，其后一个字符不是'('，表示该结点是叶子结点，不需要进栈）。然后开始处理该结点的左孩子，因此置k=1，表示其后创建的结点将作为这个结点（栈顶结点）的左孩子结点；
若ch=')'：表示以栈顶结点为根结点的子树创建完毕，将其退栈；
若ch=','：表示开始处理栈顶结点的右孩子结点，置k=2；
其他情况：只能是单个字符，表示要创建一个新结点p，根据k值建立p结点与栈顶结点之间的联系，当k=1时，表示p结点作为栈顶结点的左孩子结点，当k=2时，表示p结点作为栈顶结点的右孩子结点。

Source

未分类