题目内容
(请给出正确答案)
提问人:网友13***002
发布时间:2022-01-07
[主观题]
设一棵树的存储表示为子女-兄弟链表,编写一个算法无重复地输出树中所有的边,要求输出的形式为
(k1,k2),…,(ki,kj),…,其中ki,和kj,为树结点的标志。
简答题官方参考答案
(由简答题聘请的专业题库老师提供的解答)
查看官方参考答案
(1)沿袭5-60题使用逆转链遍历二叉树的思想。
(2)不使用tag标志,而是用内嵌的栈代替tag的作用。该内嵌的栈使用了叶结点作为栈的结构,没有另外定义栈的存储空间。
(3)利用栈解决在回溯时分辨究竟是从左子树还是右子树上升的问题,步骤是:
①当进入有非空左子树的结点的右子树时,将该结点的地址进栈。
②在回溯过程中如遇到结点的左、布子树都非空时,如果该结点就是存于栈顶的结点,则可判定当前是从该结点的右子树退回,该结点的右子女指针指向它的父结点;否则当前是从该结点的左子树退回,该结点的左子女指向它的父结点。
(1)树的根结点作为内子树构成的表的表名,放在表的最前面。
(2)每个结点的左子树和右子树用逗号隔开。若仅有在子树没有左子树,则逗号不能省略。
(3)在整个广义表表示输人的结尾加上一个特殊的符号(例如)表示输入结束。例如,对于如图5-26所示的二叉树,广义表表示为:A(B(D,E(G,)).C(,F))
为了保护您的账号安全,请在“简答题”公众号进行验证,点击“官网服务”-“账号验证”后输入验证码“”完成验证,验证成功后方可继续查看答案!