后序遍历的非递归算法

《后序遍历的非递归算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章树二叉树后序遍历的非递归算法。在对二叉树进行后序遍历的过程中，当指针p指向某一个结点时，不能马上对它进行访问，而要先遍历它的左子树，因而要将此结点的地址进栈保存。当其左子树遍历完毕之后，再次搜索到该结点时(该结点的地址通过退栈得到)，还不能对它进行访问，还需要遍历它的右子树，所以，再一次将此结点的地址进栈保存。为了区别同一结点的两次进栈，引入一个标志变量nae，有0表示该结点暂不访问1表示该结点可以访问标志flag的值随同进栈结点的地址一起进栈和出栈。因此，算法中设置两个空间足够的堆栈，其中，STACK

2、lCM]存放进栈结点的地址，STACK2[M]存放相应的标志n昭的值，两个堆栈使用同一栈顶指针top，top的初值为—1。具体算法如下：#defineH100／●定义二叉树中结点最大数目。／voidPOSTOiRDER(BTREET){／*T为二叉树根结点所在链结点的地址。／BTREESTACKl[H]，p=T；intSTACK2[M]，flag,top=—1；if(T!=NULL)d0{while(p!=NULL){STACK／[++top]=p；／●当前p所指结点的地址进栈●／STACK2[top]=0；

3、／，标志0进栈●／p=p->lchild；／●将p移到其左孩子结点x／}p=STACKl[top)；flag=STACK2[top--]；if(flag==0){STACKl[++top]=p；／，当前p所指结点的地址进栈。／STACK2[toP]=1；／●标志1进栈●／p=p->rchild；／x将p移到其右孩子结点o／}else{VISIT(p)；／x访问当前p所指的结点x／p=NULL；}}while(p!=NULLtttop!=-1)；}不难分析，上述算法的时间复杂度同样为O(n)7．6．3二叉树的线

4、索化算法对--X树的线索化，就是把二叉树的二叉链表存储结构中结点的所有空指针域改造成指向某结点在某种遍历序列中的直接前驱或直接后继的过程，因此，二叉树的线索化过程只能在对二叉树的遍历过程中进行。·下面给出二叉树的中序线索化的递归算法。算法中设有指针pre，用来指向中序遍历过程中当前访问的结点的直接前驱结点，pre的初值为头结点的指针；T初始时指向头结点，但在算法执行过程中，T总是指向当前访问的结点。voldINTHREAD(TBTREET){TBTREEpre；if(T!=Null){INTHREAD(T—>

5、lchild)；if(T—>rchild==NULL)T—>rbit=0；if(T—>lchild==NUll)；T—>lchild=pre；T—>lbit=0；}if(pre—>rbitc==0)pre—>rchild=T；pre=T；inthread(T->rchild)；}}平均查找长度(AverageSearchLength)：确定一个元素在树中的位置所需要进行的比较次数的期望值。二叉树的内路径长度(InternalPathLength)：从二叉树根结点到某结点所经过的分支数目定义为该结点的路径长度。

6、二叉树中所有结点的路径长度之和定义为该二叉树的内路径长度IPL。图7。25(h)给出的二叉排序树的内路径长度为IPL：1X2+2X2+3X1+4X2=17二叉树的外路径长度(ExternalPathLength)：为了分析查找失败时的查找长度，在二叉树中出现空子树时，增加新的空叶结点来代表这些空子树，从而得到一棵扩充后的二叉树。为了与扩充前的二叉树相区别，这些新增添的空的叶结点用小方块代表，称之为外部结点，树中原有的结点为内部结点。图7．27给出了一棵扩充后的二叉树，其外路径长度EPL是二叉树中所有外部结点的

7、路径长度之和，即EPL=2X2+3X1+4X4+5X3十6X2=50习题7.1判断题(在你认为正确的题后的括号中打√，否则打X)。(1)在树型结构中，每一个结点最多只有一个前驱结点，但可以有多个后继结点。()(2)在树型结构中，每—个结点不能没有前驱结点。()(3)在度为k的树中，至少有一个度为k的结点。()(4)在度为k的树中，每个结点最多有k—1个兄弟结点。()(5)度为2的树是二叉树。()(6)二叉树的度一定为2。()(7)在非空完全二叉树中，只有最下面一层的结点为叶结点。()(8)在完全-y．树中，没

8、有左孩子的结点一定是叶结点。()(9)在完全二叉树中，没有右孩子的结点一定是叶结点。()(10)在结点数目一定的前提下，各种形态的二叉树中，完全二叉树具有最小深度。()(11)满二叉树一定是完全二叉树。()(12)满二叉树中的每个结点的度不是0就是2。()(13)在所有深度相同的二叉树中，满二叉树具有最大结点数目。()(14)具有n个结点的非空二叉树一定有n—1个分支。()(15)n个结点的二叉树采