关于树的初始化文档格式.docx
- 文档编号:5236622
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:17
- 大小:19.09KB
关于树的初始化文档格式.docx
《关于树的初始化文档格式.docx》由会员分享,可在线阅读,更多相关《关于树的初始化文档格式.docx(17页珍藏版)》请在冰点文库上搜索。
classT>
structPTreeNode
Tdata;
//结点的数据域
//父结点的指针
PTreeNode(Tval=-2,intpar=-2)//构造函数
{data=val;
parent=par;
};
////////////////////////////树的结点结构定义结束
//PTree类模板用父结点表示法实现的树类
classPTree
public:
PTreeNode<
T>
*NodeList;
//树的顺序存储的结点数组
intsize;
//当前树的结点的最后位置
intcurrent;
//当前结点的指针
intmaxSize;
//默认的最大数组空间
PTree(char*s,intn);
//构造函数,通过广义表描述字符串创建
~PTree()
//析构函数,释放结点数组的内存空间
{delete[]NodeList;
voidDisplay();
//显示当前树的存储结构的内容
intFindParent(inti)
//找出当前结点的父结点指针
{returnNodeList[i].parent;
intFindFirstChild(inti);
//找出当前结点i的长子结点
intFindNextSibling(inti);
//找出当前结点的相邻的兄弟结点
intNearestCommonAncestor(intp,intq);
//找p和q的最近公共祖先结点
intCountLeaf();
//计算当前树的叶子结点的个数
intDepth();
//求出当前树的深度
/////////////////////////////PTree类模板声明结束
//构造函数通过广义表描述字符串创建树
PTree<
:
PTree(char*s,intn)
//计算要开辟的内存空间的个数
maxSize=n>
defaultSize?
n:
defaultSize;
//为结点数组开辟内存空间,需要结点结构默认构造函数
NodeList=newPTreeNode<
[maxSize];
//初始化数据成员
current=0;
size=-1;
//标志
intflag=0;
//结点指针堆栈
LinkedStack<
int>
LS;
//用于存放栈顶的指针
inttop;
//通过描述字符串建立一棵树
inti=0;
while(s[i]!
='
#'
)
{
switch(s[i])
case'
('
//进入子树,把父结点的指针入栈
LS.Push(size);
flag=1;
break;
'
//表示是从栈顶获取的父结点指针
)'
//退栈
LS.Pop(top);
default:
//数组指针向后推进一格
size++;
//送入数据域
NodeList[size].data=s[i];
//如果是根结点,则父结点为-1
if(flag==0)
NodeList[size].parent=-1;
//如果是分支结点,从堆栈中获取父结点指针
elseif(flag==1)
LS.getTop(top);
NodeList[size].parent=top;
}
i++;
}
//////////////////////通过广义表描述字符串创建树
//Display()公有成员函数
voidPTree<
Display()
for(inti=0;
i<
=size;
i++)
cout<
<
"
NodeList[i].data<
"
NodeList[i].parent<
endl;
///////////////////////////Display()公有成员函数
//FindFirstChild()公有成员函数
//找出当前结点i的长子结点的指针,如果没有就返回-1
intPTree<
FindFirstChild(inti)
//因为结点的顺序是前序序列,所以如果有长子结点
//那肯定就在i结点的下个相邻结点
//如果该结点没有子结点
if(NodeList[i+1].parent!
=i)
return-1;
else
//否则下个结点就是其长子结点
returni+1;
////////////////////////FindFirstChild()函数结束
//FindNextSibling()公有成员函数
//找出当前结点i的下个兄弟结点,如果没有就返回-1
FindNextSibling(inti)
//寻找第一个和当前结点i有相同父结点的结点
for(intj=i+1;
j<
j++)
if(NodeList[j].parent==NodeList[i].parent)
returnj;
//没有找到
return-1;
///////////////////////FindNextSibling()函数结束
//NearestCommonAncestor()公有成员函数
//找结点p和结点q的最近公共祖先结点
NearestCommonAncestor(intp,intq)
//定义两个堆栈,存放p,q两个结点的所有祖先结点
S1,S2;
//保证p在前
if(p>
q)
intt;
t=p;
p=q;
q=t;
};
//寻找结点p和q的最近公共祖先结点
//首先找出p的所有祖先结点
while(p!
=-1)
//p指针向上指向其父结点
p=NodeList[p].parent;
//把每次的父结点指针压入队列Q1
S1.Push(p);
//再找出q的所有的祖先结点
cout<
while(q!
//q指指针向上指向其父结点
q=NodeList[q].parent;
//把每次的父结点压入队列Q2
S2.Push(q);
//从队列Q1和Q2头部开始找最先相同的结点指针
do
//分别从对头取两个指针
S1.Pop(p);
S2.Pop(q);
while(p==q&
&
!
S1.IsEmpty()&
S2.IsEmpty());
//最后得到的是两者的最近公共祖先
returnp;
/////////////////NearestCommonAncestor()函数结束
//CountLeaf()公有成员函数
//计算当前树中叶子结点的个数
//作于09年1.16
CountLeaf()
intp=0;
//计数器
intf=1;
//是否是叶子结点的标记变量
i++)
//遍历数组的所有结点
f=1;
for(intj=0;
if(NodeList[j].parent==i)
f=0;
//不是叶子结点
break;
if(f==1)
p++;
//是叶子结点
/////////////////////////////CountLeaf()函数结束
//Depth()公有成员函数
//求出当前二叉树的深度,算法思想:
从每个结点出发,
//向根结点迈进,计算每个结点的最大层次数就是深度
Depth()
intdepth=0;
//遍历结点数组里的所有结点
intp=i,count=1;
while(p!
=0)
//从结点i往根迈进
//求出结点i所在的层次
count++;
if(depth<
count)
//保留最大结点层次数
depth=count;
returndepth;
/////////////////////////////////Depth()函数结束
#endif
回复3楼geninsf009
你写的很复杂·
我不是刚学·
不过还是谢谢!
!
代码:
/*完成树的顺序存储结构(双亲数组法)实现。
完成如下功能:
(1)能进行初始化;
(2)输入任一结点,求其在数组中的存储位置
(3)输入一结点,求其双亲
(4)输入一结点,求其孩子
(5)输入一结点,求其度(选作)*/
//定义树变量:
psqtree
t1;
//输入树中结点个数:
cin>
>
t1.num;
//输入树中第i个结点的数据元素的值:
//cin>
t1.nodes[i].data
//输入第i个元素的双亲的下标
iostream.h"
#definemaxsize10
//数据元素的值
//双亲结点下标位置
//一个数据结点的类型
//结构体数组,每一个元素有两个成员,data,parent
//树中结点的个数
//树的顺序存储结构类型
voidcreatetree(psqtree
t1)
输入结点的个数:
;
//输入结点个数,初始化num
for(inti=1;
=t1.num;
t1.nodes[i].data;
t1.nodes[i].parent;
int
arraylocation(psqtree&
t1,elemtypee)//输入任一结点e,求其在数组中的存储位置i
inti=1;
while(t1.nodes[i].data!
=e)
returni;
voidgetparent(psqtree&
t1,elemtypee)//输入一结点,求其双亲
t1.nodes[t1.nodes[i].parent].data;
voidgetsons(psqtree&
t1,elemtypee)//输入一结点,求其孩子
for(intj=1;
if(t1.nodes[j].parent==i)
t1.nodes[j].data;
voidgetdu(psqtree&
intmax=0;
//结点子树的个数
inti=-1;
//结点的下标
while(i<
t1.num)
{
intnum=0;
for(intj=1;
if(t1.nodes[j].parent==i)
num++;
if(max<
num)
max=num;
i++;
max;
voiddislist(psqtree
//cout<
voidmain()
psqtreet1;
createtree(t1);
dislist(t1);
elemtypee;
输入结点为e的元素:
e;
数据的位置:
arraylocation(t1,e);
输入结点为e的(求双亲):
getparent(t1,e);
输入结点为e的(求孩子):
getsons(t1,e);
树的度为:
getdu(t1);
我做的:
#definemaxsize20
typedefchartsbnode;
typedefstruct
//双亲存储结构
//双亲结点下标
//一个结点结构
//孩子链存储结构
//树中结点的个数
//树的顺序存储结构类型
t1)
//能进行初始化;
inti;
for(i=1;
//依次输入元素的值,初始化数组nodes[]
输出第"
存储元素的值和下标:
voidgettree(psqtree&
t1,elemtypee)
//输入任一结点值,求其在数组中的存储位置
while(e!
=t1.nodes[i].data)
if(i>
无此结点!
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关于 初始化