手机版
你好,游客 登录 注册
背景:
阅读新闻

二叉树数据结构的实现

[日期:2017-02-27] 来源:Linux社区  作者:11838641 [字体: ]

(1)任务为:抽象数据类型的实现;本次任务用了devcpp程序作为开发软件,编写语言为C语言

(2)二叉树是一种递归数据结构。二叉树是含有n(n>=0)个节点的有限集合。当n=0时称为空二叉树。在非空二叉树中:(1)有且仅有一个称为根的节点(2)当n>1时,其余节点划分为两个互不相交的子集L和R,其中L和R也是一课二叉树,分别称为左子树和右子树,且其次序不能颠倒。

二叉树的基本操作有:

1、Status InitBiTree(BiTree &T)即创建一棵空二叉树

2、BiTree MakeBiTree(TElemType e,BiTree L,BiTree R)即创建一棵二叉树T,其中根节点的值为e,L和R分别作为左子树和右子树

3、void DestoryBiTree(BiTree &T)即销毁二叉树

4、Status BiTreeEmpty(BiTree &T)二叉树判空,若为空返回TRUE,否则FALSE

5、Status BreakBitree(BiTree &T,BiTree &L,BiTree &R)将一棵二叉树T分解成根、左子树和右子树三个部分

6、Status ReplaceLeft(BiTree &T,BiTree <)替换左子树。若T非空,则用LT替换T的左子树,并用LT返回T的原有左子树

7、Status ReplaceRight(BiTree &T,BiTree &RT)替换右子树。若T非空,则用RT替换T的左子树,并用RT返回T的原有左子树

8、Status CutLeft(BiTree &T,BiTree <)剪除左子树,若T非空,则剪除T的左子树,并用LT返回

9、Status CutRight(BiTree &T,BiTree &RT)剪除右子树,若T非空,则剪除T的右子树,并用RT返回

10、Status PreTraverse(BiTree T,Status(*visit)(TElemType e))先序遍历

11、Status MidTraverse(BiTree T,Status(*visit)(TElemType e))中序遍历

12、void AfterTraverse(BiTree T)后序遍历

13、int BiTreeDepth(BiTree T)求树的深度

14、BiTree CreatBT ()建立二叉树

(3)所选的存储结构为链式存储,其中包含一个数据域和两个左右孩子指针。各基本操作的实现:

1、Status InitBiTree(BiTree &T)操作中通过T=(BiTree)malloc(sizeof(BiTNode));给树开辟一块空间实现创建一棵空二叉树

2、BiTree MakeBiTree(TElemType e,BiTree L,BiTree R)中,通过t->data = e;t->lchild = L;t->rchild = R;实现令L、R成为t的左右子树

3、void DestoryBiTree(BiTree &T)则直接通过free(T);释放内存空间来达到销毁树

4、Status BiTreeEmpty(BiTree &T)中如果NULL==T,即树中没有内容,则判断为空树

5、Status BreakBitree(BiTree &T,BiTree &L,BiTree &R)通过        L = T->lchild;R = T->rchild;来将结构体T所指向的左右子树分别赋给L和R树。

6、Status ReplaceLeft(BiTree &T,BiTree <)通过t = T->lchild;T->lchild = LT;LT = t使T的左子树变为指向LT,即LT成为T的左子树,从而达到替换作用

7、Status ReplaceRight(BiTree &T,BiTree &RT)原理与上一步相同

8、Status CutLeft(BiTree &T,BiTree <)通过LT = T->lchild;T->lchild = NULL使LT的存储位置变为T->lchild,而T->lchild 的存储位置变为NULL

9、Status CutRight(BiTree &T,BiTree &RT)原理与上一步相同

10、Status PreTraverse(BiTree T,Status(*visit)(TElemType e))先序遍历通过递归的方法,每进入一层递归 先visit(T->data)即先访问根节点,再进入PreTraverse(T->lchild,visit)左子树的一层递归访问,再进入PreTraverse(T->rchild,visit)右子树

11、Status MidTraverse(BiTree T,Status(*visit)(TElemType e))中序遍历,先进入左子树的最底层MidTraverse(T->lchild,visit)访问,接着回访问根节点visit(T->data),再进入右子树最底层MidTraverse(T->rchild,visit)访问,再逐层上升访问。

12、void AfterTraverse(BiTree T)后序遍历则先进入左子树最底层 AfterTraverse (T->lchild);访问,再进入右子树最底层AfterTraverse (T->rchild);访问,然后再访问根节点,再逐层上升访问。

15、int BiTreeDepth(BiTree T)求树的深度,根节点独占一层,所以二叉树的深度为其左右子树深度的最大值加1,判断到达最底层时NULL == T就返回上一层,逐层上升加1

16、BiTree CreatBT ()建立二叉树。用户先输入根节点信息,此时如果用户输入0,则令t=NULL,即不存储任何信息,当输入非0时,链表中t->data的信息域即存储为该用户输入的信息,接着用户输入左子树信息,进入一层递归,此时该信息为t->lchild信息域的内容,当输入为0则返回上一层,问右子树的信息,此时该信息为t->rchild信息域的内容,以此类推。

以下为源码:

#include <stdio.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

typedef int TElemType;

typedef bool Status;

typedef struct BiTNode{

TElemType data;

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

 

Status InitBiTree(BiTree &T){

T = (BiTree)malloc(sizeof(BiTNode));

if(!T) return ERROR;

return OK;

}

 

BiTree MakeBiTree(TElemType e,BiTree L,BiTree R){

BiTree t;

t = (BiTree)malloc(sizeof(BiTNode));

if(NULL == t) return NULL;

t->data = e;

t->lchild = L;

t->rchild = R;

return t;

}

 

void DestoryBiTree(BiTree &T){

free(T);

}

 

Status BiTreeEmpty(BiTree &T){

if(NULL == T) return TRUE;

else return FALSE;

}

 

Status BreakBitree(BiTree &T,BiTree &L,BiTree &R){

if(NULL == T) return FALSE;

L = T->lchild;

R = T->rchild;

T->lchild = NULL;

T->rchild = NULL;

return TRUE;

}

 

Status ReplaceLeft(BiTree &T,BiTree <){

if(NULL == T) return FALSE;

BiTree t;

t = T->lchild;

T->lchild = LT;

LT = t;

return TRUE;

}

 

Status ReplaceRight(BiTree &T,BiTree &RT){

if(NULL == T) return FALSE;

BiTree t;

t = T->rchild;

T->rchild = RT;

RT = t;

return TRUE;

}

Status CutLeft(BiTree &T,BiTree <){

if(NULL == T) {

LT = NULL;

return FALSE;

}

LT = T->lchild;

T->lchild = NULL;

return TRUE;

}

Status CutRight(BiTree &T,BiTree &RT){

if(NULL == T) {

RT = NULL;

return FALSE;

}

RT = T->lchild;

T->lchild = NULL;

return TRUE;

}

//先序遍历

Status PreTraverse(BiTree T,Status(*visit)(TElemType e)){

if(NULL == T) return OK;

if(ERROR == visit(T->data)) return ERROR;

if(ERROR == PreTraverse(T->lchild,visit))

return ERROR;

return PreTraverse(T->rchild,visit);

}

//中序遍历

Status MidTraverse(BiTree T,Status(*visit)(TElemType e)){

if(NULL == T) return OK;

if(ERROR == MidTraverse(T->lchild,visit))

return ERROR;

if(ERROR == visit(T->data))

return ERROR;

return MidTraverse(T->rchild,visit);

}

//后序遍历

void AfterTraverse(BiTree T){

if (T == NULL)

    return ;

  else

    {

      AfterTraverse (T->lchild);

      AfterTraverse (T->rchild);

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

    }

}

Status visit(TElemType e) {

printf("%d",e);

}

//求深度

int BiTreeDepth(BiTree T){

int dL = 0,dR = 0;

if(NULL == T) return 0;

else{

dL = BiTreeDepth(T->lchild);

dR = BiTreeDepth(T->rchild);

return 1+(dL > dR ? dL : dR);

}

}

//建立二叉树

BiTree CreatBT ()

{

  BiTree t;

  int x;

  scanf ("%d", &x);

  if (x == 0)

    {

      t = NULL;

    }

  else

    {

      t = (BiTree) malloc (sizeof (BiTNode));

      t->data = x;

      printf ("\n请输入%d结点的左子结点:", t->data);

      t->lchild = CreatBT ();

      printf ("\n请输入%d结点的右子结点:", t->data);

      t->rchild = CreatBT ();

    }

  return t;

}

int main(){

BiTree T;

int i,k;

    InitBiTree(T);

    printf("正在为您建立二叉树,请以输入'0'表示值为空\n");

    printf ("请输入根结点:\n");

    //建立一颗二叉树

T = CreatBT ();

//对用户输入的树判空

i = BiTreeEmpty(T);

if(1 == i){

printf ("该树为空树\n");

}else{

    printf(" ----------先序遍历二叉树 ----------\n");

PreTraverse(T,visit);

printf("\n ----------中序遍历二叉树 ----------\n");

MidTraverse(T,visit);

printf("\n ----------后序遍历二叉树 ----------\n");

AfterTraverse(T);

printf("\n ----------二叉树的深度----------\n");

k = BiTreeDepth(T);

printf("%d",k);

BiTree T1,T2;

T1 = T;

printf("\n ----------为您剪掉左子树----------\n");

CutLeft(T1,T2);

printf("\n ----------剪掉左子树的先序遍历二叉树 ----------\n");

PreTraverse(T1,visit);

printf("\n ----------为您将左子树接回----------\n");

ReplaceLeft(T1,T2);

printf("\n ----------接回左子树的先序遍历二叉树 ----------\n");

PreTraverse(T1,visit);

printf("\n ----------为您拆散这课二叉树 ----------\n");

BreakBitree(T,T1,T2);

printf("\n ----------拆散后根节点的先序遍历二叉树 ----------\n");

PreTraverse(T,visit);

printf("\n ----------拆散后左子树的先序遍历二叉树 ----------\n");

PreTraverse(T1,visit);

printf("\n ----------拆散后右子树的先序遍历二叉树 ----------\n");

PreTraverse(T2,visit);

printf("\n ----------为您重新组装这课二叉树 ----------\n");

BiTree t = MakeBiTree(T->data,T1,T2);

printf("\n ----------组装后的先序遍历二叉树 ----------\n");

PreTraverse(t,visit);

DestoryBiTree(T);

}

while(1){//设置一个死循环,为了不让程序结束而关闭窗口

 


}

return 0;

}

测试数据:

预期子树为:

测试结果为:

本文永久更新链接地址http://www.linuxidc.com/Linux/2017-02/141123.htm 

linux
相关资讯       二叉树 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款