C/C++

C++ 数据结构(五)二叉树(3)二叉树概述

上一篇:《C++ 数据结构(五)二叉树(2)树的表示》

二叉树

节点度数 不超过2 的树称作二叉树(binary tree)

同一节点的孩子和子树,均以左、右区分

lChild() ~ lSubtree()

rChild() ~ rSubtree()

隐含有序

1.png

基数

深度为 k 的节点,至多 2^k

n 个节点、高度为 h 的二叉树中,h < n < 2^(h+1)

n = h + 1 时,二叉树退化为一条单链

n = 2^(h+1) - 1 时,即所谓满二叉树(full binary tree)

2.png

真二叉树

所谓真二叉树,就是节点的出度只能为 20 的二叉树

3.png

用二叉树描述多叉树

二叉树是多叉树的特例,但在有根且有序时,其描述能力却足以覆盖后者

多叉树均可转化并表示为二叉树 —— 回忆长子兄弟表示法

4.png

下一篇:《C++ 数据结构(五)二叉树(4)二叉树实现》

OceanicKang
心若浮沉,浅笑安然
查看“OceanicKang”的所有文章 →

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关推荐