第七章 树和二叉树
一、基本知识点
(1)树的递归特点和树的相关术语。
(2)树的性质、树的遍历和树的存储结构。
(3)二叉树与树/森林之间的转换方法。
(4)二叉树的递归特点、二叉树的性质和二叉树的两种存储结构。
(5)完全二叉树和满二叉树的特点。
(6)二叉树的先序、中序和后序遍历递归和非递归算法设计。
(7)二叉树的层次遍历算法设计。
(8)二叉树遍历算法的应用。
(9)二叉树的构造过程。
(10)线索二叉树的特点构造和遍历过程。
(11)哈夫曼树的特点哈夫曼树的构造过程和哈夫曼编码的生成。
(12)灵活地运用二叉树这种数据结构解决些综 合应用问题。
二、要点归纳、基本实现
(1)树用来表示具有层次结构的数据。
(2)在一棵树中根结点没有前驱结点，其余每个结点都有唯一的前驱结点。
(3)度为m的树至少有一个结点的度为m，且没有度大于m的结点。例如，度为3的树至少有4个结点。
(4)含有n个结点的m次树，n=n0+n1+… +nm.，所有结点度之和=n1+2n2 +…+mnm。
(5)对于含有n个结点的树(或者二叉树)，无论度为多少，其分支数或所有结点度之和均为n-1。
(6)对于高度为h的m次树，当为满m次树时结点个数最多。
(7)树的遍历运算主要有先根遍历、后根遍历和层次遍历3种。
(8)树的存储结构主要有双亲存储结构、孩子链存储结构和孩子兄弟链存储结构。
(9)二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称为根结点的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。
(10)二叉树和树都属于树形结构，但二叉树并不是特殊的树。
(11)度为2的树和二叉树是不同的。
(12)二叉树中所有结点的度均小于或等于2。结点个数=n0+n1 +n2，所有结点度之和=n-1=n1+2n2，所以n0=n2 +1.
(13)在二叉树中，根结点的层次(或深度)为1，一个结点的层次是其双亲结点的层次加1。
(14)在二叉树中，二叉树的高度h等于从根结点到叶子结点的最长路径上的结点个数。
(15)满二叉树中所有分支结点的度皆为2，即n1=0，且所有叶子结点在同一层上。
(16)若满二叉树的结点数为n，其树形是唯一确定的，高度h= log2(n+1)。
(17)完全二叉树中除最后一层以外，其余层都是满的，并且最后一层的右边缺少连续若干个结点。
(18) 完全二叉树中单分支结点个数n1只能为1或0。
(19)对于结点个数为n的完全二叉树，其树形是唯一确定的。也就是说，可以由n计算出n0、n1、n2和高度h，h=「log2(n+1)](向上取整)。
(20)二叉树的存储结构主要有顺序存储结构和二叉链存储结构两种。
(21)在含有n个结点的二叉链中，通过根结点指针来唯一标识该二叉链，其中空指针域个数为n+1。
(22)二叉树的遍历方式主要有先序遍历、中序遍历后序遍历和层次遍历。
(23)在二叉树的先序遍历、中序遍历和后序遍历中，所有左于树均在右子树之前遍历，这3种遍历算法可以采用递归实现，也可以栈转换为非递归算法。
(24)在非递归后序遍历中，当出栈并访向一个结点时，栈中恰好包含它的所有祖先。
(25)在设计二叉树的递归算法时，通常以整棵二叉树的求解为“大问题”，而左、右子树的求解为“小问题”。假设左、右子树可以求解，推导出“大问题”的求解关系，从而得到到递归体，再根据递推方向考虑一个特殊情况(如空树或只有一个结点的二叉树)给出递归出口，得到递归模型，在此基础上写出递归算法。
(26)假设二叉树中的结点值均不相同，由先序序列和中序序列可以唯一确定一棵二叉树。
(27)假设二叉树中的结点值均不相同，由后序序列和中序序列可以唯一确定一棵二叉树。
(28)假设二叉树中的结点值均不相同，由层次遍历序列和中序序列可以唯一确定一棵二叉树。
(29)在将一棵非空树转换成二叉树时，树的根结点变为二叉树的根结点。树的每个结点的最左孩子(长子)变为二叉树的左孩子，其他孩子变成该孩子的右下结点。
(30)在将一个森林转换成二叉树时，整个森林转换成一棵二叉树。第1棵树的根结点变为二叉树的根结点，第1棵树的其他结点变为二叉树根结点左子树中的结点，森林的其他树中结点变为二叉树根结点的右子树中的结点。
(31)线索二叉树是由二叉链存储结构变化而来的，将原来的空链域改为某种遍历次序下该结点的前驱结点和后继结点的指针。
(32)中序线索二叉树可以采用不需要栈的非递归算法来实现中序遍历，对应的空间复杂度为0(1)。
(33)中序线索二又树仅仅有利于中序遍历，并不能提高先序遍历和后序遍历的效率。
(34)哈夫曼树是带权路径长度最小的二叉树。
(35)哈夫曼树中权值较小的叶子结点一般离根结点较远。
(36)天曼树中的单分支结点个数为0，在含有m个叶子结点的哈夫曼树中，其结点总数为2m-1。
(37)在组字符的哈夫曼编码中，任何字符的编码不可能是另一个字符编码的前缀。
二叉树的基本运算
#include <iostream>
using namespace std;
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data; //数据元素
struct node *lchild; //指向左孩子节点
struct node *rchild; //指向右孩子节点
} BTNode;
void CreateBTree(BTNode*& b, char* str) //创建二叉树
{
BTNode* St[MaxSize], * p = NULL;
b = NULL;
int j = 0, k = 0, top = -1; //k等于1：这个节点作为左孩子，等于2时作为右孩子
char ch = str[j];
while (ch != '\0')
{
switch (ch)
{
case'(':top++; St[top] = p; k = 1; break; //处理左子树
case')':top--; break; //子树处理完了
case',':k = 2; break; //处理右子树
default:
p = (BTNode*)malloc(sizeof(BTNode));
p->data = ch;
p->lchild = p->rchild = NULL;
if (b == NULL) //如果是第一个，那么视为根结点
{
b = p;
}
else //已经有根结点了
{
switch (k)
{
case 1:St[top]->lchild = p; break;
case 2:St[top]->rchild = p; break;
default:
break;
}
}
break;
}
j++;
ch = str[j]; //遍历下一个字符
}
}
void DestroyBTree(BTNode *&b)
{ if (b!=NULL)
{ DestroyBTree(b->lchild);
DestroyBTree(b->rchild);
free(b);
}
}
BTNode *FindNode(BTNode *b,ElemType x)
{
BTNode *p;
if (b==NULL)
return NULL;
else if (b->data==x)
return b;
else
{
p=FindNode(b->lchild,x);
if (p!=NULL)
return p;
else
return FindNode(b->rchild,x);
}
}
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
int BTHeight(BTNode *b)
{
int lchildh,rchildh;
if (b==NULL) return(0); //空树的高度为0
else
{
lchildh=BTHeight(b->lchild); //求左子树的高度为lchildh
rchildh=BTHeight(b->rchild); //求右子树的高度为rchildh
return (lchildh>rchildh)? (lchildh+1):(rchildh+1);
}
}
void DispBTree(BTNode* b) //输出二叉树
{
if (b != NULL)
{
cout << b->data; //根结点直接输出，后续递归输出分支结点
if (b->lchild != NULL || b->rchild != NULL)
{
cout << " ( ";
DispBTree(b->lchild); //递归处理左子树
if (b->rchild != NULL)
{
cout << ",";
}
DispBTree(b->rchild); //递归处理右子树
cout << " ) ";
}
}
}
二叉树的三种遍历（包括递归非递归）
void PreOrder(BTNode* b) //先序遍历递归
{
if (b!=NULL)
{
cout << b->data << " "; //打印输出根结点的值
PreOrder(b->lchild); //递归访问左子树
PreOrder(b->rchild); //递归访问右子树
}
}
void PreOrder1(BTNode* b) //先序遍历非递归
{
BTNode* St[MaxSize], * p;
int top = -1;
if (b!=NULL)
{
top++;
St[top] = b; //根结点进栈
while (top>-1) //栈不为空则循环遍历
{
p = St[top]; //退栈并打印当前结点的值
top--;
cout << p->data << " ";
//此处由于栈是先进后出表，应先让右孩子进栈
if (p->rchild!=NULL) //如果有右孩子则进栈
{
top++;
St[top] = p->rchild;
}
if (p->lchild != NULL) //若有左孩子，进栈
{
top++;
St[top] = p->lchild;
}
}
cout << endl;
}
}
void InOrder(BTNode* b) //中序遍历递归
{
if (b != NULL)
{
InOrder(b->lchild); //递归访问左子树
cout << b->data << " "; //打印输出根结点的值
InOrder(b->rchild); //递归访问右子树
}
}
void InOrder1(BTNode* b) //中序遍历非递归
{
BTNode* St[MaxSize], * p;
int top = -1;
if (b != NULL)
{
p = b;
while (top>-1||p!=NULL)
{
while (p != NULL) //扫描结点p的所有左下结点并进栈
{
top++;
St[top] = p;
p = p->lchild;
}
if (top>-1)
{
p = St[top]; //出栈结点p并打印输出
top--;
cout << p->data << " ";
p = p->rchild;
}
}
cout << endl;
}
}
void PostOrder(BTNode* b) //后序遍历递归
{
if (b != NULL)
{
PostOrder(b->lchild); //递归访问左子树
PostOrder(b->rchild); //递归访问右子树
cout << b->data << " "; //打印输出根结点的值
}
}
void PostOrder1(BTNode* b) //后序遍历非递归
{
BTNode* St[MaxSize], * p;
int top = -1;
bool flag;
if (b!=NULL)
{
do
{
while (b != NULL) //b的所有左下结点并进栈
{
top++;
St[top] = b;
b = b->lchild;
}
p = NULL; //p指向当前结点的前一个已经访问的结点
flag = true; //正在处理栈顶结点
while (top!=-1 && flag)
{
b = St[top]; //取出栈顶元素
if (b->rchild==p)
{
cout << b->data << " "; //输出结点b
top--;
p = b; //p指向被访问的结点
}
else
{
b = b->rchild; //b指向右子树
flag = false;
}
}
} while (top!=-1);
cout << endl;
}
}
中序线索化二叉树
线索二叉树的遍历: 中序线索化上述二叉树并找出根结点的前驱和后继。
Thread.h
#pragma once
#include<iostream>
using namespace std;
const int MaxSize = 100;
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node* lchild;
struct node* rchild;
int ltag, rtag;
}TBTNode;
void CreateTBTree(TBTNode*& b, char* str); //建立含空线索域的二叉链b
void DispTBTree(TBTNode* b); //输出
void Thread(TBTNode*& p); //中序线索化二叉树，被调用CreateThread函数调用
TBTNode* CreateThread(TBTNode* b); //建立中序线索化二叉树
void PreNode(TBTNode* T); //查找结点T的前驱结点
void NextNode(TBTNode* T); //查找结点T的后继结点
Thread.cpp
#include"Thread.h"
void CreateTBTree(TBTNode*& b, char* str) //建立含空线索域的二叉链b
{
TBTNode* St[MaxSize], * p=NULL; //创建数组St 和 p结点
int top = -1; //初始下标为-1
int k, j = 0; //k=1表示处理左子树，k=2表示处理右子树
char ch = str[j]; //ch获取一个字符
b = NULL;
while (ch!='\0') //只要字符数组不为空，循环遍历
{
switch (ch)
{
case '(': top++; St[top] = p; k = 1; break; //准备处理左子树，并将该节点的双亲进栈
case ')': top--; break;
case ',': k = 2; break; //准备处理右子树
default:
//初始化p结点
p = (TBTNode*)malloc(sizeof(TBTNode));
p->data = ch;
p->lchild = p->rchild = NULL;
if (b==NULL) //如果是根节点，直接赋值，因为不可能遇到前面的case
{
b = p;
}
else //根据k的值来建立左右子树
{
switch (k)
{
case 1: St[top]->lchild = p; break;
case 2: St[top]->rchild = p; break;
default:
break;
}
}
break;
}
j++;
ch = str[j]; //更新下一字符
}
}
void DispTBTree(TBTNode* b) //输出，递归实现
{
if (b!=NULL)
{
cout << b->data ;
if (b->lchild!=NULL || b->rchild!=NULL)
{
cout << "(";
DispTBTree(b->lchild);
if (b->rchild!=NULL)
{
cout << " , ";
}
DispTBTree(b->rchild);
cout << ")";
}
}
}
TBTNode* pre = new TBTNode; //指向中序遍历的前一个结点
void Thread(TBTNode*& p) //中序线索化二叉树，被调用CreateThread函数调用
{
if (p!=NULL)
{
Thread(p->lchild);
if (p->lchild == NULL)
{
p->lchild = pre;
p->ltag = 1;
}
else { p->ltag = 0; }
if (pre->rchild == NULL)
{
pre->rchild = p;
pre->rtag = 1;
}
else { pre->rtag = 0; }
pre = p;
Thread(p->rchild);
}
}
TBTNode* CreateThread(TBTNode* b) //建立中序线索化二叉树
{
TBTNode* root;
root = (TBTNode*)malloc(sizeof(TBTNode));
root->ltag = 0; //值为1表示线索，指向前驱，为0时指向左孩子
root->rtag = 1; //值为1表示线索，指向后继，为0时指向右孩子
root->rchild = b;
if (b==NULL) //如果b为空，将其lchild指向自身
{
root->lchild = root;
}
else
{
root->lchild = b;
pre = root;
Thread(b);
pre->rchild = root;
pre->rtag = 1;
root->rchild = pre; //将root的rchild指针域指向最后一个结点
}
return root;
}
void PreNode(TBTNode * T)
{
TBTNode* p = T;
if (T->ltag == 1) //如果是线索，直接输出
{
cout << "根节点的前驱为：" << T->lchild->data << endl;
}
else
{
while (p->rchild != T)
{
while (p->ltag == 0)
{
p = p->lchild;
}
while (p->rtag == 1)
{
p = p->rchild;
}
p = p->rchild;
}
cout << "根节点的前驱为：" << p->data << endl;
}
}
void NextNode(TBTNode* T)
{
TBTNode* p = T;
if (T->rtag == 1) //如果是线索，直接输出
{
cout << "根节点的后继为：" << T->rchild->data << endl;
}
else
{
while (p->lchild != T)
{
while (p->rtag == 0)
{
p = p->rchild;
}
while (p->ltag == 1)
{
p = p->lchild;
}
p = p->lchild;
}
cout << "根节点的后继为：" << p->data << endl;
}
}
Thread_main.cpp
#include"Thread.h"
int main()
{
TBTNode* b;
char s[] = "A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))";
CreateTBTree(b, s);
cout << "创建二叉树：\n";
DispTBTree(b);
TBTNode* root=CreateThread(b);
cout << endl;
PreNode(root->lchild);
NextNode(root->lchild);
}
哈夫曼树的应用
#include <stdio.h>
#include <string.h>
#define N 50 //叶子结点数
#define M 2*N-1 //树中结点总数
typedef struct
{
char data[5]; //结点值
double weight; //权重
int parent; //双亲结点
int lchild; //左孩子结点
int rchild; //右孩子结点
} HTNode;
typedef struct
{
char cd[N]; //存放哈夫曼码
int start;
} HCode;
void CreateHT(HTNode ht[],int n0) //构造哈夫曼树
{ int i,k,lnode,rnode;
double min1,min2;
for (i=0;i<2*n0-1;i++) //所有节点的相关域置初值-1
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n0;i<=2*n0-2;i++) //构造哈夫曼树的n0-1个节点
{ min1=min2=32767; //lnode和rnode为最小权重的两个节点位置
lnode=rnode=-1;
for (k=0;k<=i-1;k++) //在ht[0..i-1]中找权值最小的两个节点
if (ht[k].parent==-1) //只在尚未构造二叉树的节点中查找
{ if (ht[k].weight<min1)
{ min2=min1;rnode=lnode;
min1=ht[k].weight;lnode=k;
}
else if (ht[k].weight<min2)
{ min2=ht[k].weight;rnode=k; }
}
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;ht[i].rchild=rnode; //ht[i]作为双亲节点
ht[lnode].parent=i;ht[rnode].parent=i;
}
}
void CreateHCode(HTNode ht[],HCode hcd[],int n0) //构造哈夫曼树编码
{ int i,f,c;
HCode hc;
for (i=0;i<n0;i++) //根据哈夫曼树求哈夫曼编码
{ hc.start=n0;c=i;
f=ht[i].parent;
while (f!=-1) //循环直到无双亲节点即到达树根节点
{ if (ht[f].lchild==c) //当前节点是双亲节点的左孩子
hc.cd[hc.start--]='0';
else //当前节点是双亲节点的右孩子
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent; //再对双亲节点进行同样的操作
}
hc.start++; //start指向哈夫曼编码最开始字符
hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n0) //输出哈夫曼树编码
{
int i,k;
double sum=0,m=0;
int j;
printf(" 输出哈夫曼编码:\n"); //输出哈夫曼编码
for (i=0;i<n0;i++)
{
j=0;
printf(" %s:\t",ht[i].data);
for (k=hcd[i].start;k<=n0;k++)
{
printf("%c",hcd[i].cd[k]);
j++;
}
m+=ht[i].weight;
sum+=ht[i].weight*j;
printf("\n");
}
printf("\n 平均长度=%g\n",1.0*sum/m);
}
int main()
{
int n=8,i; //n表示初始字符串的个数
char *str[]={"a","b","c","d","e","f","g","h"};
double fnum[]={0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.1};
HTNode ht[M];
HCode hcd[N];
for (i=0;i<n;i++)
{
strcpy(ht[i].data,str[i]);
ht[i].weight=fnum[i];
}
printf("\n");
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
printf("\n");
return 1;
}
运行结果：
三、练习题
1、选择题
（1）把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。
A．唯一的
Ｂ．有多种
C．有多种，但根结点都没有左孩子
Ｄ．有多种，但根结点都没有右孩子
答案：A
解释：因为二叉树有左孩子、右孩子之分，故一棵树转换为二叉树后， 这棵二叉树的形态是唯一的。
（2）由 3 个结点可以构造出多少种不同的二叉树？（ ）
A．2
B．3
C．4
D．5
答案：D
（3）一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（ ）。
A．250
B． 500
C．254
D．501
答案：D
解释：设度为 0 结点（叶子结点）个数为 A，度为 1 的结点个数为 B，度为 2 的结点个数为 C，有 A=C+1，A+B+C=1001，可得 2C+B=1000，由完全二叉树的性质可得 B=0 或 1，又因为 C 为整数，所以 B=0，C=500，A=501，即有501 个叶子结点。
（4）一个具有 1025 个结点的二叉树的高 h 为（ ）。
A．11
B．10
C．11 至 1025 之间
D．10 至 1024 之间
答案：C
解 释 ： 若 每 层 仅 有 一 个 结 点 ， 则 树 高 h 为 1025 ； 且 其 最 小 树 高为 [log21025]_(此处下取) + 1=11，即 h 在 11 至 1025之间。
（5）深度为 h 的满 m 叉树的第 k 层有（ ）个结点。(1=<k=<h)
A．mk-1
B．mk-1
C．mh-1
D．mh-1
答案：A
（6）利用二叉链表存储树，则根结点的右指针是（ ）。
A ． 指 向 最 左 孩 子
B ． 指 向 最 右 孩 子
C ． 空
D．非空
答案：C
解释：利用二叉链表存储树时，右指针指向兄弟结点，因为根节点没有兄弟结点，故根节点的右指针指向空。
（7）对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（ ）遍历实现编号。
A．先序
B. 中序
C. 后序
D. 从根开始按层次遍历
答案：C
解释：根据题意可知按照先左孩子、再右孩子、最后双亲结点的顺序遍历二叉树，即后序遍历二叉树。
（8）若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。
A．前序
B．中序
C．后序
D．按层次
答案：C
解释：后序遍历和层次遍历均可实现左右子树的交换，不过层次遍历的实现消耗比后序大，后序遍历方法最合适。
（9）在下列存储形式中，（ ）不是树的存储形式.
A．双亲表示法
B．孩子链表表示法
C．孩子兄弟表示法
D．顺序存储表示法
答案：D
解释：树的存储结构有三种：双亲表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。
（10）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。
A．所有的结点均无左孩子
B．所有的结点均无右孩子43
C．只有一个叶子结点
D．是任意一棵二叉树
答案：C
解释：因为先序遍历结果是“中左右”，后序遍历结果是“左右中”， 当没有左子树时，就是“中右”和“右中”；当没有右子树时，就是“中左” 和“左中”。则所有的结点均无左孩子或所有的结点均无右孩子均可，所以 A、 B 不能选，又所有的结点均无左孩子与所有的结点均无右孩子时，均只有一个叶子结点，故选 C。
（11）设哈夫曼树中有 199 个结点，则该哈夫曼树中有（ ）个叶子结点。
A．99
B．100
C．101
D．102
答案：B
解释：在哈夫曼树中没有度为 1 的结点，只有度为 0（叶子结点）和度为 2 的结点。设叶子结点的个数为 n0，度为 2 的结点的个数为 n2，由二叉树的性质 n0=n2+1，则总结点数 n= n0+n2=2*n0-1，得到 n0=100。
（12）若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，则X 的前驱为（）。
A．X 的双亲
B．X 的右子树中最左的结点
C．X 的左子树中最右结点
D．X 的左子树中最右叶结点
答案：C
（13）引入二叉线索树的目的是（ ）。
A．加快查找结点的前驱或后继的速度
B．为了能在二叉树中方便的进行插入与删除
C．为了能方便的找到双亲
D．使二叉树的遍历结果唯一
答案：A
（14）设 F 是一个森林，B 是由 F 变换得的二叉树。若 F 中有 n 个非终端结点，则 B 中右指针域为空的结点有（）个。
A．n−1
B．n
C．n + 1
D．n + 2
答案：C
（15）n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（ ）。
A．该树一定是一棵完全二叉树
B．树中一定没有度为 1 的结点44
C．树中两个权值最小的结点一定是兄弟结点
D．树中任一非叶结点的权值一定不小于下一层任一结点的权值
答案：A
解释：哈夫曼树的构造过程是每次都选取权值最小的树作为左右子树构造一棵新的二叉树，所以树中一定没有度为 1 的结点、两个权值最小的结点一定是兄弟结点、任一非叶结点的权值一定不小于下一层任一结点的权值。
2、填空题
1.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。下面函数的功能是返回二叉树BT中值为x的结点所在的层号，请在划有横线的地方填写合适的内容。
int NodeLevel ( BinTreeNode * BT, ElemType& x ) {
if ( BT == NULL ) return –1; //空树的层号为-1
else if ( BT->data == x ) return 0; //根结点的层号为0
else {
int c1 = NodeLevel ( BT->leftChild, x ); //向子树中查找x结点
if ( c1 >= 0 ) _________(1)_________;
int c2 =_________(2)__________;
___________(3)____________;
else return -1; //在树中不存在x结点返回-1
}
}
2.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为x的结点，返回指向其父结点的指针。若该结点不存在或为树根结点则返回空。算法中参数PT的初值为NULL。请在划有横线的地方填写合适的内容。
BinTreeNode* ParentPtr ( BinTreeNode* BT, BinTreeNode* PT, ElemType& x ) {
if ( BT == NULL ) return NULL;
else if ( BT->data == x ) return PT;
else {
if ( PT = ParentPtr ( BT->leftChild, BT, x ) ) _______(1)________;
______________(2)_______________;
else _______(3)________;
}
}
3.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的树根结点。
BinTreeNode* BinTreeSwopX ( BinTreeNode * BT ) {
if ( BT == NULL ) return NULL;
else {
BinTreeNode* pt = new BinTreeNode;
pt->data = BT->data;
pt->rightChild = BinTreeSwopX ( BT->leftChild );
pt->lefthild = BinTreeSwopX ( BT->rightChild );
return pt;
}
}
算法功能：__________________________________________________
4.已知二叉树中的结点类型用ThreeTreeNode表示，被定义为:
struct ThreeTreeNode { datatype data; ThreeTreeNode *leftChild, *rightChild, *parent; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，parent为指向父结点的指针域。根据下面函数的定义指出函数的功能。算法中参数T指向一棵二叉树的树根结点，x保存一个结点的值。
ThreeTreeNode* PN ( ThreeTreeNode * T, datatype& x ) {
if ( T == NULL ) return NULL;
else {
ThreeTreeNode* mt;
if ( T->data == x ) return T->parent;
else if ( mt = PN ( T->leftChild, x ) ) return mt;
else if ( mt = PN ( T->rightChild, x ) ) return mt;
return NULL;
}
}
算法功能：__________________________________________________
5.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。
void BTC ( BinTreeNode* BT ) {
if ( BT != NULL ) {
if ( BT->leftChild != NULL && BT->rightChild != NULL )
if ( BT->leftChild->data > BT->rightChild->data ) {
BinTreeNode* t = BT->leftChild;
BT->leftChild = BT->rightchild;
BT->rightChild = t;
}
BTC ( BT->leftChild );
BTC ( BT->rightChild );
}
}
算法功能：_________________________________________________
6.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild;};
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定指针bt指向一棵二叉树，该二叉树的广义表表示为a (b (a, d (f) ), c (e ( , a (k) ), b) )，整数变量C的值为0，若：
(1) 执行BTC1( bt, ’a’, C ) 调用后，C的值为________;
(2) 执行BTC1( bt, ’b’, C ) 调用后，C的值为________;
(3) 执行BTC1( bt, ’c’, C) 调用后，C的值为________;
(4) 执行BTC1( bt, ’g’, C) 调用后，C的值为________;
void BTC1( BinTreeNode* BT, char x, int& k ) {
if ( BT != NULL ) {
if ( BT->data == x ) k++;
BTC1( BT->leftChild, x, k );
BTC1( BT->rightChild, x, k );
}
}
7.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data; BinTreeNode * leftChild, * rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。下面函数的功能是从二叉树BT中查找值为x的结点，若查找成功则返回结点地址，否则返回空。请在划有横线的地方填写合适内容。
BinTreeNode* BTF ( BinTreeNode* BT, ElemType& x ) {
if ( BT == NULL ) _____(1)______;
else {
if ( BT->data == x ) _____(2)_____;
else {
BinTreeNode* t;
If ( t = BTF ( BT->leftChild, x ) ) _____(3)_____;
___________(4)___________;
else return NULL;
}
}
}
(1) _____________________________________________
(2) _____________________________________________
(3) _____________________________________________
(4) _____________________________________________
8.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。
int DST ( BinTreeNode*& BT, ElemType x ) {
if ( BT == NULL ) return 0;
else {
if ( BT->data == x ) { BT = NULL; return 1; }
else {
if ( DST ( BT->leftChild, x ) ) return 1;
if ( DST ( BT->rightChild, x ) ) return 1;
else return 0;
}
}
}
算法功能：_________________________________________________
9.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。假定一棵二叉树采用链接存储，它的广义表表示为r (b (, d (f, g) ), t (e) )，rt, bt, dt和et指针变量分别保存指向r, b, d和e结点的指针值，则：
(1)执行BTM (rt) 调用后，得到的函数值为________;
(2)执行BTM (bt) 调用后，得到的函数值为________;
(3)执行BTM (dt) 调用后，得到的函数值为________;
(4)执行BTM (et) 调用后，得到的函数值为________;
char BTM(BinTreeNode* BT) {
static char max = 0;
if ( BT != NULL ) {
char k1, k2;
k1 = BTM ( BT->leftChild );
k2 = BTM ( BT->rightChild );
if ( k1 > max ) max = k1;
else if ( k2 > max ) max = k2;
else if ( BT->data > max ) max = BT->data;
}
return max;
}
10.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { ElemType data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数BT指向一棵二叉树的根结点。
void preserve ( BinTreeNode* BT, ElemType a[ ], int n ) {
static int i = 0;
if ( BT != NULL ) {
preserve ( BT->leftChild, a, n );
a[i++] = BT->data;
preserve ( BT->rightChild, a, n );
}
}
算法功能：__________________________________________________
11.假定在a[10]数组中数据为 { 16, 42, 35, 73, 54, 38, 80 }，n为整型变量，其值为7，则执行IH ( a, n, 25 ) 调用下面算法后数组a中的数据变为：_________________________
void IH ( int HBT[ ], int& n, int item ) {
HBT[n] = item;
n++;
int x = item;
int i = n-1;
while ( i != 0 ) {
int j = (i-1)/2;
if ( x >= HBT[j] ) break;
HBT[i] = HBT[j];
i = j;
}
HBT[i] = x;
}
12.假定在a[10]数组中数据为 {16, 35, 42, 73, 54, 68, 80, 26}，n为整型变量，其值为8，则执行DH ( a, n ) 调用下面算法后数组a中的数据变为：____________________________
int DH ( int HBT[ ], int& n ) {
if ( n == 0 ) { cerr << "null!" << endl; exit (1); }
int temp = HBT[0];
n--;
int x = HBT[n];
int i = 0, j = 2*i+1;
while ( j <= n-1 ) {
if ( j < n-1 && HBT[j] > HBT[j+1] ) j++;
if ( x <= HBT[j] ) break;
HBT[i] = HBT[j];
i = j; j = 2*i+1;
}
HBT[i] = x;
return temp;
}
参考答案:
1.(1) return c1+1 //2分
(2) NodeLevel ( BT->rightChild, X ) //3分
(3) if (c2 >= 0 ) return c2+1 //3分
2.(1) return PT //2分
(2) if ( PT = ParentPtr ( BT->rightChild, BT, X ) ) return PT //4分
(3) return NULL或return 0 //2分
3.算法功能：生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右子树交换的结果。
4.算法功能：从树根指针为T的二叉树中查找值为X的结点，返回指向父结点的指针。
5.算法功能：对二叉树BT进行处理，当BT中每个结点的左孩子的值大于右孩子的值则交换左右子树。
6.(1) 3 //2分
(2) 2 //2分
(3) 1 //2分
(4) 0 //2分
7.(1) return NULL //2分
(2) return BT //2分
(3) return t //2分
(4) if ( t = BTF ( BT->rightChild, x ) ) return t //2分
8.算法功能：从一棵二叉树中删除根结点值为x的子树，若删除成功则返回1，否则返回0。
9.(1) ’t’ //2分
(2) ’g’ //2分
(3) ’g’ //2分
(4) ’e’ //2分
10.算法功能：对具有n个结点的二叉树进行中根遍历，把得到的结点值序列保存到数组a中。
11.{16, 25, 35, 42, 54, 38, 80, 73 } //有一处错则不得分
12.{ 26, 35, 42, 73, 54, 68, 80 } //有一处错则不得分
3、算法设计
（1）利用二叉树字符串“A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”创建二叉树的二叉链式存储结构；
（2）输出该二叉树；
（3）输出‘H’节点的左、右孩子结点值；
（4）输出该二叉树的结点个数、叶子结点个数、二叉树的度和高度；
btree.h
#pragma once
#include<iostream>
#include<malloc.h>
using namespace std;
const int MaxSize = 100;
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node* lchild;
struct node* rchild;
}BTNode;
void CreateBTree(BTNode*& b, char* str); //创建二叉树
void DestoryBTree(BTNode*& b); //销毁二叉树（递归实现）
void DispBTree(BTNode* b); //输出二叉树（递归实现）
int BTHeight(BTNode* b); //求树的高度（递归实现）
BTNode* FindNode(BTNode* b, ElemType e); //查找结点
BTNode* LchildNode(BTNode* b); //返回左孩子结点
BTNode* RchildNode(BTNode* b); //返回右孩子结点
int CountNodes(BTNode* b); //二叉树的结点个数，递归实现
int LeafNodes(BTNode* b); //叶子结点个数
void CountDu(BTNode* b, int& du);//二叉树的度
btree.cpp
#include"btree.h"
void CreateBTree(BTNode*& b, char* str) //创建二叉树
{
BTNode* St[MaxSize], * p=NULL;
b = NULL;
int j = 0, k = 0, top = -1; //k等于1：这个节点作为左孩子，等于2时作为右孩子
char ch = str[j];
while (ch!='\0')
{
switch (ch)
{
case'(':top++; St[top] = p; k = 1; break; //处理左子树
case')':top--; break; //子树处理完了
case',':k = 2; break; //处理右子树
default:
p = (BTNode*)malloc(sizeof(BTNode));
p->data = ch;
p->lchild = p->rchild = NULL;
if (b==NULL) //如果是第一个，那么视为根结点
{
b = p;
}
else //已经有根结点了
{
switch (k)
{
case 1:St[top]->lchild = p; break;
case 2:St[top]->rchild = p; break;
default:
break;
}
}
break;
}
j++;
ch = str[j]; //遍历下一个字符
}
}
void DestoryBTree(BTNode*& b) //销毁二叉树（递归实现）
{
if (b!=NULL) //递归实现销毁
{
DestoryBTree(b->lchild);
DestoryBTree(b->rchild);
free(b);
}
}
void DispBTree(BTNode* b) //输出二叉树
{
if (b!=NULL)
{
cout << b->data; //根结点直接输出，后续递归输出分支结点
if (b->lchild!=NULL || b->rchild!=NULL)
{
cout << " ( ";
DispBTree(b->lchild); //递归处理左子树
if (b->rchild!=NULL)
{
cout << ",";
}
DispBTree(b->rchild); //递归处理右子树
cout << " ) ";
}
}
}
int BTHeight(BTNode* b) //求树的高度（递归实现）
{
int lchild_height, rchild_height;
if (b==NULL)
{
return 0;
}
else //递归找到最大高度，然后别忘了加上根结点
{
lchild_height = BTHeight(b->lchild);
rchild_height = BTHeight(b->rchild);
return (lchild_height > rchild_height) ? (lchild_height + 1) : (rchild_height + 1);
}
}
BTNode* FindNode(BTNode* b, ElemType e) //查找结点
{
BTNode* p;
if (b==NULL) //如果根结点或者最后找不到，返回空
{
return NULL;
}
else if (b->data==e) //如果找到一个结点等于e值，返回该结点
{
return b;
}
else //递归实现遍历左右分支结点
{
p = FindNode(b->lchild, e);
if (p!=NULL)
{
return p;
}
else
{
return FindNode(b->rchild, e);
}
}
}
BTNode* LchildNode(BTNode* b) //返回左孩子结点
{
return b->lchild;
}
BTNode* RchildNode(BTNode* b) //返回右孩子结点
{
return b->rchild;
}
int CountNodes(BTNode* b) //二叉树的结点个数，递归实现
{
int lchild_num, rchild_num;
if (b == NULL)
{
return 0;
}
else if (b->lchild == NULL && b->rchild == NULL)
{
return 1;
}
else
{
lchild_num = CountNodes(b->lchild);
rchild_num = CountNodes(b->rchild);
return lchild_num + rchild_num + 1;
}
}
int LeafNodes(BTNode* b) //叶子结点个数
{
int lchild_num, rchild_num;
if (b == NULL)
{
return 0;
}
else if (b->lchild == NULL && b->rchild == NULL)
{
return 1;
}
else
{
lchild_num = LeafNodes(b->lchild);
rchild_num = LeafNodes(b->rchild);
return lchild_num + rchild_num;
}
}
void CountDu(BTNode* b, int& du)//二叉树的度
{
if (du==2)//度为2时可返回，因为二叉树的度最大为2
{
return;
}
else if (b->lchild&&b->rchild)
{
du = 2; return;
}
else if (b->lchild || b->rchild) //如果该结点只有左右子树之一，取较大值
{
du = du > 1 ? du : 1;
if (b->lchild)
{
CountDu(b->lchild, du);
}
else
{
CountDu(b->rchild, du);
}
}
else
{
du = 0; return;
}
}
btree_main.cpp
#include "btree.h"
int main()
{
BTNode* b, *p ,*Lc ,*Rc;
char str[50] = "A(B(D, E(H(J, K(L, M(, N))))), C(F, G(, I)))";
//char str[50] = "A(,B(C,D))";//测试统计度
cout << "创建二叉树并输出：\n";
CreateBTree(b, str);
DispBTree(b);
cout << "\n输出‘H’节点的左、右孩子结点值：\n";
p = FindNode(b, 'H');
if (p!=NULL)
{
Lc = LchildNode(p);
if (Lc!=NULL)
{
cout << "H结点的左孩子为 :" << Lc->data<<endl;
}
else
{
cout << "H结点无左孩子。\n";
}
Rc = RchildNode(p);
if (Rc != NULL)
{
cout << "H结点的右孩子为 :" << Rc->data << endl;
}
else
{
cout << "H结点无右孩子。\n";
}
}
//（4）输出该二叉树的结点个数、叶子结点个数、二叉树的度和高度；
cout << "该二叉树的结点个数："<<CountNodes(b)<<endl;
cout << "该二叉树的叶子结点个数："<<LeafNodes(b)<<endl;
int du = 0;
CountDu(b, du);
cout << "该二叉树的度："<<du<<endl;
cout << "该二叉树的高度："<<BTHeight(b)<<endl;
}
2、[二叉链存储结构+先序递归遍历算法]
1.
假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法计算一棵给定二叉树b中的所有双分支结点个数。
解:采用基于先序遍历的递归方法。
int DsonNode(BTNode *b)
{
int num1;
int num2;
int n;
if(b==NULL)
{
return 0;
}
else if(b->lchild!=NULL and b->rchild!=NULL)
{
n = 1;
}
else n=0;
num1 = DsonNode(b->lchild);
num2 = DsonNode(b->rchild);
return num1+num2+n;
}
2.
假设二叉树中每个结点值为单个字符，采用二叉链存储结构存储。设计一个算法，求该二叉树中距离根结点最近的叶子结点。
解:采用基于先序遍历的递归方法，用min记录结点层次(初始值取个大整数)，I表示当前访问结点的层次。先判断根结点，若为叶子结点，其层次l小于min，置min=I，用x记录其结点值；再到左子树中查找并比较，最后到右子树中查找并比较。
//l的初始值为1，min为大整数，x为所求的叶子结点。
void MinLenLeaf(BTNode *b, int l, int &min ,char &x)
{
if(b!=NULL)
{
if(b->lchild==NULL and b->rchild==NULL)
{
if(l<min)
{
min = l;
x = b->data;
}
}
MinLenLeaf(b->lchild, l+1, min, x);
MinLenLeaf(b->rchild, l+1, min, x);
}
}
3.
假设二叉树采用二叉链存储结构存储，试设计一个算法，输出从每个叶子结点到根结点的逆路径。
解:采用基于先序遍历的递归方法，用path数组存放查找的路径，pathlen存放路径长度，当找到叶子结点b时，由于b叶子结点尚未添加到path中，因此在输出路径时还需输出b->data值；若b不为叶子结点，将b->data放人path中，然后在左、右子树中递归查找。
//pathlen的初值为0；
void AllPath(BTNode * b, ElemType path[], int pathlen)
{
if(b!=NULL)
{
if(b->lchild==NULL and b->rchild==NULL)
{
cout<<b->data<<"到根结点逆路径："<<b->data;
for(int i=pathlen-1; i>=0 ; i--)
{
cout<<path[i];
}
}
else{
path[pathlen]=b->data;
pathlen++;
AllPath(b->lchild,path,pathlen);
AllPath(b->rchild,path,pathlen);
pathlen--;
}
}
}
1.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树高度的算法，该高度由函数返回。假定根结点的层次为0，参数BT初始指向这棵二叉树的根结点。
int BTreeHeight ( BinTreeNode* BT );
2.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BTreeNode { char data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。
int BTreeCount ( BinTreeNode* BT );
3.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向这棵二叉树的根结点。
int BTreeLeafCount ( BinTreeNode* BT );
4.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出删除一棵二叉树中所有结点的算法，并使树根指针为空。假定引用参数BT初始指向这棵二叉树的根结点。
void ClearBinTree ( BinTreeNode*& BT);
5.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1，否则返回0。算法中参数T1和T2为分别指向这两棵二叉树根结点的指针。当两棵树的结构完全相同并且对应结点的值相同时才被认为相等。
int BTreeEqual ( BinTreeNode* T1, BinTreeNode* T2 );
6.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出交换一棵二叉树中所有结点的左、右指针域值的算法，算法中参数BT初始指向这棵二叉树的根结点。
void BTreeSwop ( BinTreeNode* BT );
7.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出复制一棵二叉树的算法，并返回复制得到的二叉树的树根指针。算法中参数BT初始指向待复制二叉树的根结点。
BinTreeNode* BTreeCopy ( BinTreeNode* BT );
8.已知二叉树中的结点类型用BinTreeNode表示，被定义为:
struct BinTreeNode { char data; BinTreeNode *leftChild, *rightChild; };
其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根据下面函数声明编写出从一棵二叉树中求出结点值大于x的结点个数的算法，并返回所求结果。算法中参数BT初始指向二叉树的根结点。
int BTreeCount ( BinTreeNode* BT, ElemType x );
参考答案：
//1.算法如下
int BTreeHeight ( BinTreeNode* BT ) {
if ( BT == NULL ) return –1; //对于空树，返回-1并结束递归，1分
else {
int h1 = BTreeHeight ( BT->leftChild ); //计算左子树的高度，2分
int h2 = BTreeHeight (BT->rightChild ); //计算右子树的高度，2分
if ( h1 > h2 ) return h1+1;
else return h2+1; //返回树的高度，3分
}
}
//2.算法如下
int BTreeCount ( BinTreeNode* BT ) {
if ( BT == NULL ) return 0; //2分
else
return BTreeCount ( BT->leftChild ) + BTreeCount ( BT->rightChild ) + 1; //6分
}
//3.算法如下
int BTreeLeafCount ( BinTreeNode* BT ) {
if ( BT == NULL ) return 0; //1分
else if (BT->leftChild == NULL && BT->rightChild == NULL) return 1; //3分
else return BTreeLeafCount ( BT->leftChild ) + BTreeLeafCount ( BT->rightChild ); //4分
}
//4.算法如下
void ClearBinTree ( BinTreeNode*& BT ) {
if ( BT!=NULL ) { //1分
ClearBinTree ( BT->leftChild ); //递归删除左子树，2分
ClearBinTree ( BT->rightChild ); //递归删除右子树，2分
delete BT; //回收根结点，2分
BT = NULL; //置根指针为空，1分
}
}
//5.算法如下
int BtreeEqual ( BinTreeNode* T1, BinTreeNode* T2) {
if ( T1 == NULL && T2 == NULL ) return 1; //若两棵树均为空则返回1，1分
else if ( T1 == NULL || T2 == NULL) return 0; //若一棵为空一棵不为空则返回0，2分
else if ( T1->data == T2->data && BTreeEqual ( T1->leftChild, T2->leftChild ) &&
BTreeEqual (T1->rightChild, T2->rightChild ) ) return 1;
//若根结点值相等并且左、右子树对应相等则两棵树相等，3分
else return 0; //若根结点值不等或左、右子树对应不等则两棵树不等，2分
}
//6.算法如下
void BTreeSwop ( BinTreeNode* BT ) {
if ( BT != NULL ) { //1分
BinTreeNode* pt = BT->leftChild;
BT->leftChild = BT->rightChild;
BT->rightChild = pt; //交换左右子女指针域的值，3分
BtreeSwop ( BT->leftChild ); //对左子树进行同样处理，2分
BtreeSwop ( BT->rightChild ); //对右子树进行同样处理，2分
}
}
//7.算法如下
BinTreeNode* BtreeCopy ( BinTreeNode* BT ) {
if ( BT == NULL ) return NULL; //1分
else {
BinTreeNode* pt = new BinTreeNode; //得到新结点，1分
pt->data = BT->data; //复制根结点值，1分
pt->leftChild = BtreeCopy ( BT->leftChild ); //复制左子树，2分
pt->rightChild = BTreeCopy ( BT->rightChild ); //复制右子树，2分
return pt; //返回新树的树根指针，1分
}
}
//8.算法如下
//统计出二叉树中大于给定值x的结点个数，该统计值由函数返回
int BtreeCount ( BinTreeNode* BT, ElemType x ) {
if ( BT == NULL ) return 0; //1分
else if ( BT->data > x )
return BtreeCount ( BT->leftChild, x ) + BtreeCount ( BT->rightChild, x ) + 1; //4分
else
return BtreeCount ( BT->leftChild, x ) + BtreeCount ( BT->rightChild, x ); //3分
}