将一棵树转换为二叉树后，为什么根节点没有右子树

2025-04-27 13:42:17

推荐回答（2个）

回答1：

树转化为二叉树时结点左子树是原来的孩子结点，右子树是原来的兄弟结点。即取根节点左孩子向右连接他的兄弟结点（在同一层次的节点，原来互不相连）并把它的子树，而把除左孩子外，原来与根节点相连的线擦除。这样根节点没有右孩子，因为由树转化来的二叉树某个节点A的左子树是原来作为树时A的孩子，其右子树是他的兄弟。
希望你能看懂~~

回答2：

有xx个节点的二叉树最少可以是1个叶子节点（即一条路径走到底，不拐弯）。最多可以是
argmax_y(xx-2^y+1
|
2^y-1该过程中每减少一个出度为1的路径结点则增加一个叶子，所以答案可以是1~最多个节点。