数据结构考研分类复习真题 第六章 答案 (四)[22]

最后一个递归调用语句所保留的参数没有意义这类递归因其在算法最后通常被称为尾递归 可不用栈且将其（递归）消除 如中序遍历递归算法中最后的递归语句inorder (bt>rchild)可改为下列语句段

bt=bt>rchild;

while (bt>rchild!=null)

{inorder (bt >lchild); printf(%cbt >data);//访问根结点假定结点数据域为字符

bt=bt >rchild; }

在二叉链表表示的二叉树中 引入线索的目的主要是便于查找结点的前驱和后继因为若知道各结点的后继二叉树的遍历就变成非常简单二叉链表结构查结点的左右子女非常方便但其前驱和后继是在遍历中形成的为了将非线性结构二叉树的结点排成线性序列 利用结点的空链域左链为空时用作前驱指针右链为空时作为后继指针再引入左右标记ltag 和rtag 规定ltag=lchild 指向左子女ltag=时lchild指向前驱当rtag=时 rchild指向右子女rtag=时rchild 指向后继这样在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归也不使用栈（后序线索二叉树查后继仍需要栈）

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []