二叉树建树

题目描述

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

输入

无输入。

直接定义 char *str="A(B(D,F(E,)),C(G(,H),I))"

输出

输出 先序遍历的顺序

样例输出

ABDFECGHI

提示

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

其他情况：只能是单个字符，表示要创建一个新结点p，根据k值建立p结点与栈顶结点之间的联系，当k=1时，表示p结点作为栈顶结点的左孩子结点，当k=2时，表示p结点作为栈顶结点的右孩子结点。

#include
using namespace std;
struct BTNode
{
int data;
BTNode *lchild;
BTNode *rchild; 
};
BTNode*CreateBTNode(char *str)
{BTNode *r=NULL;BTNode *st[100000];BTNode *p;int top=-1,k=0,j=0;char ch;while(str[j]!='\0'){ch=str[j];switch(ch){case'(':top++;st[top]=p;k=1;break;case')':top--;break;case ',':k=2;break;default:p=new BTNode();p->lchild=p->rchild=NULL;p->data=ch;if(r==NULL)r=p;else{switch(k){case 1:st[top]->lchild=p;break;case 2:st[top]->rchild=p;break;default:break;}}break;}  j++;} return r;
}
void DispBTNode1(BTNode *t)//递归先序遍历 
{if(t!=NULL){printf("%c",t->data);DispBTNode1(t->lchild);DispBTNode1(t->rchild);}
}
int main()
{char *str="A(B(D,F(,E)),C(G(,H),I))";BTNode *bt=CreateBTNode(str);DispBTNode1(bt);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！