二叉树
树的基本概念
父节点：在树结构中，每一个节点只有一个前件，称为父节点，没有前件的称为根节点，简称树的根。
子节点和叶子节点：在树结构中每一个结点可以有多个后件，称为该结点的子节点，没有后件的节点称为叶子节点。
度：在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。
深度：定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。
子树：在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。
二叉树的6个重要性质
二叉树（Binary Tree）：是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树构成；
二叉树的特点是：（1）二叉树可以为空，空的二叉树没有结点，非空二叉树有且只有一个根结点；（2）每个结点最多有两棵子树，即二叉树中不存在度大于2的结点。（3）二叉树的子树有左右之分，其次序不能任意颠倒；
满二叉树和完全二叉树
满二叉树：指除了最后一层外，每一层上的所有结点都有两个子结点的二叉树；
满二叉树在其第i层上有2(i-1)（上角标）个结点，即每一层上的结点数都是最大结点；
一棵深度为K的满二叉树，整颗二叉树共有2（K）（上角标）-1个结点；
完全二叉树：指除最后一层外，每一层上的结点树均达到最大值，在最后一层上只缺少右边的若干结点。
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树；
完全二叉树的叶子结点只可能在最后两层出现；
对于任一结点，若其右子树的深度为m，则该结点左子树的深度为m或为m+1；
二叉树的基本性质
在二叉树的第K层上，最多2^(k-1)（k>=1）个结点。
深度为K的二叉树中，最多有2^(k-1)个结点；
对任何一颗二叉树，度为0的结点总是比度为2的结点多一个；
具有n个结点的二叉树，其深度至少为[log2 n]+1，其中[log2 n]表示取其中的整数部分；
具有n个结点的完全二叉树的深度为[log2 n]+1；
设完全二叉树共有n个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1，2，3……n给结点进行编号，有以下结论：
若i=1，则该结点为根结点，它没有父结点；若i>1,则该结点的父节点编号为[i/2]，其中结果只取整数部分；
若2i>n，该结点无左子结点也无右子结点；若2i<=n,则编号为i的结点的左子结点编号为2i；
若2i+1>n,则该结点无右子结点；若2i+1<=n,则编号为i的结点的右子结点编号为2i+1；
注意：性质5和性质6是完全二叉树和满二叉树特有的；
二叉树的存储结构
左指针域+数据域+右指针域
由于二叉树每一个存储结点有两个指针域，因此二叉树的链式存储结构也称为二叉链表。对于满二叉树和完全二叉树可以按层次进行顺序存储；
二叉树的遍历
二叉树的遍历是指不重复地访问二叉树（非线性结构）中的所有结点。在先左后右的原则下，根据访问根结点的次序不同，二叉树的遍历可以分为3种：前序遍历、中序遍历、后序遍历。
前序遍历（DLR）：若二叉树为空，则空操作，否则访问根节点，然后前序遍历左子树，前序遍历右子树。（“前”的含义是，访问根结点在访问子树之前；）
中序遍历（LDR）：访问根结点在访问左子树和访问右子树两者之间；
后序遍历（LRD）：最后访问根结点；
注意：
已知一颗二叉树的前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树；
已知后序和中序也可以，但已知前序和后序则不行；
Last updated