我要招人

去企业版

首页 > 试题广场 >

以下哪种二叉树左右子树可以交换（）。

[单选题]

以下哪种二叉树左右子树可以交换（）。

```
二叉排序树
```
```
线索二叉树
```
```
平衡二叉树
```
```
哈夫曼树
```

查看答案及解析

CpInsist

一模一样的题，上次答案还是C：平衡二叉树！

发表于 2016-12-03 12:21:57 回复(3)

mike-1020

哈夫曼树又叫最优二叉树，是一种特殊的二叉树。

最重要的特征就是：树的带权路径长度最小。

哈夫曼树的构造并不唯一，因为其左右子树位置交换，并不影响该二叉树的带权路径长度最小的性质。

发表于 2017-02-02 00:06:58 回复(0)

心海盗梦

平衡二叉树是二叉排序树，为什么还左右子树可以交换？

发表于 2017-04-28 18:42:13 回复(7)

3kna1j

二叉排序树（BST）：左子节点的值一定比当前根节点的值小，右子节点的值一定比当前根节点的值大，左右子树不可交换

平衡二叉树（AVL）：在BST中，如果数据为[1,2,3,4,5]这样的集合，直接生成的BST将会退化为链表（因为全在右子节点上），影响查找效率（链表需要从头遍历），因此需要通过“旋转”等方式，把BST进行一个“平衡”，因此AVL实际上是一个优化过的BST，左右子树不可交换

线索二叉树： 在链式存储二叉树的的基础上，充分利用空指针域存放该节点在某种遍历次序下的前驱结点和后继结点，使得链式存储结构变为顺序存储结构，记录前驱和后继的指针成为线索，这种二叉树就是线索二叉树。由于交换左右节点后，遍历的顺序可能不一致，因此“线索”也会变得不准确，因此不能直接交换

哈弗曼树：只要使得树的带权路径长度最小即可，不需要考虑顺序以及位置。

发表于 2021-02-04 16:11:36 回复(0)

孤单的跟鞋声和你的笑丶

老师说哈弗曼树左节点小右节点大根节点又比右节点大，这样可以左右交换吗？

发表于 2020-10-30 09:38:14 回复(1)

hanfu

平衡二叉树的定义：左右子树的高度差不超过1；左右子树均是平衡二叉树；

二叉排序树与平衡二叉树之间无关系；提出平衡二叉树就是为了解决二叉排序树：n个结点，其树深度逼近logn/log2-----即平衡二叉排序树

发表于 2017-08-12 11:11:18 回复(0)

InGodWeTrust

哈夫曼树为给定的n个权值作为n个叶子节点构造的一颗二叉树，其要求带权路径长度达到最小。左右子树顺序不唯一。

发表于 2017-04-08 10:11:36 回复(0)

牛客415897573号

鄙人拙见：讨论这个问题没有多大意义，照本人所学教材，以上所有二叉树均不可调换左右子树。二叉树调换左右子树后并不是同一棵树了。（当然你可以定义什么叫 “可以调换” ，如“不影响树的性质”）

考研的同学可以看看这里，主要是把概念弄清楚就行。

严蔚敏、吴伟民著，《数据结构（C语言版）》，清华大学出版社，2016

1、二叉树(Binary Tree)是另一种树形结构，它的特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。（121页）

2、最优二叉树（赫夫曼树）: 假设有n个权值{W₁,W₂,..,W_n}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为W_i，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。（144页）

3、二叉排序树（Binary Sort Tree）或者是一棵空树；或者是具有以下性质的二叉树：（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）它的左、右子树也分别为二叉排序树。（227页）

4、平衡二叉树（Balanced Binary Tree 或 Height-Balanced Tree）又称AVL树。它或者是一棵空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF(Balance Factor)定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

...我们希望由任何初始序列构成的二叉排序树都是AVL树。因为....（233页）

（由此可见按本教材定义，二叉排序树和AVL树并非有从属关系，而以上所有这些树均为二叉树）

题外话：教材中除了二叉树定义处，并无再讨论“左右子树（孩子）是否可以调换次序”的话题，本人目前所做的题目以及试卷，也并未出现这类问题。可见它确实不是十分重要，没有必要纠结。

发表于 2023-10-16 19:27:47 回复(0)

看见我请叫我去刷题

平衡树一定是排序树，就是为了解决高度差过大问题，AVL

发表于 2022-04-08 17:10:16 回复(0)

凡纳提克

这是一道多选题，答案选CD

发表于 2018-11-19 19:06:16 回复(0)

宸신

平衡二叉树不是特殊的二叉排序树嘛？？？

发表于 2018-08-12 15:34:56 回复(0)

Favourite流沙

我认为答案只有一个，就是 D

发表于 2018-08-04 22:44:15 回复(0)

zurp

怎么说呢，主要是“又称”这个词造的孽，以后做题根据要求和答案来看名称表示的具体意义吧

发表于 2018-04-07 10:37:23 回复(0)

GeekZW

空的左孩子指针指向该结点的前驱；空的右孩子指针指向该结点的后继。这种附加的指针值称为线索，带线索的二叉树称为线索二叉树。

发表于 2018-04-01 14:35:24 回复(0)

女。。。

平衡二叉树的前提是二叉排序树，不能交换，

发表于 2017-11-23 20:28:18 回复(0)

霸王小小花

平衡二叉树是一种特殊的二叉排序树，怎么可以交换？

发表于 2017-09-09 14:28:59 回复(0)

飘过的小牛

什么鬼？

发表于 2017-09-02 14:10:22 回复(0)

Noiz

平衡二叉树又称为AVL树，它具有以下特征：
它是一棵空树或它的左右两个子树的高度差（称为平衡因子）不大于1的二叉排序树。怎么可以交换左右子树？

发表于 2017-06-27 17:15:32 回复(0)

提交观点

问题信息

树

上传者：城市里的养猫者

难度：

18条回答 300收藏 6760浏览

以下哪种二叉树左右子树可以交换（）。

问题信息

热门推荐

相关试题