二叉树

Binary Tree,第i(i>=1)层上结点数最大值:2i-1。即1、2、4、8、16…。
深度为i的树的结点数最大值,或从第i(i>=1)到1层所有结点数最大值:2i-1。即1、3、7、15、31。这称为满二叉树。满二叉树的结点数为2k-1,只有度为0和2的结点,并且叶结点都处在最下层。
结点总数n=n2+n1+n0,度为0的结点数n0=n2+1,即叶结点数比双分支的结点数多1个。
二叉树中序号大于n/2的结点没有孩子结点。
完全二叉树中度为1的结点数是0或1。
完全二叉树,n个结点,深度=⌊log2n⌋+1。
完全二叉树,若深度k>1,则 2k-1>=叶子结点数>=2k-2,结点数>=2k-1
深度为k的二叉树,结点数最多为2k-1,最少为k。
深度为k的二叉树,若只有度为0、2的结点,结点数最少为2k-1。
第i个结点的父结点编号为⌊i/2⌋,左孩子编号为2*i,右孩子编号为2*i+1。
n个结点的二叉树的二叉链表中,有2n个指针域,n-1个指针域不为空,n+1个指针域为空,结果发现2n没有被平分,而是多出了一个空指针域是因为根结点没有被指向。
n个结点的二叉树的三叉链表中,除了具有二叉链表的统计结果,然后所有parent指针中只有根结点的parent指针为空。

结点的度:结点的子树的数目。
树的度:树中最大的结点度。
树的高度:也叫深度,即从1开始的最大层次数。
树的出度:树中结点度为D(D>=0)的结点的个数与D的乘积。
树的结点数=各个度(0到树的度)的结点的个数之和=各个结点的度之和再加一。

存储

完全二叉树的顺序存储结构中,编号为i的结点的层次为⌈log2(i+1)⌉ 。

二叉树的链式存储结构中,三叉链表比二叉链表的结点中多了一个parent指针域。

遍历

PreOrder、InOrder、PostOrder、LevelOrder。
先序序列的第一个结点是根结点,后序序列的最后一个结点是根结点,中序序列中由根结点将序列分为为两部分。

先序序列和中序序列相反,则二叉树每个结点只有左子树,左单极树。
先序序列和中序序列相同,则二叉树每个结点只有右子树。
先序序列和后序序列相反,则二叉树高度和结点数相同即可。
先序序列和后序序列相同,则二叉树只有一个根结点。
从一个遍历序列推导出不同形状的二叉树,首先宽二叉树,然后是多种每层单节点二叉树。

中序序列中前后结点在二叉树中的关系是,前面的结点在后面的结点的左边,左边是指左子或其所在分支的父。
交换所有分支左右子树的位置,利用前序遍历方法最合适。
一棵二叉树的前序序列和中序序列,或后序和中序序列可唯一确定这棵二叉树。在先序中第一个字符是根结点,而在后序中最后一个字符是根结点。在中序中,根结点前后分别是其左右子树。按照这个思想递归可推导出二叉树。
方法一:以中序为主线,在前序中找中序的根:
1.在中序中,由树的根分左序L,右序R。在先序中找到排在根后面的第一个L中的值,即为根的左结点。同样地,在先序中找到排在根后面的第一个R中的值,即为根的右结点。在中序中标记根值为墙表示它是已处理完毕的界线,在树中对字符画圈也表示它已处理完毕。
2.再把左右两个结点分别视为根,依次进行步骤1。
当是在后序序列中辅助查找时,方向是从后向前。

遍历实现

1.二叉链表上遍历的递归实现。还可以利用递归遍历求得二叉树的高度为较高的子树的高度加1。
2.二叉树的层次遍历可以借助队列来实现。将根结点入队列,从队列中出一个结点,将该结点的左右孩子结点入队列。如此出入直至队列为空。则入队列或出队列的顺序即为层次遍历的序列。
3.二叉树顺序存储或链式存储上的非递归实现可以借助栈来实现。

算法:输出二叉树各结点的值

//中序遍历
void printtree (BiTree BT)
{
  BiTnode* p=BT;
  InitStruct(s); //构造一个数组结构s
  s.top=0;
  
  while (p || s.top!=0)
  { 
    //把p、左子、左子的左子...,存入eles。
    while (p)
    { 
      s.eles[s.top++]=p;
      p=p->lchild ;
    }
    
    if (s.top>0)
    { 
      //输出eles中最后一个元素。
      p=s.eles[s.top--];
      cout < < p->data;//int pos=s.top,输出的元素将不在eles中继续保存。
      //遍历p的右子树
      p=p->rchild; //在下一次进入循环时,eles[pos]会被替换为p,即原p的右子结点。
    }
  }
}

树和二叉树的转换

树转二叉树:
1.将所有兄弟连接起来;
2.保留兄弟中的第一个结点与父结点的连接,断开其它的父连接;
3.结果即是使这条兄弟链变成以兄长为根的子树,新枝都变为右枝,旧枝变为左枝;
转换后得到的二叉树的根结点的右子树总是空的。

森林转二叉树:
1.将森林中的每棵树转为二叉树;
2.将每棵树对应的二叉树的根作为兄弟结点连接起来;
3.同样遵循子树外部左排列、子树内部右排列的规则;
森林中有m个非终端结点,则其对应的二叉树中有m+1个右指针域为空的结点。右指针为空,即没有右孩子。因为每个非终端结点转换成二叉树后都对应(本身是,或者它的右孩子…是)一个无右孩子的结点,另外最后一棵树的根结点转换后也没有右孩子。
转换后得到的二叉树的根结点和其左子对对应森林中的第一棵树,右子树对应森林中的所有其它树。

二叉树转森林:
1.将根结点与其右子树连线断开,继续对新生的二叉树断开其根结点和其右子树的连接,得到多棵无右子树的二叉树。
2.把每个二叉树中的所有右支中的各结点依次断开连接并连接到支的父结点;最终得到多棵只根其结点多枝,其它结点都单枝的树。

树的遍历

树的先序遍历,与其对应的二叉树的先序遍历,结果相同。
树的中序遍历,与其对应的二叉树的中序遍历,结果相同。

树存储结构:孩子链表表示法、孩子兄弟链表表示法、双亲表示法。

按层遍历孩子兄弟链表结点,采用队列辅助,在访问某个结点后,立即把它的孩子和兄弟都加入队列。
1.根结点入队列
2.判断队列不为空时,出列一个元素,并访问这个元素的数据
3.将上一步访问的元素的孩子及其兄弟、兄弟的兄弟…,入队列。
4.循环步骤2、3。

哈夫曼(Huffman)树

树的应用之一是可以描述分类过程,按标准将数据划分为不同的种类。

判定树:描述分类过程的二叉树。分类问题中的因素有总数N,某个类别的属性有名称、条件、占比(权重)。二叉树中分叉结点表示判断条件,叶子结点表示值。判断树中的问题在于,同一个分类问题有不同的分类算法,会产生不同的判定树。它们从表面上看有纵深形状或水平形状,那么它们的总加权遍历查找的计算量也不同。则判定树中要研究的课题是要使平均比较次数计算量最小,使权重大的类别的比较次数尽量少。

哈夫曼算法和哈夫曼树,是从序列生成树的过程:
1.给定一组类别,{p1,p2,…,pk},其初始对应为单根树的森林{T1,T2…Tk}。
2.从森林中选两个根结点权(即占比)最小的树合并,它们分别为新树的左右子树,整齐起见可以按左小右大排列,新树的根结点权为左右子结点权之和。
3.直到森林中只剩一棵最小带权路径长度的二叉树,即哈夫曼树。
哈夫曼树也是满二叉树,其中共有2n0-1个结点,n0个叶结点是初始森林中的结点数。
WPL(Weight Path Length Of Node 带权路径长度)= 权与比较次数的乘积之和。

哈夫曼树的树形不一定唯一,但其WPL值最小且相等
哈夫曼字符编码不一定唯一,但总码长最短
哈夫曼树没有严格要求区别左右子树权重次序

哈夫曼编码:
在通信领域,希望字符在传输中总编码长度最短。
给出所有不同的字符,根据其出现次数比重构造哈夫曼树,然后将每个结点的左分支路径标记为0,右分支路径标记为1,每个叶结点都有一个从根结点开始的唯一的0、1序列,这个序列即是这个字符的编码,即哈夫曼编码。

发表评论