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线索化的概念 要分清是 哪种哦 • 四种线索化方法和线索树： –前序线索化/树 –中序线索化/树 –后序线索化/树 –层序线索化/树