前5篇博客写的都是线性结构，对于有层级结构的数据需要用树形结构来描述
本章的重要知识点
核心一句话
线性结构中一个结点至多只有一个直接后继，树形结构一个结点可以有一个或多个直接后继
看图即可，你要能区分出来哪些是树，哪些不是树
结点的度：树上任意结点所拥有的子树的数目称为该结点的度
叶子：度为0的结点称为叶子或者终端结点
结点的层次：从根算起，根的层次为1，其余结点的层次为其双亲的层次加1
我要评论深度还有一些小概念：有序树、无序树
树的相关术语，一定要一开始就明确清晰，后面才好学习
官方概念：二叉树是n(n≥0)个元素的有限集合，该集合或者为空，或者由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。二叉树的任一结点都有两棵子树（它们中的任何一个都可以是空子树），并且这两棵子树之间有次序关系，交换位置就成为一棵不同的二叉树。
左子树和右子树，也有的叫做左孩子和右孩子
二叉树五种基本形态，方块表示子树
性质1：二叉树第i(i≥1)层上至多有2^i-1^个结点。
不需要死记硬背，实际需要的时候画一个二叉树就可以求出来了
性质2：深度为k（k≥1）的二叉树至多有2^k^-1个结点
依旧可以推导出来
深度为1的二叉树 结点最多为1
深度为2的二叉树 结点最多为3
深度为3的二叉树 结点最多为7
深度为k的二叉树 结点最多为2^k^-1
性质3：对任何一棵二叉树，若度数为0的结点（叶结点）个数为n~0~，度数为2的结点个数为n~2~，则n~0~ = n~2~+1
这个性质需要稍微推导一下
先回答一个问题，你知道树的度数，怎么计算树的结点数
例如 树的度数为2，结点树为几，这个不难想象，会出现如下情况
看到这里不难发现，存在一个公式为 树的度数+1=树的结点树
那么我们开始推导上述公式
假设 二叉树的0度，1度，2度结点个数为n~0~，n~1~，n~2~，结点总数为t
t = n~0~+n~1~+n~2~
树的度数+1 = t
树的度数怎么求？n~0~0+n~1~1+n~2~2 是树的度数
继续n~0~0+n~1~1+n~2~2 +1 = t = n~0~+n~1~+n~2~
===> 2n~2~+1=n~0~+n~2~
===>n~0~=n~2~+1
好了，上述过程，争取看明白吧
性质4：含有n个结点的完全二叉树的深度为
如对本文有疑问， 点击进行留言回复！！
HBase Filter 过滤器之FamilyFilter详解
去 HBase，Kylin on Parquet 性能表现如何？
如何找到Hive提交的SQL相对应的Yarn程序的applicationId
网友评论