数据结构 树和二叉树代码_树和二叉树数据结构
数据结构 树和二叉树代码由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“树和二叉树数据结构”。
树和二叉树
一、实验目的：
参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。
二、实验要求：
1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1．设计实现二叉树类，要求：
（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。（2）实现二叉树层次遍历的非递归算法。
（3）假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。
（4）编写求二叉树高度的函数（5）编写一主函数来验证算法实现。2.设计实现二叉线索链表类，要求：
（1）编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的遍历算法。
（2）编写一主函数来验证算法实现。*3.编写创建哈夫曼树和生成哈夫曼编码的算法。
*4．假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点到根结点的路径。
*5．假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即具有结点数最多的层次上结点总数）
四、程序样例
#include #include using namespace std;template struct BiNode{ T data;BiNode *lchild, *rchild;};int max(int a,int b){ return a > b ? a : b;} template cla BiTree{ public: BiTree();//构造函数，初始化一棵空的二叉树
~BiTree()//二叉树的析构函数算法BiTree { Release(root);} void InOrder(){ InOrder(root);} //中序遍历二叉树
void PreOrder(){ PreOrder(root);} void PostOrder(){PostOrder(root);} //后序遍历二叉树
void LeverOrder(){LeverOrder(root);} //层序遍历二叉树
void Count(){Count(root);} void PreOrdercnt(){PreOrdercnt(root);} int Depth(){int www.daodoc.comt(BiNode *root);///设计算法按前序次序打印二叉树中的叶子结点;int Depth(BiNode *root);//深度； };template BiTree::BiTree(){ Creat(root);} template void BiTree ::Creat(BiNode *&root){ char ch;cin>>ch;if(ch=='#')root=NULL;//建立一棵空树
else {
root=new BiNode;//生成一个结点
root->data=ch;
Creat(root->lchild);//递归建立左子树
Creat(root->rchild);//递归建立右子树 } } template void BiTree::LeverOrder(BiNode *root){ BiNode * Q[100];int front = 0, rear = 0;//采用顺序队列，并假定不会发生上溢 if(root==NULL)return;Q[++rear]=root;while(front!=rear){ BiNode * q=Q[++front];coutdatalchild!=NULL)Q[++rear]=q->lchild;if(q->rchild!=NULL)Q[++rear]=q->rchild;} } template void BiTree::PostOrder(BiNode *root){ if(root == NULL)return;//递归调用的结束条件
else {
PostOrder(root->lchild);//后序递归遍历root的左子树
PostOrder(root-> rchild);//后序递归遍历root的右子树
coutdata
} } template void BiTree::PreOrder(BiNode *root){ if(root ==NULL)return;//递归调用的结束条件
else {
coutdatalchild);//前序递归遍历root的左子树
PreOrder(root->rchild);//前序递归遍历root的右子树 } } template void BiTree ::Release(BiNode *root){ if(root!=NULL){
Release(root->lchild);//释放左子树
Release(root->rchild);//释放右子树
delete root;} }
template void BiTree::InOrder(BiNode *root)//二叉树的中序遍历递归算法InOrder{ if(root==NULL)return;//递归调用的结束条件
else {
InOrder(root->lchild);//中序递归遍历root的左子树
coutdata
InOrder(root->rchild);//中序递归遍历root的右子树
} } int n = 0;template void BiTree::Count(BiNode *root)//n为全局量并已初始化为0 { if(root){ Count(root->lchild);n++;///求二叉树的结点个数 Count(root->rchild);} } int cnt = 0;template void BiTree::PreOrdercnt(BiNode *root)///设计算法按前序次序打印二叉树中的叶子结点;{ if(root){ if(!root->lchild &&!root->rchild)
{ coutdata
cnt++;
} PreOrdercnt(root->lchild);PreOrdercnt(root->rchild);} } template int BiTree::Depth(BiNode *root)//算法求二叉树的深度 { if(root==NULL)return 0;else { int hl= Depth(root->lchild);int hr= Depth(root->rchild);return max(hl, hr)+1;} } int main(){ BiTree mytree;cout
enum flag {Child, Thread};//枚举类型，枚举常量Child=0，Thread=1 template struct ThrNode //二叉线索树的结点结构 { T data;ThrNode *lchild, *rchild;flag ltag, rtag;};
template cla InThrBiTree { public: InThrBiTree();//构造函数，建立中序线索链表
~InThrBiTree();//析构函数，释放线索链表中各结点的存储空间
ThrNode* Getroot();//获取根结点
ThrNode* Next(ThrNode* p);//查找结点p的后继 void InOrder(ThrNode* root);//中序遍历线索链表 private: ThrNode* root;//指向线索链表的头指针 ThrNode* Creat();//构造函数调用
void ThrBiTree(ThrNode* root);//构造函数调用 void Release(ThrNode* root);//析构函数调用 };#endif //定义类InThrBiTree中的成员函数，文件名为inthrbitree.cpp #include #include #include“inthrbitree.h” using namespace std;//构造一棵中序线索二叉树 template InThrBiTree::InThrBiTree(){ ThrNode* pre = NULL;this->root = Creat();ThrBiTree(root);} //释放中序线索二叉链表中各结点的存储空间 template InThrBiTree::~InThrBiTree(void){ Release(root);} //获取指向中序线索二叉树根结点的指针 template ThrNode* InThrBiTree::Getroot(){ return root;} //输出指向结点p的后继结点的指针 template ThrNode* InThrBiTree::Next(ThrNode* p){ ThrNode* q;if(p->rtag==Thread)q = p->rchild;//右标志为1，可直接得到后继结点
else{ q = p->rchild;//工作指针初始化 while(q->ltag==Child)//查找最左下结点
{ q = q->lchild;
} } return q;}
//中序遍历一棵线索二叉树 template void InThrBiTree::InOrder(ThrNode *root){ ThrNode* p = root;if(root==NULL)return;//如果线索链表为空，则空操作返回 while(p->ltag==Child)//查找中序遍历序列的第一个结点p并访问 { p = p->lchild;} coutdatarchild!=NULL)//当结点p存在后继，依次访问其后继结点 { p = Next(p);coutdata ThrNode* InThrBiTree::Creat(){ ThrNode *root;T ch;cout>ch;if(ch==“#”)root = NULL;else{
root=new ThrNode;//生成一个结点 root->data = ch;root->ltag = Child;
root->rtag = Child;root->lchild = Creat();//递归建立左子树 root->rchild = Creat();//递归建立右子树 } return root;} //给二叉树建立线索 template void InThrBiTree::ThrBiTree(ThrNode *root){ if(root==NULL)return;//递归结束条件 ThrBiTree(root->lchild);if(!root->lchild){ //对root的左指针进行处理 root->ltag = Thread;root->lchild = pre;//设置pre的前驱线索 } if(!root->rchild)root->rtag = Thread;//对root的右指针进行处理
if(pre!= NULL){ if(pre->rtag==Thread)pre->rchild = root;//设置pre的后继线索 } pre = root;ThrBiTree(root->rchild);}
//释放中序线索二叉树的存储空间，析构函数调用
template void InThrBiTree::Release(ThrNode* root){ if(root!=NULL){ Release(root->lchild);//释放左子树 Release(root->rchild);//释放右子树 delete root;} } //线索二叉树的主函数，文件名为inthrbitreemain.cpp #include #include #include“inthrbitree.cpp” using namespace std;ThrNode* pre;void main(){ InThrBiTree inbt;//构造一棵线索二叉树
ThrNode* p = inbt.Getroot();//获取指向根结点的指针 cout
注意问题
1．注意理解有关树的各种递归算法的执行步骤。
2．注意字符类型数据在输入时的处理。3．重点理解如何利用栈结构实现非递归算法。
