二叉树知识整理

1.1.树的定义树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点，还(很可能)有多个附加结点，所有结点构成一个多级分层结构。⭐特点：树状图是一种数据结构，它是由n（n=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；⭐种类：无序树：树中任意节点的子结点之间没有顺序关系，这种树称为无序树,也称为自由树;有序树：树中任意节点的子结点之间有顺序关系，这种树称为有序树；二叉树：每个节点最多含有两个子树的树称为二叉树；完全二叉树：在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者是在右边缺少连续若干节点，则此二叉树为完全二叉树。满二叉树：一棵深度为i，且有2i-1个节点的二叉树，称为满二叉树。霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；1.2.二叉树相关术语1)节点的度：一个节点含有的子树的个数称为该节点的度；2)叶节点或终端节点：度为0的节点称为叶节点；3)非终端节点或分支节点：度不为0的节点；4)双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；5)孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；6)兄弟节点：具有相同父节点的节点互称为兄弟节点；7)树的度：一棵树中，最大的节点的度称为树的度；8)节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；9)树的高度或深度：树中节点的最大层次；10)堂兄弟节点：双亲在同一层的节点互为堂兄弟；11)节点的祖先：从根到该节点所经分支上的所有节点；12)子孙：以某节点为根的子树中任一节点都称为该节点的子孙。13)森林：由m（m=0）棵互不相交的树的集合称为森林；1.3.树的深度：定义一棵树的根结点层次为1，其他节点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度二.二叉树（BinaryTree)2.1什么是二叉树（BinaryTree)1）定义：二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。⭐特点：每个结点至多拥有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。注意，在二叉树中，与数组等等计算机编程不同，树的顶端为第1层，而非第0层。⭐类型：(1)完全二叉树——若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。⭐辨析：二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：1.树中结点的最大度数没有限制，而二叉树结点的最大度数为2；2.树的结点无左、右之分，而二叉树的结点有左、右之分。2.2相关术语：1)树的结点（node）：包含一个数据元素及若干指向子树的分支；2)孩子结点（childnode）：结点的子树的根称为该结点的孩子；3)双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；4)兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；5)祖先结点:从根到该结点的所经分支上的所有结点子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙6)结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；7)树的深度：树中最大的结点层8)结点的度：结点子树的个数9)树的度：树中最大的结点度。10)叶子结点：也叫终端结点，是度为0的结点；11)分枝结点：度不为0的结点；12)有序树：子树有序的树，如：家族树；13)无序树：不考虑子树的顺序；2.3二叉树的性质(1)在非空二叉树中，第i层的结点总数不超过,i=1；(2)深度为h的二叉树最多有个结点(h=1)，最少有h个结点；(3)对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；(4)具有n个结点的完全二叉树的深度为（注：[]表示向下取整）(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：A.若I为结点编号则如果I1，则其父结点的编号为I/2；B.如果2*I=N，则其左孩子（即左子树的根结点）的编号为2*I；若2*IN，则无左孩子；C.如果2*I+1=N，则其右孩子的结点编号为2*I+1；若2*I+1N，则无右孩子。(6)给定N个节点，能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n，n)/(n+1)。(7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i2.4完美二叉树(PerfectBinaryTree)一个深度为k(=-1)且有2^(k+1)-1个结点的二叉树称为完美二叉树。(注：国内的数据结构教材大多翻译为满二叉树)例如：2.5完全二叉树(CompleteBinaryTree)换句话说，完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。例如：2.6完满二叉树(FullBinaryTree)换句话说，所有非叶子结点的度都是2。（只要你有孩子，你就必然是有两个孩子。）注：FullBinaryTree又叫做StrictlyBinaryTree。例如：2.6完美(Perfect)二叉树v.s.完全(Complete)二叉树(1)一棵完美(Perfect)二叉树看起来是这个样儿的，（2）那么，将编号为15,14,...,9的叶子结点从右到左依次拿掉或者拿掉部分，则是一棵完全(Complete)二叉树,例如，将上图中的编号为15,14,13,12,11叶子结点都拿掉(从右到左的顺序)，（3）下图就不是一棵完全(Complete)二叉树，如果将编号11(K)结点从编号6(E)的左儿子位置移动到编号5(E)的右儿子位置，则变成一棵完全(Complete)二叉树。三、二叉树的遍历1.先序遍历若树为空，则空操作返回。否则，先访问根节点，然后前序遍历左子树，再前序遍历右子树。（W）型（中左右）2.中序遍历若树为空，则空操作返回。否则，从根节点开始（注意并不是先访问根节点），中序遍历根节点的左子树，然后是访问根节点，最后中序遍历根节点的右子树。（M）型，（左中右）3.后序遍历若树为空，则空操作返回。否则，从左到右先叶子后节点的方式遍历访问左右子树，最后访问根节点。（左右中）逆时针型（左右中）4.层序遍历若树为空，则空操作返回。否则，从树的第一层，也就是根节点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序结点逐个访问。