16.现有程序
void pr(){
scanf("%c",&ch) ;
if (ch!='#') pr();
printf("%c" ,ch) ;
}
写出输入为abc#时，调用pr函数的输出结果。
17.试编写如下定义的递归函数的递归算法:
g(m,n) = 0 当m=0,n>=0
g(m,n) = g(m-1,2n)+n 当m>0,n>=0
int G(int m, int n)
/* 如果 m<0 或 n<0 则返回 -1 */
{
if(m<0||n<0)
{
return -1;
}
if(m==0&&n>=0)
{
return 0;
}
return G(m-1,2*n)+n;
}
18.给出满足下列条件的所有二叉树。
- 先序序列与后序序列相同；
- 中序序列与后序序列相同；
- 先序序列与中序序列相同；
- 中序序列与层次序列相同；
先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根”，根据以上原则，解答如下：
1）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树。
2）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树。
（3）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树。
（4）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树
19.（1）n个结点的k叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的child域有多少个？
假设有m个叶子节点 那么空域就是k*m，和你的理解是一致的
非叶子节点就是 N-m个，因为是K叉树 ，那么(N-m) * k 就是除根节点外的所有节点，除了根节点以外有N-1个节点，所以 (N-m) *k = N-1
k*m = N*k-(N-1)
20.一颗完全二叉树共有520个结点,该完全二叉树共有多少个叶子节点·度为1的结点和度为2的结点
完全二叉树的n1（结点为1）的结点数要么为0要么为1。
并根据二叉树的性质：n0=n2+1
则总节点数250=n0+n1+n2=n0+n1+n0-1=2n0+n1=521
则说明n1=1,那么就可以解出n0=260,n2=259.
所以答案就是：n0=260,n1=1,n2=259.
20.已知完全二叉树的第七层有10个结点，则整个二叉树的结点数为多少个？
这一题问的不严谨，原题应该是问最多的结点数，所以下面就已最多结点数计算
由于完全二叉树的第七层上最多有2^6=64个结点，现在第七层上有10个叶子结点，说明该完全二叉树共有8层，所以整个二叉树的结点最多是(2^7-1)+(64-10)*2=127+108=235
21.在不同的线索化二叉树中,空余指针个数分别是多少?
按照某种遍历方式对二叉树进行遍历,可以把二叉树中所有结点排序为一个线性序列.在该序列中,除第一个结点外每个结点有且仅有一个直接前驱结点；除最后一个结点外每一个结点有且仅有一个直接后继结点.这些指向直接前驱结点和指向直接后续结点的指针被称为线索（Thread）,加了线索的二叉树称为线索二叉树.
按某种次序将二叉树线索化的实质是：按该次序遍历二叉树,在遍历过程中用线索取代空指针.
综上,第一个结点没有前驱,则其左指针为空,最后一个结点没有后继,则其右指针为空.
因此在不同的线索化二叉树中,空余指针个数应该是两个.
22.画出和下列已知序列对应的树T： 树的先根次序访问序列为GFKDAIEBCHJ; 树的后根次序访问序列为DIAEKFCJHBG。
树的先根序列为GFKDAIEBCHJ，后根序列为DIAEKFCJHBG，可以先转化成二叉树，再通过二叉树转换成树。注意二叉树的先根序列与等价树的先根序列相同，二叉树的中序序列对应着树的后根序列。
GFKDAIEBCHJ为所求二叉树的先序序列，DIAEKFCJHBG为二叉树的中序序列。通过观察先序序列，G为二叉树的根结点，再由中序序列，G的左子树序列为DIAEKFCJHB，右子为空。可以表示成如下形式：
G(DIAEKFCJHB，NULL)
对于子树先序序列为FKDAIEBCHJ，中序序列为DIAEKFCJHB，显然子树根为F。再由中序序列可以看到，F的左子树是DIAEK，右子树为CJHB。进一步表示成：
G(F(DIAEK,CJHB),NULL)
对于DIAEK（中序表示），先序为KDAIE，K为根，左子为DIAE，右子为空；对于CJHB，B为根，左子为CJH，右子为空。进一步表示成：
G(F(K(DIAE,NULL),B(CJH,NULL)),NULL)
G(F(K(D(NULL,IAE),NULL),B(C(NULL,JH),NULL)),NULL)
G(F(K(D(NULL,A(I,E)),NULL),B(C(NULL,H(J,NULL)),NULL)),NULL)
由此画出二叉树，进而画出树。
23.已知二叉树采用二叉链表方式存放，要求返回二叉树T的后序序列中的第一个结点的指针，是否可不用递归，且不用栈来完成请简述原因。
可以。
原因：后序遍历的顺序是“左子树―右子树―根结点”。因此，二叉树最左下的叶子结点是遍历的第一个结点。下面的语句段说明了这一过程(设P是二叉树根结点的指针)。
if (p! =NULL) {
while (p-＞ lchild! =NULL || p-＞ rchild! =NULL) {
while(p-＞ lchild! =NULL) p=p-＞ lchild;
if(p-＞ rchild! =NULL) p=p-＞ rchild;
}
}
return(p); //返回后序序列第一个结点的指针
24.已知一棵二叉树按顺序方式存储在数组A[1....N]中,设计算法求出下标分别为i和j的两个节点的最近的 公共祖先节点的值
#include "iostream.h"
const n = 10;
int findfather(int *a,int i,int j)
{
while(1)
{
if(i>j)
i=i/2;
else
j=j/2;
if(i == j)
return a[i-1];
}
}
void main()
{
int a[n]={1,2,3,4,5,6,7,8,9,10};
cout<<findfather(a,4,10);
}
25.假设二叉树采用二叉链表方式存储，root指向根结点，p所指结点和q所指结点为二叉树中的两个不同结点，且互不成为根到该结点的路径上的点，编程求解距离它们最近的共同祖先。
#include<bits/stdc .h>
using namespace std;
#define N 20
typedef struct Tree{
char data;
struct Tree *LeftChild;
struct Tree *RightChild;
}BiTNode , *BiTree;
BiTree Only(char *pre,char *in,int length){ //根据前序序列和中序序列唯一确定一个二叉树
BiTree root;
root=(BiTree)malloc(sizeof(BiTNode));
root->data=*pre;
int index;
if(length==0){ return 0;} //哇哦 这句话真是重中之重
for(index=0;index<length;index ){
if(root->data==in[index]){
break;
}
} //到了中序序列第几号元素:index==根节点==前序序列第一个元素
//递归 开始找根节点的左子树------的根节点
root->LeftChild=Only(pre 1,in,index);
//递归 开始找根节点的右子树-------的根节点
root->RightChild=Only(pre 1 index,in index 1,length-index-1);
return root;
}
bool Cover(BiTree root,char pt){
if(root==NULL) { return false;}
if(root->data==pt){
return true;
}else{
return Cover(root->LeftChild,pt)||Cover(root->RightChild,pt) ;
}
}
BiTree SearchCommen(BiTree node,char pt1, char pt2){
if(node==NULL){ return NULL;} //没有找到或者node压根就是个空的 返回null；
if(node->data==pt1||node->data==pt2){ return NULL;}//一个元素和根节点元素撞了，另一个是子元素，二者没有共同祖先
//两个元素都是正常的子节点的元素
//先在根节点的左子树里面找两个元素
bool t1=Cover(node->LeftChild,pt1);//leftchild pt1
bool t2=Cover(node->LeftChild,pt2);//leftchild pt2
if(t1!=t2) { return node;} //两个元素 一个在左边找到了 一个没找到 证明一左一右 所以祖先就是node
else{
//t1=t2 如果都等于true 就是两个元素都在左子树这边 所以往下循环就好
if(t1==true) { return SearchCommen(node->LeftChild,pt1,pt2);}
//t1=t2 如果都等于No 证明没有在左子树找到，那么就一定在右子树
if(t2==true) { return SearchCommen(node->RightChild,pt1,pt2);}
}
}
int main(){
BiTree pt;
/*假设二叉树采用二叉链表方式存储*/
char pre[N];
char in[N];
char *preo=pre;
char *ino=in;
char ch1,ch2;
int length;
cout<<"输入前序序列";
cin>>pre;
cout<<endl;
cout<<"输入中序序列";
cin>>in;
cout<<endl;
length=strlen(pre);
pt=Only(pre,in,length);
cin>>ch1>>ch2;
pt=SearchCommen(pt,ch1,ch2);
if(pt){ cout<<pt->data;}
else{ cout<<"NULL";}
}
26.已知二叉树按照顺序方式存储，编写算法，计算二叉树中非叶子结点的数目
int NoLeafCount(Node *T)/*求二叉树中非叶子结点的数目*/
{
if(!T)
return 0; /*空树没有叶子*/
else if(!T->lchild && !T->rchild)
return 0; /*叶子结点*/
else
return (1 + NoLeafCount(T->lchild) + NoLeafCount(T->rchild));/*当前结点+左子树的非叶子数+右子树的非叶子数*/
}
