§5.62根据广义表表示创建树 ()二叉树的广义表表示 一棵以r为根的二叉树的广义表表示(广义表表达式)定义为如下形 式 (R) 其中,R可递归地定义为: a)若r空树,则R的形式为星号,即“*” b)若r是叶子,则R的形式为:rN c)若r是非叶子结点,则R的形式为:r(rL,rR) 其中,N为结点r的标识,工L和R分别为r的左右子树的广义表表示
1 §5.6.2 根据广义表表示创建树 (一)二叉树的广义表表示 一棵以r为根的二叉树的广义表表示（广义表表达式）定义为如下形 式： (R) 其中，R可递归地定义为： a) 若r空树，则R的形式为星号，即“*” ； b) 若r是叶子，则R的形式为：rN c) 若r是非叶子结点，则R的形式为：r(rL，rR) 其中，rN为结点r的标识，rL和rR分别为r的左右子树的广义表表示
§5.6.2根据广义表表示创建树 ()二叉树的广义表表示 广义表:(1(2(*4(5,*),3) 广义表:(1(*,3(24(5,*)) 图二叉树的广义表表示
2 §5.6.2 根据广义表表示创建树 (一)二叉树的广义表表示 1 2 3 4 5 3 1 2 4 5 广义表：(1(2(*,4(5,*)), 3)) 广义表：(1(*,3(2,4(5,*)))) 图 - 二叉树的广义表表示
§5.6.2根据广义表表示创建树 (二)广义表创建树的非递归算法 template <class TElem> TBin Tree Node0<TElem>*TBin Tree<TElem> GListToTree(long gList Exp, TElem*es, long numElem) TBinTreeNode<TElem>*p, rt, **S; long top, 1; if(num Elem<)return NULL s= new TBin TreeNode<TElem>*InumElem+1 if(s==NULL) throw TExcepComm(3)
3 §5.6.2 根据广义表表示创建树 (二)广义表创建树的非递归算法 template <class TElem> TBinTreeNode0<TElem> *TBinTree<TElem>:: GListToTree(long *gListExp, TElem *es, long numElem) { TBinTreeNode<TElem> *p, *rt, **s; long top, i; if (numElem<2) return NULL; s = new TBinTreeNode<TElem> *[numElem+1]; if (s==NULL) throw TExcepComm(3);
p=new TBin TreeNode< TElem> if (p-NULL) delete[ s throw TExcep Comm(3); top=0; Fl rt=p p->SetElem(&es[glist Expl Sl++top]=p
4 p = new TBinTreeNode<TElem>; if (p==NULL) { delete [] s; throw TExcepComm(3); } top=0;i=1; rt = p; p->SetElem(&es[gListExp[i]]); s[++top] = p;
1++ if(gListExp-=( ) continue if( gListExp[]==’‖ gListExp[i]==)top-; if (gList Exp[]== )p=NULL; eise p=new TBin TreeNode <telem> if(p=-NULL) delete[ s throw TExcepComm(3) p->SetElem(&es[gListExpiD)
5 do{ i++ ; if (gListExp[i]=='(') continue ; if (gListExp[i]==',' || gListExp[i]==')') top-- ; else { if (gListExp[i]=='*') p = NULL ; else {p = new TBinTreeNode<TElem> ; if (p==NULL) { delete [] s ; throw TExcepComm( 3 ) ; }p ->SetElem(&es[gListExp[i]]) ; }