二叉树概念
在计算机科学中，二叉树是每个结点最多有两个子树的树结构。一般子树被称作“左子树”和“右子树”。二叉树常被用于完成二叉查找树和二叉堆。
二叉树分类
彻底二叉树A8站源码交易平台
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都到达最大个数，第h层有叶子结点，而且叶子结点都是从左到右顺次排布，这便是彻底二叉树。
满二叉树
除了叶子结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树
平衡二叉树
它是一棵空树或它的左右两个子树的高度差的绝对值不超越1，而且左右两个子树都是一棵平衡二叉树。
相关术语解说
树的结点：包括一个数据元素及若干指向子树的分支；
孩子结点：结点的子树的根称为该结点的孩子；
双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；
兄弟结点：同一双亲的孩子结点； 堂兄结点：同一层上结点；
先人结点: 从根到该结点的所经分支上的一切结点
后代结点：以某结点为根的子树中任一结点都称为该结点的后代
结点层：根结点的层界说为1；根的孩子为第二层结点，依此类推；
树的深度：树中最大的结点层
结点的度：结点子树的个数
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为 0 的结点；
分枝结点：度不为0的结点；
有序树：子树有序的树，如：宗族树；
无序树：不考虑子树的次序；
二叉树性质
(1) 在非空二叉树中，第i层的结点总数不超越2的i-1次方 , i>=1；
(2) 深度为h的二叉树最多有2的h次方减1个结点(h>=1)，最少有h个结点；
(3) 关于恣意一棵二叉树，假如其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
(4) 具有n个结点的彻底二叉树的深度为[2为底n的对数]+1 （注：[ ]表明向下取整）
(5)有N个结点的彻底二叉树各结点假如用次序方法存储，则结点之间有如下联系：
若I为结点编号则 假如I>1，则其父结点的编号为I/2；
假如2*I<=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*I>N，则无左孩子；
假如2*I+1<=N，则其右孩子的结点编号为2*I+1；若2*I+1>N，则无右孩子。
(6)给定N个节点，能构成h(N)种不同的二叉树。
h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。
(7)设有i个枝点，I为一切枝点的路途长度总和，J为叶的路途长度总和J=I+2i
二叉树的遍历方法
先序遍历
先拜访根节点，先序遍历左子树，先序遍历右子树
中序遍历
中序遍历左子树，拜访根节点，中序遍历右子树
后序遍历
后序遍历左子树，后序遍历右子树，拜访根节点
层次遍历
即依照层次拜访，一般用行列来做。拜访根，拜访子女，再拜访子女的子女
特别的二叉树
堆
堆具有以下性质：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
二叉查找树(BST)
二叉查找树的特色：
若恣意节点的左子树不空，则左子树上一切结点的 值均小于它的根结点的值
若恣意节点的右子树不空，则右子树上一切结点的值均大于它的根结点的值
恣意节点的左、右子树也分别为二叉查找树
没有键值持平的节点
红黑树
红黑树具有以下性质：
每个节点非红即黑
根节点总是黑色的
每个叶子节点都是黑色的空节点（NIL节点）
假如节点是赤色的，则它的子节点有必要是黑色的（反之不一定）
从根节点到叶节点或空子节点的每条途径，有必要包括相同数目的黑色节点（即相同的黑色高度）
