1.假设二叉树采用二叉链表存储结构，设计一个算法，计算一棵给定二叉树的所有结点数。
1
2
3
4
5
6
7
8
9
10
11
| int n=0;
void count(BTNode *p)
{
if(p!=NULL)
{
++n;
count(p->lChild);
count(p->rChild);
}
}
|
2.假设二叉树采用二叉链表存储形式，设计一个算法，计算一棵给定二叉树的所有叶子结点数。
1
2
3
4
5
6
7
8
9
10
11
12
| int n=0;
void count(BTNode *p)
{
if(p!=NULL)
{
if(p->lChild&&p->rChild==NULL)
++n;
count(p->lChild);
count(p->rChild);
}
}
|
3.假设二叉树采用二叉链表存储结构，设计一个算法，利用结点的右孩子指针rchild将一棵二叉树的叶子结点按照从左往右的顺序串成一个单链表（在题目中定义两个指针，head与tail，其中head指向第一个叶子结点，head初值为null,tail指向最后一个叶子结点）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| void link(BTNode *p,BTNode *&head,BTNode *&tail)
{
if(p!=NULL)
{
if(p->rchild==NULL&&p->lChild==NULL)
if(head==NULL)
{
head=p;
tail=p;
}
else
{
tail->rchild=p;
tail=p;
}
link(p->lchild,head,tail);
link(p->rchild,head,tail);
}
}
|
4.在二叉树的二叉链表存储结构中，增加一个指向双亲结点的parent指针，设计一个算法，给这个指针赋值，并输出所有结点到根结点的路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| typedef struct BTNode //修改数据结构
{
char data;
struct BTNode *parent;
struct BTNode *lchild;
struct BTNode *rchild;
}BTNode;
void triBtree(BTNode *p,BTNode *q)
{
if(p!=NULL)
{
p->parent=q;
q=p;
triBtree(p->lchild,q);
triBtree(p->rchild,q);
}
}
void printPath(BTNode *p)
{
while(p!=NULL)
{
cout<<p->data<<" "<<endl;
p=p->parent;
}
}
void allPath(BTNode *p)
{
if(p!=NULL)
{
printPath(p);
allPath(p->lchild);
allPath(p->rchild);
}
}
|
5.假设满二叉树b的先序遍历序列已经存放在于数组中（在解题过程中，此数组名称可以自己定义，长度为n），设计一个算法将其转化为后序遍历序列。
1
2
3
4
5
6
7
8
9
10
| void change(char pre[],int L1,int R1,char post[],int L2,int R2)
{
if(L1<=R1)
{
post[R2]=pre[L1];
change(pre,L1+1,(L1+1+R1)/2,post,L2,(L2+R2-1)/2);
change(pre,(L1+1+R1)/2+1,R1,post,(L2+R2-1)/2+1,R2-1);
}
}
|
7.假设二叉树采用二叉链表存储结构存储，设计一个算法，求二叉树b中值为x的结点的层号。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int L=1;
void leno(BTNode *p,char x)
{
if(p!=NULL)
{
if(p->data==x)
{
cout<<L<<endl;
}
++L;
leno(p->lchild,x);
leno(p->rchild,x);
--L;
}
}
|
这里用到了一个我们发现遍历序列时候的共性：在遍历结点的时候，总是由指针p从一层往下面一层去走，一直走到最底层，(++L)然后由下层往上层走（–L）,而且，第一次遇见一个结点，是往下走，此时是先序遍历，（第二次遇见也是往下走），第三次遇见是往上走，是后序遍历，所以，我们在第10行加入++L,在递归处理左右子树后，在第14行加入--L（这里说的比较个人化。。不好理解）
8.二叉树的双序遍历是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。
1
2
3
4
5
6
7
8
9
10
| void Double_order(BTNode *t)
{
if(t!=NULL)
{
Visit(t);
Double_order(t->lchild);
Visit(t);
Double_order(t->rchild);
}
}
|
9.设中序线索二叉树的类型为TBTNode*InThree;
设计算法，在一棵中序线索二叉树中寻找结点t的子树上中序下的最后一个结点。
设计算法，在一棵中序线索二叉树中寻找结点t的中序下的前驱。
设计算法，在一棵中序线索二叉树中寻找结点t的前序下的后继。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
| TBTNode* inLast(TBTNode *t)
{
TBTNode *p=t;
while(p&&!p->rtag)
p=p->rchild;
return p;
}
TBTNode inPrior(TBTNode *t)
{
TBTNode *p=p->lchild;
if(p&&!t->ltag)
p=inLast(p);
return p;
}
TBTNode * treNext(TBTNode *t)
{
TBTNode *p;
if(!t->ltag)
p=t->lchild;
else if(!t->rtag)
p=t->rchild;
else
{
p=t;
while(p&&p->rtag)
p=p->rchild;
if(p)
p=p->rchild;
}
}
|
10.假设二叉树采用二叉链存储结构，设计一个算法，输出根结点到每个结点的路径。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int i ;
int top=0;
char pathstack[maxsize];
void allPath(BTNode *p)
{
if(p!=NULL)
{
pathstack[top]=p->data;
++top;
if(p->lchild=NULL&&p->rchild=NULL)
{
for(i=0;i<top;++i)
cout<<pathstack[i];
}
allPath(p->lchild);
allPath(p->rchild);
--top;
}
}
|