二叉树

2019-08-10 本文已影响0人 YY_Lee

介绍二叉树之前先说下树状结构，不同于线性结构只有前后两个方向，树状结构可以有多个方向。

tree.png

每个节点的度最大为2，左子树和右子树是有序的，即使只有一颗子树也要区分左右的树是二叉树；

BinaryTree.png

所有节点的度要么为0，要么为2的二叉树称为真二叉树；

最后一层节点的度为0，其他节点的度都为2的二叉树称为满二叉树；

满二叉树.png

对一棵具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树

完全二叉树.png

叶子节点只会出现最后两层，最后一层的叶子节点都靠左对齐的二叉树
从根节点至倒数第二层是一棵满二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
度为1的节点只有左子树
度为1的节点要么是1个，要么是0个
同样节点数量的二叉树，完全二叉树的高度最小
假设完全二叉树的高度为h(h≥1)，那么
至少有 $2^{h-1}$ 个节点( $2^{0}$ + $2^{1}$ +···+ $2^{h-2}$ + 1)
最多有 $2^{h}$ - 1个节点( $2^{0}$ + $2^{1}$ +···+ $2^{h-1}$ ) ，满二叉树)
若总结点数为n
$2^{h-1}$ ≤ n ＜ $2^{h}$ => h -1≤ ${log_2{n}}$ < h => h = floor( ${log_2{n}}$ ) + 1
一棵有n个节点的完全二叉树(n>0)，从上到下、从左到右对节点从1开始进行编号，对任意第i个节点

排序完全二叉树.png

若i=1，它是根节点
若i>1,它的父节点编号是floor(i/2)
若2i≤n，它的左子节点编号为2i
若 2i＞n，它无左子节点
若2i+1 ≤n，它的右子节点编号为2i+1
若2i+1 ＞n，它无右子节点

从图中可以看到，对于节点i，它的左子节点等于2i，右子节点等于2i+1；