用程序完成完整的二叉树结构的实现及测试（C语言）

源文件：

#include
#include
#include "BinaryTree.h"

template
BinTreeNode *BinaryTree::Parent (BinTreeNode *subTree, BinTreeNode *t) {
//私有函数: 从结点 subTree 开始, 搜索结点 t 的双
//亲, 若找到则返回双亲结点地址, 否则返帆雹塌回NULL
if (subTree == NULL) return NULL;
if (subTree->leftChild == t || subTree->rightChild == t )
return subTree; //找到, 返回父结点肆帆地址
BinTreeNode *p;
if ((p = Parent (subTree->leftChild, t)) != NULL)
return p; //递归在左子树中搜索
else return Parent (subTree->rightChild, t);
//递归在左子树中搜索
};

template
void BinaryTree::Destroy (BinTreeNode * subTree) {
//私有函数: 删除根为subTree的子树
if (subTree != NULL) {
Destroy (subTree->leftChild); //删除左子树
Destroy (subTree->rightChild); //删除右子树
delete subTree; //删除根结点
}
};

template
void BinaryTree::InOrder (BinTreeNode * subTree) {
if (subTree != NULL) {
InOrder (subTree->leftChild); //遍历左子树
cout<data<<"|"; //访问根结点
InOrder (subTree->rightChild); //遍历右子树
}
};

template
void BinaryTree::PreOrder (BinTreeNode * subTree) {
if (subTree != NULL) {
cout<data<<"|"; //访问根结点
PreOrder (subTree->leftChild); //遍历左子树
PreOrder (subTree->rightChild); //遍历右子树
}
};

template
void BinaryTree::PostOrder (BinTreeNode * subTree) {
if (subTree != NULL ) {
PostOrder (subTree->leftChild); //遍历左子树态圆
PostOrder (subTree->rightChild); //遍历右子树
cout<data<<"|"; //访问根结点
}
};

template
int BinaryTree::Size (BinTreeNode * subTree){
//私有函数：利用二叉树后序遍历算法计算二叉
//树的结点个数
if (subTree == NULL) return 0; //空树
else return 1+Size (subTree->leftChild) + Size (subTree->rightChild);
};

template
int BinaryTree::Height ( BinTreeNode * subTree){
//私有函数：利用二叉树后序遍历算法计算二叉
//树的高度或深度
if (subTree == NULL) return 0; //空树高度为0
else {
int i = Height (subTree->leftChild);
int j = Height (subTree->rightChild);
return (i < j) ? j+1 : i+1;
}
};

template
void BinaryTree::CreateBinTree (T RefValue, BinTreeNode * & subTree) {
//前序序列从键盘输入建立二叉树。
T item;
cin >> item; //读入根结点的值
if (item != RefValue) {
subTree = new BinTreeNode(item); //建立根结点
if (subTree == NULL)
{cerr << "存储分配错!" << endl; exit (1);}
CreateBinTree (RefValue, subTree->leftChild); //递归建立左子树
CreateBinTree (RefValue, subTree->rightChild); //递归建立右子树
}
else subTree = NULL; //封闭指向空子树的指针
};

头文件：

#pragma once

template
struct BinTreeNode { //二叉树结点类定义
T data; //数据域
BinTreeNode *leftChild, *rightChild; //左子女、右子女链域
BinTreeNode () //构造函数
{ leftChild = NULL; rightChild = NULL; }
BinTreeNode (T x, BinTreeNode *l = NULL, BinTreeNode *r = NULL)
{ data = x; leftChild = l; rightChild = r; }
};

template
class BinaryTree { //二叉树类定义
protected:
BinTreeNode *root; //二叉树的根指针
T RefValue; //数据输入停止标志
void Destroy (BinTreeNode * subTree); //删除
int Height (BinTreeNode *subTree); //返回树高度
int Size (BinTreeNode *subTree); //返回结点数
BinTreeNode *Parent (BinTreeNode * subTree, BinTreeNode *t); //返回父结点
void PreOrder (BinTreeNode* subTree); //前序遍历
void InOrder (BinTreeNode* subTree); //中序遍历
void PostOrder (BinTreeNode* subTree); //后序遍历
void CreateBinTree (T RefValue, BinTreeNode * & subTree); //从键盘读入建树
public:
BinaryTree () : root (NULL) { } //构造函数
BinaryTree (T value) : RefValue(value), root(NULL) { } //构造函数
~BinaryTree () { Destroy(root); } //析构函数
bool IsEmpty () { return root == NULL;} //判二叉树空否
int Height () { return Height(root); } //求树高度
int Size () { return Size(root); } //求结点数
BinTreeNode *Parent (BinTreeNode *t)
{ return (root == NULL || root == t) ? NULL : Parent (root, t); } //返回双亲结点
BinTreeNode *LeftChild (BinTreeNode *t)
{ return (t != NULL)?t->leftChild : NULL; } //返回左子女
BinTreeNode *RightChild (BinTreeNode *t)
{ return (t != NULL)?t->rightChild : NULL; } //返回右子女
BinTreeNode *GetRoot () const { return root; } //取根
void PreOrder ()
{ PreOrder (root); } //前序遍历
void InOrder ()
{ InOrder (root); } //中序遍历
void PostOrder ()
{ PostOrder (root); } //后序遍历
void CreateBinTree ()
{ CreateBinTree (RefValue, root);} //从键盘读入建树
};

/扒磨晌*
实验任务:

（1）创建二叉树，实现二春锋叉树前序、中序、后序遍历算法。

（2）查找指定结点。
（3）设计算法统计二叉树中结点的个数、度为1的结点个数。

（4）设计算法求出二叉树的高度。
*/

#include
#include
#include
#define MAXSIZE 100
typedef char datatype;
typedef struct node
{
datatype data;
struct node *lchild, *rchild;
}bitree;
void CreateBitree(bitree * &t,datatype *data)
{
bitree *St[MAXSIZE],*p=NULL;
int top=-1,k,j=0;
char ch;
t=NULL;
ch=data[j];
while(ch!='\0')
{
switch(ch)
{
case '(':top++;St[top]=p;k=1;break;
case ')':top--;break;
case ',':k=2;break;
default:
p=(bitree *)malloc(sizeof(bitree));
p->data=ch;
p->lchild=p->rchild=NULL;
if(t==NULL)
t=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=data[j];

}
}
void visite(datatype data)
{
printf("%c\t",data);
}
void preorder ( bitree *t ) //前序遍历二叉树
{
if ( t != NULL )
{
visite (t->data);
preorder ( t->lchild );
preorder ( t->rchild );
}
}
void inorder ( bitree *t )//中序遍历二叉树
{
if ( t != NULL )
{
inorder ( t->lchild );
visite (t->data);
inorder ( t->rchild );
}
}
void postorder ( bitree *t )//后序游胡遍历二叉树
{
if ( t != NULL )
{
postorder ( t->lchild );
postorder ( t->rchild );
visite (t->data);
}
}
bitree * find( bitree *t, datatype x) //在二叉树中查找指定节点
{
bitree *p;
if(t==NULL)
return(NULL);//空树
if (t->data==x)
return(t);//查找成功
p=find(t->lchild,x); //查找左子树
if(p==NULL)
p=find(t->rchild,x); //查找右子树
return(p);
}
int onenodenum(bitree *t)//度为1的结点个数。
{
int nl,nr;
if(t==NULL)
return 0;
if(t->lchild!=NULL && t->rchild!=NULL)
return 0;
else
return 1;
nl=onenodenum(t->lchild);
nr=onenodenum(t->rchild);
return nl+nr;
}
int nodenumber(bitree *t)//统计二叉树中结点的个数
{
int nl,nr;
int leaf;
if ( t == NULL )
return 0;
if(t->lchild==NULL && t->rchild==NULL)
return 1;
nl=nodenumber(t->lchild);
nr=nodenumber(t->rchild);
leaf=nl+nr;

return (2*leaf-1+onenodenum(t));
}
int bitreeHeight(bitree *t)
{
int lchildh,rchildh;
if(t==NULL)
return 0;
else
{
lchildh=bitreeHeight(t->lchild);
rchildh=bitreeHeight(t->rchild);
return(lchildh>rchildh)?(lchildh+1):(rchildh+1);
}

}

void printlist()
{
printf("请选择一个功能!\n");
printf("◆(1): 前序遍历\n");
printf("◆(2): 中序遍历\n");
printf("◆(3): 后序遍历\n");
printf("◆(4): 查找指定结点\n");
printf("◆(5): 统计二叉树中结点的个数、度为1的结点个数\n");
printf("◆(6): 求出二叉树的高度\n");
printf("◆(7): 离开\n");
printf("You choose: ");
}

void main()
{
int function;
int b;
bitree *t;
datatype x;
datatype data[MAXSIZE];
printf("Please input the value!\n");
scanf("%s",data);
CreateBitree(t,data);

for(b=0;b>=0;b++)
{
printlist();
scanf("%d",&function);
if(function==7)
break;
else
{
switch(function)
{

case 1:
{
preorder(t);break;
}

case 2:
{
inorder(t);break;
}
case 3:
{
postorder(t);break;

}
case 4://查找指定结点
{
bitree *s;
printf("Please input the value you want to find!\n");
fflush(stdin);//清空缓存区
scanf("%c",&x);
s=find(t,x);//将查找返回的指针赋值给s
if(s!=NULL)
printf("Successfully find!\n");
else
printf("No such node!\n");
break;
}
case 5:
{
int allnode,onenode;
allnode=nodenumber(t);
onenode=onenodenum(t);
printf("结点个数为%d,度为1的结点个数为%d\n",allnode,onenode);
break;
}
case 6:
{
int height;
height=bitreeHeight(t);
printf("二叉树的高度为%d\n",height);
break;

}

default:
printf("No such function!\n");break;
};
}
printf("Press any button to proceed\n");
printf("-------------------------------------\n");
getch();
}
}

用程序完成 完整的二叉树结构的实现及测试（C语言）

用程序完成完整的二叉树结构的实现及测试（C语言）