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会有系统地,认真地推送:机器学习(包含深度学习,强化学习等)的理论,算法,实践,源码实现。期待您的参与!
或进入公众号界面->导读系列下,找到我的微信,进入微信讨论群。
领取专属 10元无门槛券
私享最新 技术干货