首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >基本算法|图解各种树(一)

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

作者头像
double
发布2018-04-02 14:52:01
9540
发布2018-04-02 14:52:01
举报
文章被收录于专栏:算法channel算法channel

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的实数和整个轴上的实数一样多相似。

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

方法:长子-兄弟法

多叉树如下:

长子-兄弟表示后:

整理上图:

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

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-01-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员郭震zhenguo 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档