代码2.txt

实用数据结构课后习题解答

template <class T>
struct Btnode //定义二叉链表结点类型
{ T d;//数据域
Btnode *lchild; //左指针域
Btnode *rchild; //右指针域
};


//文件名Binary_Tree.h
#include <iostream>
using namespace std;
//定义二叉链表结点类型
template <class T>
struct Btnode
{ T d;//数据域
Btnode *lchild; //左指针域
Btnode *rchild; //右指针域
};
//二叉链表类
template <class T>//类模板，T为虚拟类型
class Binary_Tree
{ private:
Btnode<T> *BT;//二叉链表根结点指针
public: //成员函数
Binary_Tree() { BT=NULL; return; }//二叉链表初始化
void creat_Binary_Tree(T);//生成二叉链表
void pretrav_Binary_Tree(); //前序遍历二叉链表
void intrav_Binary_Tree();//中序遍历二叉链表
void postrav_Binary_Tree(); //后序遍历二叉链表
};


182009▲ ▲ 2547▲ ▲ ▲ 36 ▲ 1206 ▲ ▲ 33 ▲ ▲


//生成二叉链表
template <class T>
void Binary_Tree<T>∷creat_Binary_Tree(T end)
{ Btnode<T> *p;
T x;
cin >>x;//输入第一个结点值
if (x==end) return;//第一个值为结束符值
p=new Btnode<T>; //申请二叉链表根结点
p->d=x; p->lchild=NULL; p->rchild=NULL;
BT=p; //二叉树根结点
creat(p, 1, end);//输入左子结点值
creat(p, 2, end);//输入右子结点值
return;
}
template <class T>
static creat(Btnode<T> *p, int k, T end)
{ Btnode<T> *q;
T x;
cin >>x;//输入结点值
if (x!=end) //结点值为非结束符值
 { q=new Btnode<T>; //申请一个二叉链表结点
q->d=x; q->lchild=NULL; q->rchild=NULL;
if (k==1) p->lchild=q;//链接到左子树
if (k==2) p->rchild=q;//链接到右子树
creat(q, 1, end); //输入左子结点值
creat(q, 2, end); //输入右子结点值
}
return 0;
}


//前序遍历二叉链表
template <class T>
void Binary_Tree<T>∷pretrav_Binary_Tree()
{ Btnode<T> *p;
p=BT;
pretrav(p); //从根结点开始前序遍历
cout <<endl;
return;
}
template <class T>
static pretrav(Btnode<T> *p)
{ if (p!=NULL)
 { cout <<p->d <<" ";//输出根结点值
 pretrav(p->lchild); //前序遍历左子树
 pretrav(p->rchild); //前序遍历右子树
 }
return 0;
}


//中序遍历二叉链表
template <class T>
void Binary_Tree<T>∷intrav_Binary_Tree()
{ Btnode<T> *p;
p=BT;
intrav(p);//从根结点开始中序遍历
cout <<endl;
return;
}
template <class T>
static intrav(Btnode<T> *p)
{ if (p!=NULL)
 { intrav(p->lchild);//中序遍历左子树
 cout <<p->d <<" ";//输出根结点值
 intrav(p->rchild);//中序遍历右子树
 }
return 0;
}


//后序遍历二叉链表
template <class T>
void Binary_Tree<T>∷postrav_Binary_Tree()
{ Btnode<T> *p;
p=BT;
postrav(p); //从根结点开始后序遍历
cout <<endl;
return;
}
template <class T>
static postrav(Btnode<T> *p)
{ if (p!=NULL)
 { postrav(p->lchild);//后序遍历左子树
 postrav(p->rchild);//后序遍历右子树
 cout <<p->d <<" "; //输出根结点值
 }
return 0;
}


//文件名L5_1.cpp
#include "Binary_Tree.h"
int main()
{ Binary_Tree<int> b;//建立一个二叉树对象b，数据域为整型
cout <<"输入各结点值(-1为结束符值):" <<endl;
b.creat_Binary_Tree(-1); //从键盘输入二叉树各结点值，以-1作为结束值
cout <<"前序序列:" <<endl;
b.pretrav_Binary_Tree();//前序遍历二叉树对象b
cout <<"中序序列:" <<endl;
b.intrav_Binary_Tree(); //中序遍历二叉树对象b
cout <<"后序序列:" <<endl;
b.postrav_Binary_Tree();//后序遍历二叉树对象b
return 0;
}


输入各结点值(-1为结束符值):
18 20 09 –1 –1 25 47 –1 –1 –1 36 –1 12 06 –1 –1 33 –1 -1
前序序列:
18 20 9 25 47 36 12 6 33
中序序列:
9 20 47 25 18 36 6 12 33
后序序列:
9 47 25 20 6 33 12 36 18


//定义中序线索二叉链表结点类型
template <class T>
struct TTnode
{ T d;//数据域
int lflag;//左标志域
int rflag;//左标志域
TTnode *lchild; //左指针域
TTnode *rchild; //右指针域
};


//文件名in_threaded_BT.h
#include <iostream>
using namespace std;
//定义中序线索二叉链表结点类型
template <class T>
struct TTnode
{ T d;//数据域
int lflag;//左标志域
int rflag;//左标志域
TTnode *lchild; //左指针域
TTnode *rchild; //右指针域
};
//中序线索二叉链表类
template <class T>//类模板，T为虚拟类型
class in_threaded_BT
{ private:
TTnode<T> *BT;//中序线索二叉链表根结点指针
public: //成员函数
in_threaded_BT() { BT=NULL; return; }//二叉链表初始化
void creat_Binary_Tree(T);//生成二叉链表
void creat_threaded_BT();//生成中序线索二叉链表
void intrav_threaded_BT();//遍历中序线索二叉链表
};

//生成二叉链表
template <class T>
void in_threaded_BT<T>∷creat_Binary_Tree(T end)
{ TTnode<T> *p;
T x;
cin >>x;//输入第一个结点值
if (x==end) return;//第一个值为结束符值
p=new TTnode<T>; //申请二叉链表结点
p->d=x; p->lchild=NULL; p->rchild=NULL;
p->lflag=0; p->rflag=0;
BT=p;
creat(p, 1, end);//输入左子结点值
creat(p, 2, end);//输入右子结点值
return;
}
template <class T>
static creat(TTnode<T> *p, int k, T end)
{ TTnode<T> *q;
T x;
cin >>x;//输入结点值
if (x!=end) //结点值为非结束符值
{ q=new TTnode<T>; //申请一个二叉链表结点
q->d=x; q->lchild=NULL; q->rchild=NULL;
q->lflag=0; q->rflag=0;
if (k==1) p->lchild=q;//链接到左子树
if (k==2) p->rchild=q;//链接到右子树
creat(q, 1, end); //输入左子结点值
creat(q, 2, end); //输入右子结点值
}
return 0;
}

//生成中序线索二叉链表
template <class T>
void in_threaded_BT<T>∷creat_threaded_BT()
{ TTnode<T> *p, *q=NULL;
p=BT;
in_threaded(p, &q);
 return;
}
template <class T>
static in_threaded(TTnode<T> *p, TTnode<T> **h)
{ if (p!=NULL)
 { in_threaded(p->lchild, h);
//若上次访问到的结点的右指针为空
//则将当前访问到的结点序号填入，并置右标志域为1
 if ((*h!=NULL)&&((*h)->rchild==NULL))
 { (*h)->rchild=p; (*h)->rflag=1; }
//若当前访问到的结点的左指针为空
//则将上次访问到的结点序号填入，并置左标志域为1
 if (p->lchild==NULL)
 { p->lchild=(*h); p->lflag=1; }
 *h=p;//记住当前访问到的结点
 in_threaded(p->rchild, h);
 }
return 0;
}

//遍历中序线索二叉链表
template <class T>
void in_threaded_BT<T>∷intrav_threaded_BT()
{ TTnode<T> *p;
if (BT==NULL) return;//二叉链表为空
p=BT;
while (p->lflag==0) p=p->lchild;//沿左链找到叶子结点
cout <<p->d <<" "; //输出中序序列中的第一个结点值
while (p->rchild!=NULL)//沿右链扫描后件
{ if (p->rflag==1)//
 p=p->rchild;
else //沿右子树的左链扫描
{ p=p->rchild;
while ((p->lflag==0)&&(p->lchild!=NULL)) p=p->lchild;
}
cout <<p->d <<" ";//输出中序序列中的结点值
}
cout <<endl;
return;
}


//文件名L5_2.cpp
#include "in_threaded_BT.h"
int main()
{ in_threaded_BT<int> b;//建立一个二叉树对象b，数据域为整型
cout <<"输入各结点值(-1作为结束符值):" <<endl;
b.creat_Binary_Tree(-1); //从键盘输入二叉树各结点值，以-1作为结束符值
b.creat_threaded_BT();//生成中序线索
cout <<"中序序列:" <<endl;
b.intrav_threaded_BT(); //遍历中序线索二叉树
return 0;
}


输入各结点值(-1为结束符值):
18 20 09 –1 –1 25 47 –1 –1 –1 36 –1 12 06 –1 –1 33 –1 -1
中序序列:
9 20 47 25 18 36 6 12 33


//文件名pre_threaded_BT.h
#include <iostream>
using namespace std;
//定义前序线索二叉链表结点类型
template <class T>
struct TTnode
{ T d;//数据域
int lflag;//左标志域
int rflag;//左标志域
TTnode *lchild; //左指针域
TTnode *rchild; //右指针域
};

//前序线索二叉链表类
template <class T>//类模板，T为虚拟类型
class pre_threaded_BT
{ private:
TTnode<T> *BT;//前序线索二叉链表根结点指针
public: //成员函数
pre_threaded_BT() { BT=NULL; return; }//二叉链表初始化
void creat_Binary_Tree(T);//生成二叉链表
void creat_threaded_BT();//生成前序线索二叉链表
void intrav_threaded_BT();//遍历前序线索二叉链表
};

//生成二叉链表
template <class T>
void pre_threaded_BT<T>∷creat_Binary_Tree(T end)
{ TTnode<T> *p;
T x;
cin >>x;//输入第一个结点值
if (x==end) return;//第一个值为结束符值
p=new TTnode<T>; //申请二叉链表结点
p->d=x; p->lchild=NULL; p->rchild=NULL;
p->lflag=0; p->rflag=0;
BT=p;
creat(p, 1, end);//输入左子结点值
creat(p, 2, end);//输入右子结点值
return;
}
template <class T>
static creat(TTnode<T> *p, int k, T end)
{ TTnode<T> *q;
T x;
cin >>x;//输入结点值
if (x!=end) //结点值为非结束符值
 { q=new TTnode<T>; //申请一个二叉链表结点
q->d=x; q->lchild=NULL; q->rchild=NULL;
q->lflag=0; q->rflag=0;
if (k==1) p->lchild=q;//链接到左子树
if (k==2) p->rchild=q;//链接到右子树
creat(q, 1, end); //输入左子结点值
creat(q, 2, end); //输入右子结点值
}
return 0;
}
//生成前序线索二叉链表
template <class T>
void pre_threaded_BT<T>∷creat_threaded_BT()
{ TTnode<T> *p, *q=NULL;
p=BT;
pre_threaded(p, &q);
return;
}
template <class T>
static pre_threaded(TTnode<T> *bt, TTnode<T> **h)
{ TTnode<T> *p, *q;
if (bt!=NULL)
 { p=bt->lchild; q=bt->rchild;
 //若当前访问到的结点的左指针为空
 //则将上次访问到的结点序号填入，并置左标志域为1
 if ((*h!=NULL)&&(p==NULL))
 { bt->lchild=*h; bt->lflag=1; }
 //若上次访问到的结点的右指针为空
 //则将当前访问到的结点序号填入，并置右标志域为1
 if ((*h!=NULL)&&((*h)->rchild==NULL))
 { (*h)->rchild=bt; (*h)->rflag=1; }
 *h=bt;//记住当前访问到的结点
 pre_threaded(p, h);
 pre_threaded(q, h);
 }
return 0;
}

//遍历前序线索二叉链表
template <class T>
void pre_threaded_BT<T>∷intrav_threaded_BT()
{ TTnode<T> *p;
if (BT==NULL) return;//二叉链表为空
cout <<BT->d <<" ";//输出根结点值
p=BT->lchild;//沿左子树
if (p==NULL) p=BT->rchild;//左子树空则沿右子树
while (p!=NULL)//子树不空
{ cout <<p->d <<" ";//输出当前结点值
while (p->lflag==0)//沿左链访问直到左标志非0
{ p=p->lchild;
cout <<p->d <<" "; //输出当前结点值
}
p=p->rchild;//取右指针
}
cout <<endl;
return;
}


//文件名L5_3.cpp
#include "pre_threaded_BT.h"
int main()
{ pre_threaded_BT<int> b;//建立一个二叉树对象b，数据域为整型
cout <<"输入各结点值(-1作为结束符值):" <<endl;
b.creat_Binary_Tree(-1); //从键盘输入二叉树各结点值，以-1作为结束符值
b.creat_threaded_BT();//生成前序线索
cout <<"前序序列:" <<endl;
b.intrav_threaded_BT(); //遍历前序线索二叉树
return 0;
}


输入各结点值(-1为结束符值):
18 20 09 –1 –1 25 47 –1 –1 –1 36 –1 12 06 –1 –1 33 –1 -1
前序序列:
18 20 9 25 47 36 12 6 33


//定义后序线索三叉链表结点类型
template <class T>
struct TTTnode
{ T d;//数据域
int lflag;//左标志域
int rflag;//左标志域
TTTnode *pre; //父指针域
TTTnode *lchild; //左指针域
TTTnode *rchild; //右指针域
};


//文件名pos_threaded_BT.h
#include <iostream>
using namespace std;
//定义后序线索三叉链表结点类型
template <class T>
struct TTTnode
{ T d;//数据域
int lflag;//左标志域
int rflag;//左标志域
TTTnode *pre; //父指针域
TTTnode *lchild; //左指针域
TTTnode *rchild; //右指针域
};
//后序线索三叉链表类
template <class T>//类模板，T为虚拟类型
class pos_threaded_BT
{ private:
TTTnode<T> *BT;//后序线索三叉链表根结点指针
public: //成员函数
pos_threaded_BT() { BT=NULL; return; }//三叉链表初始化
void creat_Binary_Tree(T);//生成三叉链表
void creat_threaded_BT();//生成后序线索三叉链表
void intrav_threaded_BT();//遍历后序线索三叉链表
};

//生成三叉链表
template <class T>
void pos_threaded_BT<T>∷creat_Binary_Tree(T end)
{ TTTnode<T> *p;
T x;
cin >>x;//输入第一个结点值
if (x==end) return;//第一个值为结束符值