将树T转换成一棵二叉树

flnta76 · 2018-4-30 02:31:58

普通树为有序树T，将其转化成二叉树T’的规则如下：
⑴T中的结点与T’中的结点一一对应，即T中每个结点的序号和值在T’中保持不变；
⑵T中某结点v的第一个儿子结点为v1，则在T’中v1为对应结点v的左儿子结点；
⑶T中结点v的儿子序列，在T’中被依次链接成一条开始于v1的右链；
由上述转化规则可以看出，一棵有序树转化成二叉树的根结点是没有右子树的，并且除保留每个结点的最左分支外，其余分支应去掉，然后从最左的儿子开始沿右儿子方向依次链接该结点的全部儿子。例如将图（a）所示的普通有序树转换成二叉树(图（b）)。
如果还没解决你的问题，可以加我百度HI账号。

将树T转换成一棵二叉树

1 个回复