二叉树-数据结构

二叉树-数据结构

二叉树是属性结构的一个重要类型。
如下图二叉树形状

二叉树特征如下：
1.二叉树由 n(n >= 0) 个节点组成
2.如果 n 为 0，则为空树
3.如果 n = 1，则只有一个节点称为根节点(root)
4.每个节点最多有两个节点，节点分为左子树和右子树
5.所有左子树和右子树自身也必须是二叉树

如上图
节点6 是 跟节点 root
节点6 的左子树和右子树 分别是 节点4 和 节点8

名词概念：
节点：包含一个数据元素 及指向若干个子树 信息
节点的度：一个节点拥有子树的数量称为节点的度
叶子节点：也称为终端节点，没有子树的节点或者 度为零的节点
分支节点：也成非终端节点，有子树的节点或者 度不为零的节点
树的度：树中所有节点的度的最大值
树的层次：从根节点开始，假设根节点是第一层，根节点的子节点为第二层，一次类推，如果某一个节点位于第L层，则其子节点位于第 L+1层
树的深度：也成树的高度，树中所有节点的层次最大值称为树的深度
节点的深度：从根节点到节点的路径长度
节点的高度：从节点到其子树叶子节点最长的路径