《数据结构》课程教学资源：第五章 树形结构（2/2）

§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 TBin Tree Node0*TBin Tree GListToTree(long gList Exp, TElem*es, long numElem) TBinTreeNode*p, rt, **S; long top, 1; if(num Elem*InumElem+1 if(s==NULL) throw TExcepComm(3)

3 §5.6.2 根据广义表表示创建树 (二)广义表创建树的非递归算法 template TBinTreeNode0 *TBinTree:: GListToTree(long *gListExp, TElem *es, long numElem) { TBinTreeNode *p, *rt, **s; long top, i; if (numElem *[numElem+1]; if (s==NULL) throw TExcepComm(3);

p=new TBin TreeNode 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; 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 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 ; if (p==NULL) { delete [] s ; throw TExcepComm( 3 ) ; }p ->SetElem(&es[gListExp[i]]) ; }

if(gListExp1-1]==0) s[top]->SetSon(1, p); if(p!=NULL) p->SetFather(l, stop }e stop]->SetSon(2, p); if(p!=NULL) p->SetFather(2, s[top); Sl++top]=p s while(top!=0) deletes returner

6 if (gListExp[i - 1 ] == '(' ) { s[top] ->SetSon( 1 , p) ; if (p!=NULL) p ->SetFather( 1 , s[top]) ; } else { s[top] ->SetSon( 2 , p) ; if (p!=NULL) p ->SetFather( 2 , s[top]) ; } s[++top] = p ; }} while (top!= 0 ) ; delete [] s ; return rt ; }

§5.6.2根据广义表表示创建树 (三)广义表创建树的递归算法 二叉树广义表表达式,其表元素有三种: 空子树符号“*” 叶子结点符号(其后不带左圆括号) 子树的广义表表达式

7 §5.6.2 根据广义表表示创建树 (三)广义表创建树的递归算法 • 二叉树广义表表达式，其表元素有三种： –空子树符号“*” –叶子结点符号（其后不带左圆括号） –子树的广义表表达式

§5.6.2根据广义表表示创建树 三)广义表创建树的递归算法 在算法中,应分别考虑这三种情况,即先读出根结点名 称,为其申请一个树结点,然后读它的左右子树 若子树的根结点为“*”,则将根的相应链域置为空; 若子树的根结点为叶子,则为其分配一个树结点,并将根的相 应链域置为所分配结点的地址; 否则通过递归调用建立子树,然后将子树的根指针作为树的根 结点的相应链域的值

8 §5.6.2 根据广义表表示创建树 (三)广义表创建树的递归算法 • 在算法中，应分别考虑这三种情况，即先读出根结点名 称，为其申请一个树结点，然后读它的左右子树 –若子树的根结点为“*”，则将根的相应链域置为空； –若子树的根结点为叶子，则为其分配一个树结点，并将根的相 应链域置为所分配结点的地址； –否则通过递归调用建立子树，然后将子树的根指针作为树的根 结点的相应链域的值

§57二叉树的线索化 §5.71线索化的概念 线索化的目的 有时需知道二叉树结点在某种遍历方式下的前趋与后继。 棵具有n个结点的二叉树,有(nt1)个空链域(2no +n1),占总链域数目(2n)的1/2多 线索化 规定对任一结点,用空左链域存放它的前趋的指针 用空右链存放它的后继的指针 若某链域不空,则不存贮前趋与后继指针。 线索化 被线索化了的为线索邮

9 §5.7 二叉树的线索化 §5.7.1线索化的概念 • 线索化的目的 –有时需知道二叉树结点在某种遍历方式下的前趋与后继。 • 一棵具有n个结点的二叉树，有(n+1)个空链域(2n0 +n1 )，占总链域数目（2n）的1/2多 • 线索化 –规定对任一结点，用空左链域存放它的前趋的指针 –用空右链存放它的后继的指针 –若某链域不空，则不存贮前趋与后继指针。 线索化， 被线索化了的树为线索树

85.7.1线索化的概念 四种线索化方法和线索树: 前序线索化/树 中序线索化树 后序线索化/树 层序线索化/树 要分清是 哪种哦

10 §5.7.1线索化的概念 要分清是 哪种哦 • 四种线索化方法和线索树： –前序线索化/树 –中序线索化/树 –后序线索化/树 –层序线索化/树