数据结构-二叉树的遍历及应用

2024年2月7日发(作者：)

实验报告

课程名称：数据结构与算法

课程类型：必修

实验项目：树型结构及应用

实验题目：二叉树的遍历及应用

一、实验目的

1.通过对二叉树的各种操作更好理解树型结构及其应用；

2.了解各种二叉树的遍历算法；

3.理解递归和非递归的差别。

二、实验要求及实验环境

实验要求：

1．编写建立二叉树(大于10个结点) 的二叉链表存储结构（左右链

表示）的程序，并以适当的形式显示和保存二叉树；

2．采用二叉树的二叉链表存储结构，编写程序实现二叉树的先序

、中序和后序遍历的递归和非递归算法以及层序遍历算法，并以适当

的形式显示和保存二叉树及其相应的遍历序列；

3．给定一个二叉树， 编写算法完成下列应用:

（1）判断其是否为完全二叉树；

（2）求二叉树中任意两个结点的公共祖先。

实验环境：codeblocks/Dev-C++

三、设计思想（本程序中的用到的所有数据抽象数据性ADT的定义，主程序的流程图及各程序模块之间的调用关系）

1. 所用的抽象数据性ADT的定义

1）逻辑结构：

栈：是一种特殊形式的线性表，所有的插入和删除操作都在栈顶。

栈的置空操作：void makenull(stack* s)

判断栈是否为空：int empty(stack* s)

返回栈顶元素：btree* top(stack* s)

入栈操作：void push(btree* x, stack* s)

出栈操作：void pop(stack* s)

队列：是一种特殊形式的线性表，队尾入队，队首出队。

将队列置空：void makenull_q(queue* duilie)

在队列后面插入T：void enqueue_q(btree* T, queue* duilie)

判断队列是否为空：int empty_q(queue* duilie)

返回队列的第一个元素：btree* front_q(queue* duilie)

删除队列的第一个元素:void dequeue_q(queue* duilie)

2) 存储结构

定义了一个字符栈stack，一个队列queue，一个队列里面的节点node2，一个广义表数组char widechart[100]，一个存储树节点数据的数组char

store_ancestors[100]。字符栈stack里面存储了了一个指向栈顶的int top，一个储存树节点的数组btree* zifu[100]，一个标记数组int flag[100]。队列queue里面储存了一个指向队头的指针node2* front，指向队尾的指针node2*

rear。队列节点node2里面储存了一个树节点btree* word，一个指向下一个队列节点的指针struct node22* next。

为了判断树是否为完全二叉树。定义的存储树节点数据的数组char

store_ancestors[100]里面首先调用void bring_0(char a[])数组里全部储存‘（’，然后调用make_alltrees将所有树节点的信息储存在对应下标的数组位置处，然后调用int find_last(char a[])找到需要存入截止符’0’的位置，此时char store_ancestors[100]已在树的对应位置储存了相应节点的信息，为了判断是否为完全二叉树，只需判断最后一个节点的前面字符是否有‘（’即可，

若为’(’,是不完全二叉树。

为了求出两个节点的公共祖先，只需找到两个节点在数组char

store_ancestors[100]中的位置，然后不断对两个节点进行/2操作，下标相同的即为公共祖先。

2. 主程序流程图及各程序模块之间的调用关系

调用关系：在输入操作数1~11后，分别调用：

1：createbtree_pre()

2：pre_order1(t);

3：in_order1(t);

4：post_order1(t);

5：pre_order2(t);

6：in_order2(t);

7：post_order2(t)；

8：lever_order(t);

9：keep_inchart2(t);

print_inchart();

10：bring_0(store_ancestors);

make_alltrees(t,1);

p = find_last(store_ancestors);

shifou = judge_fulltree(t);

11.

bring_0(store_ancestors);

make_alltrees(t,1);

find_last(store_ancestors);

find_ancestors(store_ancestors, m, n)；

四、测试结果（要求程序运行截图）

1. 测试用例

不完全二叉树ABDH##I##E##CF#J##G##

完全二叉树ABDH##I##EM##P##CFU##J##G##

2. 测试结果

不完全二叉树：

完全二叉树：

五、经验体会与不足

经验体会：

1.在建树过程中，递归虽然较为容易理解，但却时间复杂性高；

2.必须明白栈和队列的基本操作，两者操作数的位置不同；

3.变量名尽量设置的容易理解，不然在调用时很容易不记得是什么作用。

不足：

没有使用多种方法求得公共祖先，用数组的方法求公共祖先的方式较为繁琐；

没有对代码进行优化，时间复杂性高，运行速度慢；

六、附录：源代码（带注释）

#include

#include

typedef struct node

{

struct node* lchild;

struct node* rchild;

char data;

}btree;

//定义树的节点

typedef struct

{

btree* zifu[100];

int flag[100];

int top;

}stack;

//定义一个字符栈

typedef struct node22

{

btree* word;

struct node22* next;

}node2;

typedef struct queue22

{

node2* front;

node2* rear;

}queue;

//定义一个队列

void makenull_q(queue* duilie)

{

}

//将队列置空

void enqueue_q(btree* T, queue* duilie)

{

}

//在队列后面插入T

int empty_q(queue* duilie)

{

}

//判断队列是否为空

if (duilie->front == duilie->rear)

else

return 0;

return 1;

node2* q;

q = (node2*)malloc(sizeof(node2));

q->word = T;

q->next = NULL;

duilie->rear->next = q;

duilie->rear = q;

duilie->front = (node2*)malloc(sizeof(node2));

duilie->front->next = NULL;

duilie->rear = duilie->front;

btree* front_q(queue* duilie)

{

}

//返回队列的第一个元素

void dequeue_q(queue* duilie)

{

}

//删除队列的第一个元素

void makenull(stack* s)

{

}

//将字符栈置空

int empty(stack* s)

s->top = -1;

node2* p;

p = (node2*)malloc(sizeof(node2));

if (duilie->rear == duilie->front)

{

}

p = duilie->front->next;

duilie->front->next = p->next;

if (p->next == NULL)

{

}

free(p);

duilie->rear = duilie->front;

printf("队列空n");

if (duilie->front->next)

return duilie->front->next->word;

{

}

//判断字符栈是否置空

void push(btree* x, stack* s)

{

}

//将字符x压入字符栈的栈顶

btree* top(stack* s)

{

}

//返回字符栈栈顶元素

void pop(stack* s)

{

if (s->top < 0)

{

}

printf("栈空n");

if (s->top == -1)

{

}

else

return s->zifu[s->top];

return NULL;

s->top = s->top + 1;

s->zifu[s->top] = x;

if (s->top < 0)

else

return 0;

return 1;

}

else

{

}

s->top = s->top - 1;

//删除字符栈栈顶的元素

char widechart[100];//定义广义表数组

int i; //定义全局变量指示广义表的元素

btree* createbtree_pre()

{

char ch;

btree* T;

ch = getchar();

if (ch == '#')

{

}

else

{

T = (btree*)malloc(sizeof(btree));

if (T == NULL)

{

}

else

{

T->data = ch;

T->lchild = createbtree_pre();

T->rchild = createbtree_pre();

printf("申请内存失败n");

T = NULL; //输入‘#’代表为空节点

}

}

}

return T;

//用先序方式建立二叉树

void keep_inchart1(btree* T)

{

}

if (T != NULL)

{

}

if (T->lchild == NULL && T->rchild == NULL)

{

}

else

{

}

widechart[i] = T->data;

i++;

widechart[i] = '(';

i++;

keep_inchart1(T->lchild);

widechart[i] = ',';

i++;

keep_inchart1(T->rchild);

widechart[i] = ')';

i++;

widechart[i] = T->data;

i++;

//按广义表方式储存树步骤1--递归建立除了两边括号的广义表

void keep_inchart2(btree* T)

{

}

//按广义表方式储存树步骤2--加上两边括号和'0'

void print_inchart()

{

}

//打印广义表

void pre_order1(btree* T)

{

if (T != NULL)

{

printf("%c", T->data);

int i;

printf("树按照广义表打印为: ");

for (i = 0; widechart[i] != '0'; i++)

{

}

printf("n");

printf("%c", widechart[i]);

btree* t = T;

i = 0;

widechart[i] = '(';

i++;

keep_inchart1(t);

widechart[i] = ')';

i++;

widechart[i] = '0';

}

}

pre_order1(T->lchild);

pre_order1(T->rchild);

//先序递归遍历

void in_order1(btree* T)

{

}

//中序递归遍历

void post_order1(btree* T)

{

}

//后序递归遍历

void pre_order2(btree* T)

{

stack* s;

s = (stack*)malloc(sizeof(stack));

if (T != NULL)

{

}

in_order1(T->lchild);

in_order1(T->rchild);

printf("%c", T->data);

if (T != NULL)

{

}

in_order1(T->lchild);

printf("%c", T->data);

in_order1(T->rchild);

}

makenull(s);

while (T != NULL || !empty(s))

{

}

while (T != NULL)

{

}

if (!empty(s))

{

}

T = top(s);

pop(s);

T = T->rchild;

printf("%c", T->data);

push(T, s);

T = T->lchild;

//先序非递归遍历

void in_order2(btree* T)

{

stack* s;

s = (stack*)malloc(sizeof(stack));

makenull(s);

while (T != NULL || !empty(s))

{

while (T != NULL)

{

push(T, s);

T = T->lchild;

}

}

}

if (!empty(s))

{

}

T = top(s);

pop(s);

printf("%c", T->data);

T = T->rchild;

//中序非递归遍历

void post_order2(btree* T)

{

stack* s;

s = (stack*)malloc(sizeof(stack));

makenull(s);

while (T != NULL || !empty(s))

{

while (T != NULL)

{

}

while (!empty(s) && s->flag[s->top] == 2)

{

}

printf("%c", top(s)->data);

s->top--;

push(T, s);

s->flag[s->top] = 1;

T = T->lchild;

}

if (!empty(s))

{

}

s->flag[s->top] = 2;

T = top(s)->rchild;

}

//后序非递归遍历

void lever_order(btree* T)

{

queue* duilie;

duilie = (queue*)malloc(sizeof(queue));//队列duilie初始化

makenull_q(duilie);

btree* q;

q = (btree*)malloc(sizeof(btree));

if (T == NULL)

{

}

enqueue_q(T, duilie);

while (!empty_q(duilie))

{

q = front_q(duilie);

printf("%c", q->data);

dequeue_q(duilie);

if (q->lchild != NULL)

{

enqueue_q(q->lchild, duilie);

return;

}

}

}

if (q->rchild != NULL)

{

}

enqueue_q(q->rchild, duilie);

//层序遍历算法

char store_ancestors[100]; //定义一个数组按照层序储存所有节点数据

int judge_fulltree()

{

int pp,ll=0;

for(pp=1;store_ancestors[pp]!='0';pp++)

{

if(store_ancestors[pp]=='(')

{

ll=1;

break;

}

}

if(ll==1)

return 0;

if(ll==0)

return 1;

}

//判断树是否为完全二叉树

void make_alltrees(btree* T,int j)

{

if (T != NULL)

}

{

}

store_ancestors[j] = T->data;

make_alltrees(T->lchild, 2 * j);

make_alltrees(T->rchild, 2 * j + 1);

//把所有节点数据存入数组store_ancestors1[100]中

int find_last(char a[])

{

}

//找到需要存入'0'的位置

void bring_0(char a[])

{

}

//让字符数组store_ancestors1[100]全部为'('

for (int q = 0; q < 100; q++)

{

}

a[q] = '(';

int last;

for (int q = 99; q >0; q--)

{

}

return last;

if (a[q] != '(')

{

}

last = q;

break;

char find_ancestors(char shu[], char a, char b)

{

int m, k = 0, j = 0, n, p;

char zuxian='0';

for (m = 1; shu[m] != '0'; m++) //先找到需要查找的节点a在数组中的位置

{

}

for (m = 1; shu[m] != '0'; m++) //先找到需要查找的节点b在数组中的位置

{

}

if (k == 0 || j == 0)

{

}

else

{

for (n = k / 2; n != 0;)

{

printf("没有找到需要查找的节点，没有公共祖先n");

return;

if (b == shu[m])

{

}

j = m;

break;

if (a == shu[m])

{

}

k = m;

break;

p = j;

for (p = j / 2; p != 0;)

{

}

n = n / 2;

if (shu[n] == shu[p])

{

}

p = p / 2;

zuxian = shu[n];

printf("%c ", zuxian);

}

}

//寻找两个节点的公共祖先

int main()

{

btree* t;

t = (btree*)malloc(sizeof(btree));

int c, shifou,p;

char m, n,o;

printf("**********************************************n");

printf("欢迎来到树的操作系统n");

printf("1.按照先序方式建立二叉树(输入#代表输入为空)n");

printf("2.按照先序递归方式遍历二叉树n");

printf("3.按照中序递归方式遍历二叉树n");

printf("4.按照后序递归方式遍历二叉树n");

printf("5.按照先序非递归方式遍历二叉树n");

}

return zuxian;

printf("6.按照中序非递归方式遍历二叉树n");

printf("7.按照后序非递归方式遍历二叉树n");

printf("8.按照层序方式遍历二叉树n");

printf("9.按照广义表方式打印二叉树n");

printf("10.判断树是否为完全二叉树n");

printf("11.求树任意两个节点的公共祖先n");

printf("**********************************************n");

while (1)

{

printf("请选择你需要执行的操作：");

scanf("%d", &c);

getchar();

switch (c)

{

case 1:

printf("请按照先序方式输入你的节点(输入#代表输入为空)：");

t = createbtree_pre();

printf("n");

break;

case 2:

printf("先序排列为：");

pre_order1(t);

printf("n");

printf("n");

break;

case 3:

printf("中序排列为：");

in_order1(t);

printf("n");

printf("n");

break;

case 4:

printf("后序排列为：");

post_order1(t);

printf("n");

printf("n");

break;

case 5:

printf("先序排列为：");

pre_order2(t);

printf("n");

printf("n");

break;

case 6:

printf("中序排列为：");

in_order2(t);

printf("n");

printf("n");

break;

case 7:

printf("后序排列为：");

post_order2(t);

printf("n");

printf("n");

break;

case 8:

printf("层序排列为：");

lever_order(t);

printf("n");

printf("n");

break;

case 9:

keep_inchart2(t);

print_inchart();

printf("n");

break;

case 10:

bring_0(store_ancestors);

make_alltrees(t,1);

p = find_last(store_ancestors);

store_ancestors[p + 1] = '0';

shifou = judge_fulltree();

if (shifou == 1)

else

printf("树不是完全二叉树n");

printf("树是完全二叉树n");

printf("n");

break;

case 11:

bring_0(store_ancestors);

make_alltrees(t,1);

p = find_last(store_ancestors);

store_ancestors[p + 1] = '0';

printf("请输入你需要求的两个节点: ");

scanf(" %c %c", &m, &n);

printf("公共祖先为：");

find_ancestors(store_ancestors, m, n);

}

}

printf("n");

printf("n");

break;

default:

}

printf("请输入正确信息n");

printf("n");

printf("n");

break;

return 0;