【精品数据结构】根据广义表表示创建树.PPTVIP

§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 根据广义表表示创建树 (一)二叉树的广义表表示 §5.6.2 根据广义表表示创建树 (二)广义表创建树的非递归算法 template class TElem TBinTreeNode0TElem *TBinTreeTElem:: GListToTree(long *gListExp, TElem *es, long numElem) { TBinTreeNodeTElem *p, *rt, **s; long top, i; ? if (numElem2) return NULL; ? s = new TBinTreeNodeTElem *[numElem+1]; if (s==NULL) throw TExcepComm(3); p = new TBinTreeNodeTElem; if (p==NULL) { delete [] s; throw TExcepComm(3); } ? top=0; i=1; rt = p; p-SetElem(es[gListExp[i]]); s[++top] = p; do { i++; if (gListExp[i]==() continue; if (gListExp[i]==, || gListExp[i]==)) top--; else { if (gListExp[i]==*) p = NULL; else { p = new TBinTreeNodeTElem; if (p==NULL) { delete [] s; throw TExcepComm(3); } p-SetElem(es[gListExp[i]]); } 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 根据广义表表示创建树 (三)广义表创建树的递归算法 二叉树广义表表达式，其表元素有三种： 空子树符号“*” 叶子结点符号（其后不带左圆括号） 子树的广义表表达式。 §5.6.2 根据广义表表示创建树 (三)广义表创建树的递归算法 在算法中，应分别考虑这三种情况，即先读出根结点名称，为其申请一个树结点，然后读它的左右子树 若子树的根结点为“*”，则将根的相应链域置为空； 若子树的根结点为叶子，则为其分配一个树结点，并将根的相应链域置为所分配结点的地址； 否则通过递归调用建立子树，然后将子树的根指针作为树的根结点的相应链域的值。 线索化的目的 有时需知道二叉树结点在某种遍历方式下的前趋与后继。 一棵具有n个结点的二叉树，有(n+1)个空链域(2n0 +n1)，占总链域数目（2n）的1/2多 线索化 规定对任一结点，用空左链域存放它的前趋的指针 用空右链存放它的后继的指针 若某链域不空，则不存贮前趋与后继指针。 四种线索化方法和线索树： 前序线索化/树 中序线索化/树 后序线索化/树 层序线索化/树。 【例5.5】中序线索化树。 标志信息 00：左右链均为树结构信息； 01：左为树结构信息，右为线索； 10：左为线索，右为树结构信息； 11：左右均为线索； 改写二叉树二指针存贮结构的描述，增加关于线索的标志： 　　struct TBinTreeNodeThread { TElem info; struct TBinTreeNode *lc, *rc; unsigned char threadTag; … … }; 该类/结构应是前面介绍的TBinTreeNode的派生类： 　　struct TBinTreeNodeThread ： pub