图解各种树(一)

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

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

方法:长子-兄弟法

多叉树如下:

长子-兄弟表示后:

整理上图:

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

算法channel会有系统地,认真地推送:机器学习(包含深度学习,强化学习等)的理论,算法,实践,源码实现。期待您的参与!

或进入公众号界面->导读系列下,找到我的微信,进入微信讨论群。

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20180124G00PQM00?refer=cp_1026

扫码关注云+社区