线性表是 约束比较轻的逻辑结构
加一些约束 就得到了 栈 和 队列
同样 树 也可以看作 约束比较轻 的逻辑结构,
树中每个结点可以有任意多个孩子结点,
每个结点的孩子结点是没有次序之分的。
加上约束 :
①每个结点的 孩子结点 最多有两个
②对每个结点的孩子结点 规定上次序,一个称之为左孩子,另一个称之为右孩子。
满二叉树:
除了最底层结点外,所有的结点都有左右两个孩子。
完全二叉树:
简单来说,对于一棵满二叉树,从最底层开始,从右往左,逐渐的删除结点得到的二叉树。
满二叉树 是特殊的 完全二叉树。
满二叉树 高度与结点的关系
高度为h 结点个数为 2^h -1
“|_ _|” 是 向下取整
向上取整
公式
不是第一种 就是第二种
完全二叉树中 出现叶子结点的层,要不是倒数第二层,要不是最后一层。
要结点个数最多的情况,则第六层 为 倒数第二层
前六层 是 满二叉树,63个。
1、2、4 则 a1 = 1,q = 2
Sn = 2^n - 1
an = a1 * 2^(n-1)
a6 = 32
(32 -8)*2 = 48
48 + 63 = 111
叶子结点数 = 双分支结点数 + 1
画出空分支(在没有挂子结点的地方 给它标记出来)
有些题会问你空分支有 多少个
可以在空分支处 画上节点 也就是叶子节点
那么树中原来的节点 都变为 双分支节点
根据叶子节点 = 双分支节点 + 1
空分支个数 = 结点总数 + 1
这种方式 只适合存 完全二叉树,对于一般二叉树是不行的。
注意起始结点编号 是从0开始还是从1开始 ,会有稍微不同。
虽然简单 ,但是有局限性,只适用于存储完全二叉树
每个结点有三个域:
一个数据域,左边一个指针域,右边一个指针域,分别指向左孩子和右孩子结点。
二叉链表存储结构:
貌似这种存储结构是专门存放二叉树的,
但是这种存储结构可不可以来存储一般的树,
肯定有同学说 那肯定不行。
因为树的孩子结点可能有多个,多于两个的情况就存不了了。
换个角度考虑一下。
对于一棵树而言,最重要的逻辑关系是 其父节点和孩子节点的关系。
一定要有 父节点 能找到它的孩子节点。
但是不必要父节点和孩子节点 都有直接的关系。
之前那个 树的链式存储 也体现了 这种做法
网友评论