二叉树的应用二叉树广泛应用在编译器的设计领域以及在查找中的应用。例如表达式树、二叉查找树。把数据构造为二叉查找树相当于把数据排序。排序就是为了加快查找。树的平衡树的平衡是指任何节点的深度均不得过深。极端不平衡的树相当于链表了而链表实现插入的代价巨大。最古老的平衡查找树AVL树。二叉树的公式第i(i1)层上结点数最大值2supi-1/sup即1、2、4、8、16...。深度为i的树的结点数最大值或从第i(igt;1)到1层所有结点数最大值2supi/sup-1。即1、3、7、15、31。这称为满二叉树。结点总数nnsub2/subnsub1/subnsub0/sub度为0的结点数nsub0/subnsub2/sub1。n个结点的完全二叉树深度⌊logsub2/subn⌋1。深度k1的完全二叉树最少的叶子结点数2supk-2/sup。第i个结点的父结点编号为⌊i/2⌋左孩子编号为2*i右孩子编号为2*i1。第索引i结点的父结点编号为i时左孩子编号为2*i 1右孩子编号为2*i 2。与普通的二叉树不同完全二叉树可以使用数组进行隐式表示无需使用指针。完全二叉树的最后一个父节点的索引为n/2-1n为结点总数。遍历先序、中序、后序遍历是指结果要给出一个顺序表树中的节点关系在顺序表中要满足序类型。都是要从根结点先沿左叉向下深度查找最后根据序类型再给出结果。每个结点的右子树为空的二叉树则其先序序列和中序序列相反。二叉树层次遍历又称层序遍历是从根节点出发‌自上而下、从左到右逐层访问‌每个节点属于‌广度优先搜索BFS‌。‌‌‌核心实现队列法‌根节点入队循环出队一个节点并访问将其‌左、右孩子依次入队‌队列为空时遍历结束‌复杂度‌时间 ‌O(n)‌空间 ‌O(n)‌n为节点数。‌‌‌关键技巧‌若需按层输出结果在每轮循环前‌先记录当前队列长度‌仅处理该层节点即可区分每一层。‌‌‌变种‌锯齿形层序遍历按层奇偶改变左右顺序等。‌‌算法输出二叉树各结点的值//中序遍历 void printtree (BiTree BT) { BiTnode* pBT; InitStruct(s); //构造一个数组结构s s.top0; while (p || s.top!0) { //把p、左子、左子的左子...存入eles。 while (p) { s.eles[s.top]p; pp-gt;lchild ; } if (s.topgt;0) { //输出eles中最后一个元素。 ps.eles[s.top--]; cout lt; lt; p-gt;data;//int poss.top输出的元素将不在eles中继续保存。 //遍历p的右子树 pp-gt;rchild; //在下一次进入循环时eles[pos]会被替换为p即原p的右子结点。 } } }h1树和二叉树的转换/h1树转二叉树1.将所有兄弟连接起来2.保留兄弟中的第一个结点与父结点的连接断开其它的父连接3.结果即是使这条兄弟链变成以兄长为根的子树子树左排列、子树内部右排列森林转二叉树1.将每棵树对应的二叉树的根作为兄弟结点连接起来2.同样遵循子树左排列、子树内部右排列的规则二叉树转森林把二叉树中的所有右子树中的各结点断开连接再连接到父结点h1哈夫曼Huffman树/h1判定树描述分类过程的二叉树。分类问题中的因素有总数N某个类别的属性有名称、条件、占比。二叉树中分叉结点表示判断条件叶子结点表示值。判断树中的问题在于同一个分类问题有不同的分类算法会产生不同的判定树。它们从表面上看有纵深形状或水平形状那么它们的总加权遍历查找的计算量也不同。则判定树中要研究的课题是要使平均比较次数计算量最小。哈夫曼算法和哈夫曼树1.给定一组类别{p1p2...pk}构造初始森林{T1T2...Tk}2.从森林中选两个根结点权即占比最小的树合并它们分别为新树的左右子树新树的根结点权为左右子结点权之和。3.直到森林中只剩一棵二叉树即哈夫曼树。哈夫曼树中共有2n-1个结点其中n个叶结点是初始森林中的n个结点。哈夫曼编码堆是一种特殊的完全二叉树它满足一个关键特性堆顶是最大值或最小值。