节点A的度是2吗？怎么看？树的度是3吗？怎么看？画出其转换为相应的二叉树树型

Chis_喵 · 2018-4-30 01:58:03

Chi's喵！为你解答~！

问题1：“节点A的度是2吗？怎么看？"

一个结点所拥有的后继个数称为该结点的度

结点A有 B和C两个后件因此结点A的度是2

问题2："树的度是3吗？怎么看？"

所有结点最大的度称为树的度

在整棵树中 B的后件最多共有D、E、F三个因此结点B是树的度结点B的度是3 树的度是3

问题3：“画出其转换为相应的二叉树树型”

多叉树转为二叉树的要点：左孩子，右兄弟

下图为原树：                                           A
                                                         ↙ ↘
                                                         B       C
                                                   ↙↓↘    ↓ ↘
                                                   D E F G H
                                                ↙ ↓    ↙ ↘ ↘
                                             I    J    L    M    N
                                                ↘                ↙       ↘
                                                   K             O             P

多叉树转为二叉树的第一步：“加线”  连接孩子节点中各兄弟节点

（即是将同父的结点连接如原来结点A的孩子B、C他们就是兄弟不同父亲的结点不是兄弟如结点D的孩子I和结点E的孩子J 虽然在同一层但是他们的父亲不一样因此结点I和J不是兄弟别弄混了）

得到下图：                                              A
                                                         ↙ ↘
                                                         B — C
                                                   ↙↓↘    ↓ ↘
                                                   D - E - F G - H
                                                ↙ ↓    ↙ ↘ ↘
                                             I    J    L — M    N
                                                ↘                ↙       ↘
                                                   K             O             P

多叉树转为二叉树的第二步：“抹线”  断开除最左孩子的孩子节点连接线
                                                               ▲ ▲
（注意是最左  即某一结点只有一个右孩子那么它也算是该结点中最左的孩子例如图中H的孩子N 它是结点H的最左孩子）

得到下图：                                              A
                                                         ↙
                                                         B —  C
                                                      ↙          ↓
                                                   D - E - F G - H
                                                ↙ ↓    ↙       ↘
                                             I    J    L — M    N
                                                ↘                ↙       ↘
                                                   K             O             P

多叉树转为二叉树的第三步：“旋转”将树顺时针旋转45度

（这时就要记住要点 “左孩子，右兄弟” 孩子要放在结点的左边兄弟要放在结点的右边）

得到下图：                                                                         A
                                                                                    ↙
（B是A的孩子所以放在左边）                                  B
（D是B的左孩子放左边 C是兄弟放右边）       ↙          ↘
（接下来是同样的道理）                                  D                   C
                                                                  ↙ ↘                ↙
                                                               I    E          G
                                                               ↙    ↙  ↘    ↙  ↘
                                                            K    J       F L    H
                                                                                       ↘    ↘
                                                                                          M       N
                                                                                       ↙          ↘
                                                                                    O                P
这样多叉树转为二叉树的过程就结束了。

纯手打~希望能帮到您~！

jyukichen · 2018-4-30 01:58:04

节点a的度是2
一个节点的度，就是他连出去几条边（几个儿子，父亲不算）
树的度是3，他的值为度最大的那个结点的度
二叉树如下，横着的边是右儿子

节点A的度是2吗？怎么看？ 树的度是3吗？怎么看？ 画出其转换为相应的二叉树树型

2 个回复

节点A的度是2吗？怎么看？树的度是3吗？怎么看？画出其转换为相应的二叉树树型