C++ 数据结构(五)二叉树(3)二叉树概述
     发布在:C/C++      浏览:44      评论:0 条评论

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

二叉树

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

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

lChild() ~ lSubtree()

rChild() ~ rSubtree()

隐含有序

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

基数

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

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

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

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

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

真二叉树

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

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

用二叉树描述多叉树

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

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

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

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

Responses