数据结构有关树的知识总结（一）_对于一棵满二叉树,有a个节点和b个叶结点,高度为h

前段时间准备考研，对数据结构做了一个简略的知识点总结，知识针对考研所用到的数据结构，下面是树的章节由于篇幅太多，将有关树的知识点分开发表，对B树和B+树没有深入了解，所以就没有总结出来。

这篇文章就先写到线索二叉树吧。

【知识点】树

（一）树有关结点、度、高度的计算题

（二）二叉树的遍历

（三）线索二叉树

（四）哈夫曼树

（五） 堆排序

（六）最佳归并树、败者树

（七）折半查找

      （八）二叉排序树和平衡二叉树

二叉树性质：

高度为h≥0的二叉树至少有h+1个结点；

高度为h≥0的二叉树至多有2h+1-1个结点；

约定空二叉树的高度为-1；

含有n≥1个结点的二叉树的高度至多为n-1；

完全二叉树性质：n个结点的完全二叉树的结点按层序编号，则对任一结点i(1≤i≤n)：

如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2(向下取整)；

如果2i>n，则结点i无左孩子；如果2i≤n，则其左孩子是2i；

如果2i+1>n，则结点i无右孩子；如果2i+1≤n，则其右孩子是2i+1；

 

 

（一）树有关结点、度、高度的计算题

1. 一棵度为3的树，有2个3度结点，1个2度结点，2个1度结点，则叶子结点有  6  个；

解：设叶子节点数为:N0,度为1的结点数:N1,度为2的结点数:N2,度为3的结点数:N3;

总结点个数=N0+N1+N2+N3

总分支数=N1+2*N2+3*N3

总结点数-1=总分支数（因为除了根节点之外，每一个节点都有唯一一个只想该节点的分支）

 

1. 设树T的度为4，其中度为1、2、3、4的节点个数分别为4、2、1、1，则书中的叶子结点数为 8 个。

解：(总结点数-1)n0+n1+n2+n3+n4-1=n1+2*n2+3*n3+4*n4(总分支数)->n0=n2+2*n3+3*n4+1=2+2*1+3*1+1=8

 

1. （2017算法计算13）二叉树度为0的结点数为M个，度为2的结点数为N2个，证明N2=M-1

证明：总结点数=M+N1+N2(叶子节点+度为1的结点(N1)+度为2的结点)

 总分支数=N1+2*N2

 总分支数=总结点数-1（因为除了根结点，每一个结点都有唯一只想该结点的分支）

 M+N1+N2-1=N1+2N——>M-1=N

 

1. 按照二叉树的定义，有3个节点的二叉树有 5 种。(2016简答)

公式：即计算Catalan数，给定n个结点能构成h(n)=C(2n,n)/(n+1)种形态。（其中C（2n,n）是指以2n为底）。n=3,h(n)=C(6,2)/(3+1)=[（6*5*4）/（3*2*1）]/4=5

 

1. 一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数为 11 个。（M-1=N）

 

1. 有10个叶结点的二叉树中有 9 个度为2的结点。（M-1=N：10-1=N（2度结点但数））

 

1. 一棵完全二叉树上有1001个结点，其叶结点的个数有 501 个。

解：此题分两种情况：

（1）有单分支结点，分支总数=n1+2*n2，分支总数=结点总数-1=1000=n1+2*n2,因为是完全二叉树，故如果有单分支结点，也只能有一个，所以就有：1+2*n2=1000,解得n2非整数，所以没有单分支结点。

（2）无单分支结点，分支总数=2*2n=1001(总结点数)-1=1000，解得n2=500,叶子节点数=2度结点数+1=501

 

1. 一棵高度为4的完全二叉树至少有 8 个节点。

解：高度为n的树最多有2ⁿ -1个节点，完全二叉树高度为4，则前三层是满二叉树，2³-1个结点。则该完全二叉树至少有（2³-1）+1个结点。

 

1. 一棵高度为h的完全二叉树至少有 2^(h-1) 个结点。2^(h-1)-1]+1

 

10、一棵高度为5的完全二叉树最多有 31 个结点。（2的5次幂-1=31）。

 

11、假设高度为h的二叉树上只有0度和2度结点，此类二叉树的结点至少为 2h-1 个。

解答：如下图，除了第一层只有一个根节点，其余h-1层都有两个节点，则这样的二叉树最少有2(h-1)+1=2h-1个

12、在一棵三叉树中，3度的结点个数为2，2度的结点个数为1，1度的结点个数为2，则0度的结点个数为 8 。（n0+n1+n2+n3-1=n1+2*n2+3*n3-->n0=8）

 

13、哈夫曼二叉树中只有度为0和度为2的结点，有n个叶子结点的哈夫曼树的节点总数为 2n-1个。（叶子结点数=n2+1=n,n2=n-1,节点总数=n0+n2=n+n-1=2n-1）

 

14、一棵具有1025个结点的二叉树高度h的范围是 11~1025

解：当一棵二叉树每层只有一个结点时，高度最高为1025，而当这颗二叉树为完全二叉树时最矮，

h=㏒(1025+1）=11 （而且是向上取整）2的10次方是1024。

 

1. 对一棵满二叉树，共有n个结点和m个叶子结点，高度为h，则他们之间的关系是 m=2^(h-1),n=2^h-1 。

 

1. 已知一棵完全二叉树的第七层共有10个叶结点，则该二叉树结点最多为 235 个，最少为 73个。

解：

①最多的情况：第七层已满，树共有八层

第七层的结点个数为：2^（7-1）=64个结点，

10个叶结点在第八层上：64-10=54（第七层不是叶结点的节点个数），

第八层的节点个数为：54*2=108个，

前七层的节点总数为：2^7-1=127，

则整棵二叉树的结点为：128+108=235个（前七层的结点总数+第八层的结点数）。

②最少的情况：树共有七层，六层已满

前六层的结点总数：2^6-1=63个

第七层叶结点总数：10个

总数：63+10=73个

（二）二叉树的遍历

1、中缀表达式转化为后缀表达式

如一个表达式:(a-(b+c))*(d/e)

                                  

     二叉树表达式                                                     分成了两个部分

则后序遍历得：abe+-de/*

 

1. 二叉树遍历重要技巧(2014)

前序遍历：A,B,C,D,E,F,G,H 中序遍历：C,B,E,D,F,A,H,G 后序遍历：C,E,F,D,B,H,G,A

三种遍历方法对相应上图中p经过每个节点的不同次数时对其进行输出的结果，如上图p沿着路线依次经过3号的结点次序就是后序遍历后的节点序列。

注：①已知前序遍历序列+中序遍历序列，可以确定一棵树，先由前序遍历找到根节点，再由中序确定左右子树。

②已知中序遍历序列+后序遍历序列，可以确定一棵树，先由后序遍历确定根节点，再由中序确定左右子树。

③已知前序遍历+后序遍历，不可以确定一棵树，都只能先确定根，但左右子树可以有两种表示方式。

1. 树的遍历

·先序遍历：

·中序遍历

·后序遍历

·层次遍历

    层次遍历需要建立一个循环队列，先将二叉树的头节点入队，然后出队，访问该节点，如果队列不空，则循环访问其左右子树，如果有左子树，则将左子树根节点入队，如果有右子树，将右子树根节点入队，然后出队。

（三）线索二叉树

线索二叉树的结构：

1. 若ltag=0，表示lchild为指针，指向结点的左孩子（有左子树），若ltag=1,表示该节点无左孩子，此时lchild为线索，指向结点的前驱结点。
2. 若rtag=0，表示rchlid为指针，指向结点的右孩子（有右孩子），若rtag=1,表示该节点无右孩子，此时rchlid为线索，指向结点的后继结点。

 

1、后继线索二叉树中寻找结点node的前驱和后继。

前驱：根据后序的特点，查找前驱是一个自顶向下的过程，即当右子树标记为0时，说明   node有右子树，此时node的前驱就是右儿子，否则就是它的左孩子。

prior(node,x){

    if(node != null){

        if(!node->rthread)//有右子树，则node的前驱时右子树

            *x = node->right;

        else

        *x = node->left;//没有右子树，则node的前驱时左子树

    }

}

后继：查找后继是一个自底向上的过程，与查找前驱不同的是，访问到node结点时，后继    还没办法访问，所以将查找node的后继*x的问题转换为查找*x的前驱的问题，即从    根节点开始，不断查找x的前驱，直到x的前驱为node时，x则为node的后继了。

next(bt,node,x){

    *x=bt;

    if(bt != 0 && node != null){

        if(node->rthread)//node没有右子树，则node->right指向的是node的后继

            *x = node->right;//此时x可以直接等于node的后继

        else{

            do{

                t=*x;

                prior(t,x);//不断找x的前驱

           }while(*x != node)//直到x的前驱是node，此时x就是弄得的后继

        *x = t;

          }

    }

}