首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

基本算法|图解各种树(一)

01

二叉树

节点的度数不超过2的树,称为二叉树,如下图所示:

02

单链和满二叉树

含n个节点,高度为h的二叉树中,满足如下关系:

h < n < 2^(h+1)

当 n = h+1 时,退化为一条单链,

当 n = 2^(h+1) -1 时,是一棵满二叉树,如下图所示:

03

真二叉树

节点的出度为0或2,不能为1的二叉树,称为真二叉树。

为了构造真二叉树,需要虚拟一些节点,是画蛇添足吗?当然不是,为了代码实现更为简洁明了。

04

二叉树实现多叉树

二叉树明明是多叉树的特例,怎么可能用二叉树描述多叉树呢?这出乎意料,但是的确是可能的,就像是0~0.1的实数和整个轴上的实数一样多相似。

条件:在有根且有序的前提下。

方法:长子-兄弟法

多叉树如下:

长子-兄弟表示后:

整理上图:

结论,因为多叉树可以转化为二叉树,所以只需研究二叉树即可。

下一篇
举报
领券