数计学院数据结构二叉树遍历课程设计

目录

一.问题描述..................................................................................................................... 1

（1）题目：............................................................................................................. 1

（2）题目内容：..................................................................................................... 1

二.基本要求 .................................................................................................................... 1

三.工具/准备工作 .......................................................................................................... 1

四.分析与实现................................................................................................................. 2

（1）分析：............................................................................................................. 2

（2）核心算法代码：............................................................................................. 2

①构建二叉树：................................................................................................ 2

②二叉树的递归先序遍历：............................................................................ 3

③二叉树的递归中序遍历：............................................................................ 4

④二叉树的递归后续遍历：............................................................................ 4

⑤二叉树的节点查找：.................................................................................... 5

⑥main函数部分：........................................................................................... 6

⑦二叉树的非递归先序遍历：........................................................................ 9

⑧二叉树的非递归中序遍历：...................................................................... 10

⑨二叉树的非递归后序遍历：.......................................................................11

五.测试与结论............................................................................................................... 13

六.课程设计总结........................................................................................................... 16

一.问题描述

（1）题目：二叉树的建立和后序遍历的演示。

（2）题目内容：利用单链表构建二叉树的链式存储，并能输入数据，然后分别用递归与非递归算法实现二叉树的中序遍历与后序遍历。

二.基本要求

（1）建立完整的二叉链表。

基本要求： （2）程序可以输入数据。

（3）递归中序与后续遍历。

（4）非递归后续遍历

（1）添加了菜单选择功能

扩展功能 ： （2）添加了查找功能

（3）补全了三种遍历（递归与非递归）

三.工具/准备工作

(1)二叉树的链式存储结构

（2）二叉树的基本运算

（3）二叉树的3种递归遍历

（4）二叉树的3种非递归遍历

（5）二叉树的节点查找

系统：Window 7

环境/

软件：c-free

四.分析与实现

（1）分析：运用链来指示元素间的逻辑关系，表示一颗二叉树，具有链式存储的特点。另外，结合递归与非递归的思想算法，实现二叉树的三种遍历。

（2）核心算法代码：

①构建二叉树：

void create_tree(int x)

{

bt s,p;

int flag=0;

s=(treenode*)malloc(sizeof(treenode)); s->data=x; s->left=NULL; s->right=NULL; if(root==NULL) { root=s; } else { p=root; while(!flag) { if(x>p->data) { if(p->left==NULL)

{

p->left=s;

flag=1;

}

else

p=p->left;

}

else

{

if(p->right==NULL)

{

p->right=s;

flag=1;

}

else

p=p->right;

}

}

}

}

②二叉树的递归先序遍历：

void xianxu(bt q)

{

if(q!=NULL)

{

printf("%4d",q->data);

xianxu(q->left);

xianxu(q->right);

}

}

③二叉树的递归中序遍历：

void zhongxu(bt q)

{

if(q!=NULL)

{

zhongxu(q->left);

printf("%4d",q->data);

zhongxu(q->right);

}

}

④二叉树的递归后续遍历：

void houxu(bt q)

{

if(q!=NULL)

{

houxu(q->left);

houxu(q->right);

printf("%4d",q->data);

}

}

⑤二叉树的节点查找：

bt search(bt a,int x)

{

bt p=NULL;

int i=1;

if(a)

{

if(a->data==x)

return a;

if(a->left)

{

p=search(a->left,x);

i=i++;

}

if(p)

{

return p;

}

if(a->right)

{

p=search(a->right,x);

i=i++;

}

} } if(p) { return p; } return NULL;

⑥main函数部分：

int main(void)

{

int i,k,x,a,v;

bt d;

root=NULL;

printf("\n\t\t*************************************");

printf("\n\t\t* 计科本113苏加俊出品 *"); printf("\n\t\t* 二叉树链式存储 *");

printf("\n\t\t*************************************");

printf("\n\t\t* 1. 递归先序遍历 *");

printf("\n\t\t* 2. 递归中序遍历 *");

printf("\n\t\t* 3. 递归后序遍历 *");

printf("\n\t\t* 4. 查找数据节点 *");

printf("\n\t\t* 5. 退出 *");

printf("\n\t\t*************************************"); printf("\n\n"); printf("请输入数据:\n"); for(i=0;i<5;i++)

{

scanf("%d",&k);

create_tree(k);

}

L=root;

again:printf("请选择功能：\t");

scanf("%d",&v);

switch(v)< …… 此处隐藏：3243字，全部文档内容请下载后查看。喜欢就下载吧 ……