用c语言编译二叉树,C语言数据结构平衡二叉树实例详解

淡淡的烟草味﹌ 2022-10-14 12:55 117阅读 0赞

数据结构平衡二叉树

参考代码如下：

/\*

名称：平衡二叉树

语言：数据结构C语言版

编译环境：VC++ 6.0

日期： 2014-3-26

\*/

\#include

\#define LH +1 // 左高

\#define EH 0 // 等高

\#define RH -1 // 右高

\#define N 5 // 数据元素个数

typedef char KeyType; // 设关键字域为字符型

typedef struct

KeyType key;

int order;

\}ElemType; // 数据元素类型

// 平衡二叉树的类型

typedef struct BSTNode

ElemType data;

// bf结点的平衡因子,只能够取0，-1，1，它是左子树的深度减去

// 右子树的深度得到的

int bf;

struct BSTNode \*lchild,\*rchild; // 左、右孩子指针

\}BSTNode,\*BSTree;

// 构造一个空的动态查找表DT

int InitDSTable(BSTree \*DT)

\*DT=NULL;

return 1;

// 销毁动态查找表DT

void DestroyDSTable(BSTree \*DT)

if(\*DT) // 非空树

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

DestroyDSTable(&(\*DT)->lchild); // 销毁左孩子子树

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

DestroyDSTable(&(\*DT)->rchild); // 销毁右孩子子树

free(\*DT); // 释放根结点

\*DT=NULL; // 空指针赋0

// 在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，

// 若查找成功，则返回指向该数据元素结点的指针,否则返回空指针。

BSTree SearchBST(BSTree T,KeyType key)

if((!T)|| (key == T->data.key))

return T; // 查找结束

else if(key < T->data.key) // 在左子树中继续查找

return SearchBST(T->lchild,key);

else

return SearchBST(T->rchild,key); // 在右子树中继续查找

// 对以\*p为根的二叉排序树作右旋处理，处理之后p指向新的树根结点，即旋转

// 处理之前的左子树的根结点。

void R\_Rotate(BSTree \*p)

BSTree lc;

lc=(\*p)->lchild; // lc指向p的左子树根结点

(\*p)->lchild=lc->rchild; // lc的右子树挂接为p的左子树

lc->rchild=\*p;

\*p=lc; // p指向新的根结点

// 对以\*p为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，即旋转

// 处理之前的右子树的根结点。

void L\_Rotate(BSTree \*p)

BSTree rc;

rc=(\*p)->rchild; // rc指向p的右子树根结点

(\*p)->rchild=rc->lchild; // rc的左子树挂接为p的右子树

rc->lchild=\*p;

\*p=rc; // p指向新的根结点

// 对以指针T所指结点为根的二叉树作左平衡旋转处理，本算法结束时，

// 指针T指向新的根结点。

void LeftBalance(BSTree \*T)

BSTree lc,rd;

lc=(\*T)->lchild; // lc指向\*T的左子树根结点

switch(lc->bf)

\{ // 检查\*T的左子树的平衡度，并作相应平衡处理

case LH: // 新结点插入在\*T的左孩子的左子树上，要作单右旋处理

(\*T)->bf=lc->bf=EH;

R\_Rotate(T);

break;

case RH: // 新结点插入在\*T的左孩子的右子树上，要作双旋处理

rd=lc->rchild; // rd指向\*T的左孩子的右子树根

switch(rd->bf)

\{ // 修改\*T及其左孩子的平衡因子

case LH:

(\*T)->bf=RH;

lc->bf=EH;

break;

case EH:

(\*T)->bf=lc->bf=EH;

break;

case RH:

(\*T)->bf=EH;

lc->bf=LH;

rd->bf=EH;

L\_Rotate(&(\*T)->lchild); // 对\*T的左子树作左旋平衡处理

R\_Rotate(T); // 对\*T作右旋平衡处理

// 对以指针T所指结点为根的二叉树作右平衡旋转处理，本算法结束时，

// 指针T指向新的根结点

void RightBalance(BSTree \*T)

BSTree rc,rd;

rc=(\*T)->rchild; // rc指向\*T的右子树根结点

switch(rc->bf)

\{ // 检查\*T的右子树的平衡度，并作相应平衡处理

case RH: // 新结点插入在\*T的右孩子的右子树上，要作单左旋处理

(\*T)->bf=rc->bf=EH;

L\_Rotate(T);

break;

case LH: // 新结点插入在\*T的右孩子的左子树上，要作双旋处理

rd=rc->lchild; // rd指向\*T的右孩子的左子树根

switch(rd->bf)

\{ // 修改\*T及其右孩子的平衡因子

case RH: (\*T)->bf=LH;

rc->bf=EH;

break;

case EH: (\*T)->bf=rc->bf=EH;

break;

case LH: (\*T)->bf=EH;

rc->bf=RH;

rd->bf=EH;

R\_Rotate(&(\*T)->rchild); // 对\*T的右子树作右旋平衡处理

L\_Rotate(T); // 对\*T作左旋平衡处理

// 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，则插入一个

// 数据元素为e的新结点，并返回1，否则返回0。若因插入而使二叉排序树

// 失去平衡，则作平衡旋转处理，布尔变量taller反映T长高与否。

int InsertAVL(BSTree \*T,ElemType e,int \*taller)

if(!\*T)

\{ // 插入新结点，树“长高”，置taller为1

\*T=(BSTree)malloc(sizeof(BSTNode));

(\*T)->data=e;

(\*T)->lchild=(\*T)->rchild=NULL;

(\*T)->bf=EH;

\*taller=1;

else

if(e.key == (\*T)->data.key)

\{ // 树中已存在和e有相同关键字的结点则不再插入

\*taller=0;

return 0;

if(e.key < (\*T)->data.key)

\{ // 应继续在\*T的左子树中进行搜索

if(!InsertAVL(&(\*T)->lchild,e,taller)) // 未插入

return 0;

if(\*taller)

// 已插入到\*T的左子树中且左子树“长高”

switch((\*T)->bf) // 检查\*T的平衡度

case LH:

// 原本左子树比右子树高，需要作左平衡处理

LeftBalance(T);

\*taller=0; //标志没长高

break;

case EH:

// 原本左、右子树等高，现因左子树增高而使树增高

(\*T)->bf=LH;

\*taller=1; //标志长高

break;

case RH:

// 原本右子树比左子树高，现左、右子树等高

(\*T)->bf=EH;

\*taller=0; //标志没长高

else

// 应继续在\*T的右子树中进行搜索

if(!InsertAVL(&(\*T)->rchild,e,taller)) // 未插入

return 0;

if(\*taller) // 已插入到T的右子树且右子树“长高”

switch((\*T)->bf) // 检查T的平衡度

case LH:

(\*T)->bf=EH; // 原本左子树比右子树高，现左、右子树等高

\*taller=0;

break;

case EH: // 原本左、右子树等高，现因右子树增高而使树增高

(\*T)->bf=RH;

\*taller=1;

break;

case RH: // 原本右子树比左子树高，需要作右平衡处理

RightBalance(T);

\*taller=0;

return 1;

// 按关键字的顺序对DT的每个结点调用函数Visit()一次

void TraverseDSTable(BSTree DT,void(\*Visit)(ElemType))

if(DT)

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

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

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

void print(ElemType c)

printf("(%d,%d)",c.key,c.order);

int main()

BSTree dt,p;

int k;

int i;

KeyType j;

ElemType r\[N\]=\{

\{13,1\},\{24,2\},\{37,3\},\{90,4\},\{53,5\}

\}; // (以教科书P234图9.12为例)

InitDSTable(&dt); // 初始化空树

for(i=0;i

InsertAVL(&dt,r\[i\],&k); // 建平衡二叉树

TraverseDSTable(dt,print); // 按关键字顺序遍历二叉树

printf("\\n请输入待查找的关键字: ");

scanf("%d",&j);

p=SearchBST(dt,j); // 查找给定关键字的记录

if(p)

print(p->data);

else

printf("表中不存在此值");

printf("\\n");

DestroyDSTable(&dt);

system("pause");

return 0;

/\*

输出效果：

(13,1)(24,2)(37,3)(53,5)(90,4)

请输入待查找的关键字: 53

(53,5)

请按任意键继续. . .

\*/

运行结果如下：

![a1b7a07c65167f260170397a754edcc6.gif][]

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

[a1b7a07c65167f260170397a754edcc6.gif]: /images/20221014/52aec77c8ffa458dba15d3f70fc71d78.png

用c语言编译二叉树,C语言数据结构平衡二叉树实例详解

发表评论取消回复

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

相关阅读

相关 C语言数据结构——树和二叉树

相关 C语言-数据结构-线索二叉树

相关 C语言的数据结构——二叉树

相关 C语言重构【110】平衡二叉树

相关用c语言编译二叉树,C语言数据结构平衡二叉树实例详解

相关数据结构——二叉查找树（C语言）

相关 C语言数据结构——二叉树

相关 C语言-数据结构-二叉排序树

相关 C语言数据结构——线索二叉树

相关 C语言数据结构——二叉树