二叉树综合算法分析Word格式.docx
- 文档编号:4748187
- 上传时间:2023-05-04
- 格式:DOCX
- 页数:10
- 大小:45.69KB
二叉树综合算法分析Word格式.docx
《二叉树综合算法分析Word格式.docx》由会员分享,可在线阅读,更多相关《二叉树综合算法分析Word格式.docx(10页珍藏版)》请在冰点文库上搜索。
专业:
信息与计算科学1001班
一.二叉树综合算法分析
1.设计要求:
二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现。
要求:
遍历的内容应是千姿百态的。
2.需求分析
输入树形结构的内容,建立一棵二叉树:
(1)二叉树的链表结构;
(2)二叉树的链栈结构;
(3)二叉树的非递归(栈)层次序遍历,输出结果。
(4)递归的排序方法:
1.前序2.中序3.后序,输出结果;
(5)非递归的排序方法:
1.前序2.中序3.后序,输出结果。
二.二叉树操作
1.数据结构
typedefstructBiTNode
{
ElemTypedata;
structBiTNode*lchild,*rchild;
}BiTNode;
/*栈的定义及基本操作*/
#defineMaxSize100
typedefBiTNode*SElemType;
/*栈和队列的结点类型,用于存放树结点*/
typedefstruct
SElemTypeelem[MaxSize];
inttop;
}SqStack;
2.模块划分
a.树的操作
建立二叉树tree*Creatbitree()
先根序列建立二叉树BiTNode*crt_bt_pre()
求叶子数intleaf(BiTNode*bt)
求树的高度inthigh(BiTNode*bt)
b.栈运算
初始化栈voidInitStack(SqStack*pS)
进栈intPush(SqStack*pS,SElemTypee)
出栈voidpop(stack**top,tree**T)(栈内元素赋值给树结点)c.队列运算
初始化队列voidInitQueue(SqQueue*pQ)
进队intEnQueue(SqQueue*pQ,SElemTypee)
出队intDeQueue(SqQueue*pQ,SElemType*pe)
用队列实现层次遍历voidlev_traverse(BiTNode*bt)
d.递归遍历函数
voidPreOrder(tree*b1)//前序遍历
voidMidOrder(tree*b2)//中序遍历
voidLastOrder(tree*b3//后序遍历
三.问题实现
1.创建二叉树的实现
以前序遍历的方式输入二叉树的内容,以"
"
作为二叉树的空结点,如:
Abcdefg构造一棵如下二叉树:
2.在链接栈中实现二叉树的入栈和出栈,以及获取栈顶元素
intPush(SqStack*pS,SElemTypee)/*进栈*/
if(pS->
top==MaxSize-1)/*栈满*/
return0;
pS->
elem[pS->
top]=e;
top=pS->
top+1;
return1;
}
intPop(SqStack*pS,SElemType*pe)/*出栈*/
top==0)/*栈空*/
top=pS->
top-1;
*pe=pS->
top];
此过程是从二叉树的链表结构向链接栈结构的转换,可运用到二叉树非递归遍历中。
3.层次遍历打印二叉树
voidinorder_fdg(BiTNode*bt)
BiTNode*p;
SqStacks;
InitStack(&
s);
p=bt;
do
{while(p!
=NULL)
{Push(&
s,p);
p=p->
lchild;
}
if(s.top!
=0)
{Pop(&
s,&
p);
printf("
%c"
p->
data);
rchild;
while(s.top!
=0||p!
=NULL);
这是中序遍历的层次打印树结点,采用链接崭的迭代方法,而非从根结点的层次序遍历。
4.递归方法的二叉树遍历操作
/*先根遍历*/
voidpreorder(BiTNode*bt)
{if(bt!
{printf("
bt->
preorder(bt->
lchild);
rchild);
/*中根遍历*/
voidinorder(BiTNode*bt)
{inorder(bt->
inorder(bt->
/*后根遍历*/
voidpostorder(BiTNode*bt)
{postorder(bt->
postorder(bt->
这三个函数实现了二叉树的递归遍历方法。
前序思想是先根后左孩子再右孩子,中序遍历思想是先左孩子后根再右孩子,后序是先左孩子后孩子右再根。
6.非递归方法的二叉树遍历操作
/*用队列实现层次遍历*/
voidlev_traverse(BiTNode*bt)
SqQueueq;
InitQueue(&
q);
EnQueue(&
q,p);
while(!
(q.rear==q.front))
{/*当队列不空*/
DeQueue(&
q,&
if(p->
lchild!
q,p->
rchild!
这两个函数直接调用了链接栈的方法,而不必另外为栈开辟存储空间,有效节省了资源,并且更为简便地实现了非递归的遍历方法。
7.主函数
voidmain()
BiTNode*T;
/*按先序列建树,用空格表示空子树*/
请输入如这样的形式:
'
abcdegf'
\n"
);
/*T=crt_bt_pre();
*/
crt_bt_pre_2(&
T);
\n\n先根序列建立二叉树:
preorder(T);
\n前序是:
inorder(T);
\n中序是:
postorder(T);
\n后序是:
inorder_fdg(T);
\n中序遍历:
lev_traverse(T);
\n叶子数目:
%d"
leaf(T));
\n树的高度:
%d\n"
high(T));
freetree(T);
getchar();
四.数据显示:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 二叉 综合 算法 分析