c语言 二叉排序树_c语言 二分法排序_二叉树遍历算法c语言

pubuse.h文件

#include

#include

#include /* malloc()等*/

#include /* INT_MAX 等*/

#include /* EOF(=^Z 或F6),NULL /

#include / atoi() /

#include / eof() /

#include / floor(),ceil(),abs() /

#include / exit() /

/ 函数结果状态代码*/

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

typedef int Status; /* Status 是变量的类别,其值是数组结果状态代码，如OK 等*/

typedef int Boolean; /* Boolean 是布尔类型,其值是TRUE 或FALSE */

typedef int TElemType;

BinTreeDef.h文件

typedef struct BiTNode

{

TElemType data;

struct BiTNode lchild,*rchild; / вСср╨╒всж╦уК*/

}BiTNode,*BiTree;

BinTreeAlgo.h文件

Status InitBiTree(BiTree &T)

{ /* 操作结果: 构造空二叉树T */

T=NULL;

return OK;

}

void DestroyBiTree(BiTree &T)

{ /* 初始条件: 二叉树T 存在。操作结果: 销毁二叉树T /

if(T) / 非空树*/

{

if(T->lchild) /* 有左孩子*/

DestroyBiTree(T->lchild); /* 销毁左孩子子树*/

if(T->rchild) /* 有右孩子*/

DestroyBiTree(T->rchild); /* 销毁右小孩子树*/

free(T); /* 释放根节点*/

T=NULL; /* 空指针赋0 */

}

}

#define ClearBiTree DestroyBiTree

void CreateBiTree(BiTree &T)

{ /* 按先序顺序输入二叉树中节点的值，构造二叉链表表示的二叉树T。变量Nil 表示空（子）树。*/

TElemType ch;

scanf("%d",&ch);

// printf("%d", ch);

if(ch==Nil) /* 空*/

T=NULL;

else

{

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

if(!T)

exit(OVERFLOW);

T->data=ch; /* 生成根节点*/

CreateBiTree(T->lchild); /* 构造左子树*/

CreateBiTree(T->rchild); /* 构造右子树*/

}

}

Status BiTreeEmpty(BiTree T)

{ /* 初始条件: 二叉树T 存在*/

/* 操作结果: 若T 为空二叉树,则返回TRUE,否则FALSE */

if(T)

return FALSE;

else

return TRUE;

}

int BiTreeDepth(BiTree T)

{ /* 初始条件: 二叉树T 存在。操作结果: 返回T 的深度*/

int i,j;

if(!T)

return 0;

if(T->lchild)

i=BiTreeDepth(T->lchild);

else

i=0;

if(T->rchild)

j=BiTreeDepth(T->rchild);

else

j=0;

return i>j?i+1:j+1;

}

TElemType Root(BiTree T)

{ /* 初始条件: 二叉树T 存在。操作结果: 返回T 的根*/

if(BiTreeEmpty(T))

return Nil;

else

return T->data;

}

void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType))

{ /* 初始条件: 二叉树T 存在,Visit 是对节点操作的应用变量。*/

/* 操作结果: 先序链表遍历T,对每个节点调用函数Visit 一次且仅一次*/

if(T) /* T 不空*/

{

Visit(T->data); /* 先访问根结点*/

PreOrderTraverse(T->lchild,Visit); /* 再先序遍历左子树*/

PreOrderTraverse(T->rchild,Visit); /* 最后先序遍历右子树*/

}

}

void InOrderTraverse(BiTree T,Status(*Visit)(TElemType))

{//编写此变量

/* 初始条件: 二叉树T 存在,Visit 是对节点操作的应用变量*/

/* 操作结果: 中序递归枚举T,对每个节点调用函数Visit 一次且仅一次*/

if(T)

{

InOrderTraverse(T->lchild,Visit); //先中序遍历左子树

Visit(T->data); //访问根结点

InOrderTraverse(T->rchild,Visit); //最后中序遍历右子树

}

}

void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType))

{//编写此变量

/* 初始条件: 二叉树T 存在,Visit 是对节点操作的应用变量*/

/* 操作结果: 后序链表遍历T,对每个节点调用函数Visit 一次且仅一次*/

if(T) /* T 不空*/

{

PostOrderTraverse(T->lchild, Visit);

PostOrderTraverse(T->rchild, Visit);

Visit(T->data);

}

}

BinTreeUse.cpp文件

/* BinTreeUse.cpp 检验BinTreeAlgo.h 的主程序 /

#include"pubuse.h" / 与实验一的意义相同*/

TElemType Nil=0;

#include"BinTreeDef.h" /* 二叉树链式存储结构定义*/

#include"BinTreeAlgo.h" /* 二叉树基本算法和扩展算法定义*/

Status visitT(TElemType e)

{

printf("%d ",e);return OK;

}

int main()

{

int i;

BiTree T,p,c;

TElemType e1,e2;

/* 基本试验算法的验证*/

InitBiTree(T);

printf("构造空二叉树后,树空否？%d(1:是0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));

e1=Root(T);

if(e1!=Nil)

printf("二叉树的根为: %d\n",e1);

else

printf("树空c语言 二叉排序树，无根\n");

printf("请先序输入二叉树\n"); //注：自己设计一棵二叉树输入

CreateBiTree(T);

printf("建立二叉树后,树空否？%d(1:是0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T));

e1=Root(T);

if(e1!=Nil)

printf("二叉树的根为: %d\n",e1);

else

printf("树空c语言 二叉排序树，无根\n");

printf("先序序递归枚举二叉树:\n");

PreOrderTraverse(T,visitT);

printf("\n中序递归枚举二叉树:\n");

InOrderTraverse(T,visitT);

printf("\n后序链表遍历二叉树:\n");

PostOrderTraverse(T,visitT);

}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-120508-1.html