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

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

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

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

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

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

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

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

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

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