数据结构考研分类复习真题 第六章 树和二叉树 (五)[24]

给出中序线索树的结点结构并画出一个具有头结点的中序线索树使其树结点至少应有个写一算法在不使用栈和递归的情况下前序遍历一中序线索树并分析其时间复杂性【东南大学 三(分) 三(分) 六(分)】

．设有二叉树BT每个结点包括ltaglchilddatarchildrtag五个字段依次为左标志左儿子数据右儿子右标志给出将二叉树BT建成前序(即先序)线索二叉树的递归算法【四川联合大学 三】【东南大学六(分)】

．写出中序线索二叉树的线索化过程(已知二叉树T)【山东大学 五 (分)】【长沙铁道学院 五 (分)】

．已知一中序线索二叉树写一算法完成对它的中序扫描【山东大学软件与理论三(分)】

．已知中序线索二叉树T右子树不空设计算法将S所指的结点作为T的右子树中的一个叶子结点插入进去并使之成为T的右子树的(中序序列)第一个结点(同时要修改相应的线索关系)【合肥工业大学 五(分)】

．写出算法求出中序线索二叉树中给定值为x的结点之后继结点返回该后继结点的指针线索树中结点结构为(ltaglcdatarcrtag)其中data存放结点的值lcrc为指向左右孩子或该结点前驱或后继的指针ltagrtag为标志域各值为则lcrc为指向左右孩子的指针值为则lcrc为指向某前驱后继结点的指针【北京邮电大学 八(分)】

．设后序线索树中结点构造为(LtagLchildDataRchildRtag)其中:LtagRtag 值为时LchildRchild 分别为儿子指针否则分别为直接前驱直接后继的线索请写出在后序线索树上找给定结点p^ 的直接前驱q 的算法【武汉交通科技大学 四(分)】

．用算法说明在对称序穿线树中如何对任意给定的结点直接找出该结点的对称序后继【山东大学 六３(分)】

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