二叉树的基本操作附源码

素颜马尾好姑娘i 2022-05-21 09:54 174阅读 0赞

**一、 目的**

1．掌握二叉树的存储实现。

2．掌握二叉树的遍历思想。

3．掌握二叉树的常见算法的程序实现。

**二、内容**

1、内容

a)      从键盘上输入数据，建立二叉链表。

b)      前序遍历、中序遍历、后序遍历二叉树：递归算法。

c)      前序遍历、中序遍历、后序遍历二叉树：非递归算法。

d)      借助队列实现二叉树的层次遍历。

e)      在主函数中设计一个简单的菜单，分别调试上述算法。

f)       \*综合训练：

家族关系查询系统：建立家族关系数据库，可以实现家族成员的添加，可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。

2、主要数据类型与变量

1．类型定义 //二叉链表存储

\#define TElemType char  //元素类型

typedef struct BiTNode\{

TElemType data;

struct BiTNode \*lchild, \*rchild;

\} BiTNode, \*BiTree;

3、算法思想描述

定义节点，首先将左右孩子的指针域置空，再有需要的时候讲左右孩子指向孩子节点。递归遍历注意输出语句的位置，层次遍历使用队列，能够很简单的输出所有的节点数据，非递归中注意指针指向的位置，自己不能够混乱。

**三、系统测试**

1、测试方案

**本次自己没能够通过图形化界面将所有的步骤一一的展示出来，仅仅是将输入语句写出，然后自己建立好了二叉树，点击便直接将先序，中序，后序的递归和非递归遍历，以及层次遍历的所有结果输出，这样更加的直观，可以一下将全部的答案看到，然后去判断正误。**

2、测试结果

1.本次采用的是直接输出结果的图形化界面，

输入的数据为abc  de g  f   ,以a开头，cd之间有两个空格，eg之间有两个空格，gf之间有一个空格，f之后又三个空格。

在这里面输入其他的字符串可能不会输出结果，原因可能是输入的字符串不能够形成一个二叉树，所以不能够直接输出结果。

**附：程序源代码**

**BinTree.cpp**

\#include "BiTree.h"

\#include "SqStack.h"

\#include "LinkQueue.h"

Status CreateBiTree( BiTree &T ) \{

char ch;

scanf ("%c", &ch );

if ( ch ==' ') T = NULL;

else\{

if ( !( T = ( BiTNode \* ) malloc (sizeof(BiTNode ) ) ) )

exit( OVERFLOW );

T->data = ch;

CreateBiTree( T->lchild );

CreateBiTree( T->rchild );

return OK;

/\*先序遍历二叉树\*/

void PreOrderTraverse(BiTree T)\{

if ( T )\{

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

PreOrderTraverse( T->lchild);

PreOrderTraverse( T->rchild);

/\*中序遍历二叉树\*/

void InOrderTraverse(BiTree T)\{

if ( T )\{

InOrderTraverse(T->lchild);

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

InOrderTraverse ( T->rchild);

/\*后序遍历二叉树\*/

void PostOrderTraverse(BiTree T)\{

if ( T ) \{

PostOrderTraverse ( T->lchild);

PostOrderTraverse ( T->rchild);

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

/\*按层次遍历二叉树\*/

void LevelOrderTraversal( BiTree  T)

LinkQueue Q; BiTree p;

if ( !T ) return;    /\* 若是空树则直接返回 \*/

InitQueue( Q );     /\*创建并初始化队列Q\*/

EnQueue( Q, T );

while ( !QueueEmpty( Q ) ) \{

DeQueue( Q, p );

printf("%c ", p->data); /\*访问取出队列的结点\*/

if ( p->lchild ) EnQueue( Q, p->lchild );  /\*左孩子入队列\*/

if ( p->rchild ) EnQueue( Q, p->rchild ); /\*右孩子入队列\*/

/\*先序非递归遍历二叉树\*/

void PreTraverse(BiTree T)

SqStack s;

BiTree p;

p= T;

InitStack(s);

if(!T) return;

Push(s,T);

while(!StackEmpty(s))\{

Pop(s,p);

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

if(p->rchild) Push(s,p->rchild);

if(p->lchild) Push(s,p->lchild);

printf("\\n");

/\*中序非递归遍历二叉树\*/

void InTraverse(BiTree T)\{

SqStack s;

BiTree p = T;

InitStack(s);

if(!T) return;

while(p || !StackEmpty(s))\{

if(p)\{

Push(s,p);

p = p->lchild;

\}else\{

Pop(s,p);

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

p = p->rchild;

printf("\\n");

/\*后序非递归遍历二叉树\*/

void PostTraverse(BiTree T)

SqStack s;

BiTree pre=NULL,p;

if(!T) return ;

InitStack(s);

Push(s,T);

while(!StackEmpty(s))\{

GetTop(s,p);

if((p->lchild == NULL && p->rchild == NULL)||

(pre != NULL &&(p->lchild == pre || p->rchild == pre)))\{

Pop(s,p);

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

pre = p;

\}else\{

if(p->rchild) Push(s,p->rchild);

if(p->lchild) Push(s,p->lchild);

printf("\\n");

**main.cpp**

\#include "BiTree.h"

int main()

BiTree BT;

printf("构建二叉树:\\n");

printf("请输入一串字符:\\n");

CreateBiTree(BT);

printf("先序递归遍历序列：\\n");

PreOrderTraverse(BT);

printf("\\n");

printf("中序递归遍历序列：\\n");

InOrderTraverse(BT);

printf("\\n");

printf("后序递归遍历序列：\\n");

PostOrderTraverse(BT);

printf("\\n");

printf("按层次遍历序列：\\n");

LevelOrderTraversal(BT);

printf("\\n");

printf("先序非递归遍历序列：\\n");

PreTraverse(BT);

printf("中序非递归遍历序列：\\n");

InTraverse(BT);

printf("后序非递归遍历序列：\\n");

PostTraverse(BT);

return 0;

** **

二叉树的基本操作附源码

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关二叉树的基本操作（附代码）

相关二叉树的基本操作

相关二叉排序树（二叉查找树）的基本操作

相关二叉树的基本操作

相关二叉树的基本操作方式

相关搜索二叉树的基本操作

相关二叉树的基本操作

相关第九天-------二叉排序树附源码

相关二叉树的基本操作附源码

相关二叉树的基本操作