问题 单项选择题

在平衡二叉树中,()。

A.任意节点的左、右子树节点数目相同

B.任意节点的左、右子树高度相同

C.任意节点的左、右子树高度之差的绝对值不大于1

D.不存在度为1的节点

答案

参考答案:C

解析:

平衡二叉树又称AVL树。它或者是一棵空树,或者是具有下列性质的二叉树。

①左子树和右子树都是平衡二叉树;

②左子树和右子树的深度之差的绝对值不超过1;

③二叉树上节点的平衡因子定义为该节点的左子树的深度减去它的右子树的深度。

由此可见,平衡二叉树上所有节点的平衡因子只可能是-1,0,1。只要二叉树上有一个节点的平衡因子的绝对值大于1,则该二叉树就是不平衡的。

选择题
单项选择题