数据结构实验 2

题目一：遍历二叉树

一、实验目的

熟练掌握指针变量、链表的含义
掌握二叉树的结构特性，以及二叉链表的存储方式的特点
掌握用递归的方法处理二叉树的基本算法
掌握二叉树的四种遍历方式（先序、中序、后序、按层次）

二、实验步骤

以二叉链表作为存储结构，要求以二叉树的先根序列输入建立二叉树。算法如下：
void CreatBiTree(BiTree &T)

{

char ch;

cin>>ch;

if(ch= ='#')

T=NULL;

else

{

T=new BiTNode;

T->data=ch;

CreatBiTree(T->lchild);

CreatBiTree(T->rchild);

}

}
例如，对下图所示的二叉树，则要求依次读入下列字符序列，则可建立相应的二叉链表：AB#D##CE###。

分别给出先序、中序（算法如下）、后序遍历二叉树的递归算法在二叉链表上的实现。
InOrderTraverse (BiTree T)

{
if(T)

{
InOrderTraverse(T->lchild);

cout<<T->data;
            InOrderTraverse(T->rchild);
     }
    }

给出二叉树的按层次遍历的算法。
求二叉树的高度
计算二叉树结点总数
输出叶子结点并统计其个数，
如何判断一颗二叉树是否满二叉树？

三、实验要求

实验代码：

#include <iostream>
using namespace std;struct BiTNode
{char data;BiTNode *lchild, *rchild;
};void visit(BiTNode *T)
{cout << T->data << " ";
}void CreatBiTree(BiTNode *&T)
{char ch;cin >> ch;if (ch == '#')T = NULL;else {T = new BiTNode;T->data = ch;CreatBiTree(T->lchild);CreatBiTree(T->rchild);}
}void PreOrderTraverse(BiTNode *T)
{if (T){visit(T);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}void InOrderTraverse(BiTNode *T)
{if (T){InOrderTraverse(T->lchild);visit(T);InOrderTraverse(T->rchild);}
}void PostOrderTraverse(BiTNode *T)
{if (T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);visit(T);}
}void LevelOrderTraverse(BiTNode *T)
{BiTNode *queue[100];int front = 0, rear = 0;if (T){queue[rear++] = T;while (front != rear){T = queue[front++];visit(T);if (T->lchild)queue[rear++] = T->lchild;if (T->rchild)queue[rear++] = T->rchild;}}
}void LeafCount(BiTNode *T, int &count)
{if (!T)return;if (!T->lchild && !T->rchild){visit(T);count++;}LeafCount(T->lchild, count);LeafCount(T->rchild, count);
}int TreeHeight(BiTNode *T)
{if (!T)return 0;int leftHeight = TreeHeight(T->lchild);int rightHeight = TreeHeight(T->rchild);return max(leftHeight, rightHeight) + 1;
}int TreeNodeCount(BiTNode *T)
{if (!T)return 0;return TreeNodeCount(T->lchild) + TreeNodeCount(T->rchild) + 1;
}int main()
{BiTNode *root;CreatBiTree(root);cout << "先序遍历： ";PreOrderTraverse(root);cout << endl;cout << "中序遍历： ";InOrderTraverse(root);cout << endl;cout << "后序遍历： ";PostOrderTraverse(root);cout << endl;cout << "层次遍历： ";LevelOrderTraverse(root);cout << endl;cout << "二叉树高度： " << TreeHeight(root) << endl;cout << "二叉树结点总数： " << TreeNodeCount(root) << endl;cout << "叶子结点： ";int leafCount = 0;LeafCount(root, leafCount);cout << endl;cout << "叶子结点个数： " << leafCount << endl;if(pow(2.0,TreeHeight(root))-1 == TreeNodeCount(root)){cout<<"该二叉树为满二叉树"<<endl;}else{cout<<"该二叉不为满二叉树"<<endl;}return 0;
}

题目二:用二叉树实现高校社团管理

问题描述:在高校中，为了丰富学生的业余生活，在学校的帮助下，会成立许多社团，少则几个，多则几十个。为了有效管理这些社团，要求编写程序实现以下功能：

①增加社团或会员；

②修改社团或会员相应信息；

③查询社团或会员信息；

④显示所有社团和会员信息；

问题分析:社团管理部门、社团和社团成员构成了完整的一棵树，如图1和图2所示。因此可以把它作为树的问题来解决。由于树结构比较复杂，不利于求解，先把树转换成二叉树。因此，高校社团管理就转化为对二叉树操作的问题。

在这颗二叉树中，结点类型是不同的，有社团结点，有成员结点。为了便于操作，特设置一个标志域type用于区分结点类型。（type=0表示社团，type=1表示会员）。

信息表

type	name	phone
0	社团管理委员会	23698
0	武术协会	34567
0	桥牌协会	45678
0	足球协会	12345
1	张三	13567
1	李四	13756
1	王五	133456

程序简介

数据结构的设计

typedef struct info //定义结点数据类型

{

int type; //0为社团，1为社团成员

char name[20]; //社团名称或成员姓名

char phone[11]; //联系电话

}DataType;

typedef struct Node //定义二叉链表数据类型

{

DataType data;

struct Node *lchild;

struct Node *rchild;

}BTNode,*BiTree;

主程序模块

int main(void)

{

BiTree r;

int choice;

CreatBiTree(r);

while(1)

{

cout<<endl<<"高校社团管理系统"<<endl;

cout<<"**********主菜单**********"<<endl;

cout<<" (1)增加社团或会员"<<endl;

cout<<" (2)修改社团或会员信息"<<endl;

cout<<" (3)查询社团或会员信息"<<endl;

cout<<" (4)显示所有信息"<<endl;

cout<<" (0)退出"<<endl;

cout<<"请选择(1,2,3,4,0):";

cin>>choice;

if(choice<0||choice>4)

continue;

switch(choice)

{

case 1:

Insert(r);

break;

case 2:

Update(r);

break;

case 3:

DisplayNode(r);

break;

case 4:

DisplayAll(r);

break;

case 0:

exit(0);

default:

break;

}

system("pause");

return 0;

}

各个函数功能

void CreatBiTree(BiTree &r) //前序遍历法创建二叉树

void DisplayNode(BiTree r) //根据名称查询并显示社团或会员信息

void Update(BiTree &r)

//修改社团或会员信息，若要修改的结点不存在，打印“不存在”，否则从键盘输入新的结点信息更新原有结点信息。

void Insert(BiTree &r) //增加社团或会员

void DisplayAll(BiTree r) //层次遍历，显示所有信息

系统界面显示效果

实验要求：

编写程序，使之能够实现基本的功能。
1. 1. 前序遍历法创建二叉树
  2. 显示所有信息
  3. 查询信息
  4. 修改信息
  5. 添加信息
添加功能int NodeCount(BiTree r)统计节点总数

实验代码：

#include <iostream>
using namespace std;typedef struct info
{int type; //0 为社团，1 为社团成员char name[20]; //社团名称或成员姓名char phone[11]; //联系电话
} DataType;typedef struct Node
{DataType data;struct Node *lchild;struct Node *rchild;
} BTNode, *BiTree;void CreatBiTree(BiTree &r)
{DataType data;cin >> data.type >> data.name >> data.phone;if (data.type == -1){r = NULL;}else{r = new BTNode;r->data = data;CreatBiTree(r->lchild);CreatBiTree(r->rchild);}
}void DisplayNode(BiTree r, const DataType &data)
{if (r == NULL){return;}if (strcmp(r->data.name, data.name) == 0){cout << "社团或会员信息为："<< endl;cout << r->data.type << " " << r->data.name << " " << r->data.phone << endl;}DisplayNode(r->lchild, data);DisplayNode(r->rchild, data);
}void Update(BiTree &r, const DataType &data)
{if (r == NULL){return;}if (strcmp(r->data.name, data.name) == 0){cin >> r->data.type >> r->data.name >> r->data.phone;}Update(r->lchild, data);Update(r->rchild, data);
}void Insert(BiTree &r)
{if (r == NULL){r = new BTNode;cin >> r->data.type >> r->data.name >> r->data.phone;r->lchild = NULL;r->rchild = NULL;}else{int choice;cout << "请选择插入位置（1.左子树 2.右子树）：";cin >> choice;if (choice == 1){Insert(r->lchild);}else{Insert(r->rchild);}}
}void DisplayAll(BiTree r)
{if (r == NULL){return;}cout << r->data.type << " " << r->data.name << " " << r->data.phone << endl;DisplayAll(r->lchild);DisplayAll(r->rchild);
}int NodeCount(BiTree r)
{if (r == NULL){return 0;}return NodeCount(r->lchild) + NodeCount(r->rchild) + 1;
}int main(void)
{BiTree r;int choice;CreatBiTree(r);while (1){cout << endl << "高校社团管理系统" << endl;cout << "**********主菜单**********" << endl;cout << " (1)增加社团或会员" << endl;cout << " (2)修改社团或会员信息" << endl;cout << " (3)查询社团或会员信息" << endl;cout << " (4)显示所有信息" << endl;cout << " (5)统计节点总数" << endl;cout << " (0)退出" << endl;cout << "请选择(1,2,3,4,5,0):";cin >> choice;if (choice < 0 || choice > 5)continue;switch (choice){case 1:Insert(r);break;case 2:{DataType data;cin >> data.type >> data.name >> data.phone;Update(r, data);break;}case 3:{DataType data;cin >> data.type >> data.name >> data.phone;DisplayNode(r, data);break;}case 4:DisplayAll(r);break;case 5:cout<<"节点总数为："<<NodeCount(r)<<endl;break;case 0:exit(0);default:break;}}system("pause");return 0;
}