平衡二叉排序树的设计与实现C语言源程序代码(一定要C的哟!)

这是我前几天写的，看了下应该可以满足要求，由于测试还不够，不知道有没有bug。

第一点你自己改改，2、3都达到了，至于第四，不用说肯定是平衡了的二叉树相对查找效率要高一些，平衡，随机插入，打乱插入等 *** 作都是为了防止最差情况的线性树的出现。测试的话用rand()生成随机数外加timeh里的几个函数，配合使用下就出来了。

#include <stdioh>

#include <stdlibh>

// binary search tree

typedef struct BST

{

int data;

struct BST lhs;

struct BST rhs;

}BST;

// 插入一个节点

BST BSTInsertNode(BST root, int elem)

{

BST node;

node = (BST)malloc(sizeof(BST));

node->data = elem;

node->lhs = node->rhs = 0;

if(!root)

return node;

while(1)

{

if(node->data < root->data)

{

if(root->lhs)

root = root->lhs;

else

{

root->lhs = node;

return root->lhs;

}

}

else

{

if(root->rhs)

root = root->rhs;

else

{

root->rhs = node;

return root->rhs;

}

}

}

}

// 获得父节点

BST BSTGetParentNode(BST root, BST node)

{

if(root == node)

return 0;

if(root->lhs && node->data < root->lhs->data)

return BSTGetParentNode(root->lhs, node);

else if(root->rhs && node->data > root->rhs->data)

return BSTGetParentNode(root->rhs, node);

else

return root;

}

// 删除一个节点

BST BSTDeleteNode(BST root, BST node)

{

BST parent;

BST whichNode;

BST temp;

if(root != node)

{

parent = BSTGetParentNode(root, node);

whichNode = parent->lhs == node &parent->lhs : &parent->rhs;

}

else

whichNode = &root;

if(!node->lhs && !node->rhs)

whichNode = 0;

else if(!((node->lhs 1 : 0) ^ (node->rhs 1 : 0)))

whichNode = node->lhs node->lhs : node->rhs;

else

{

temp = node->rhs;

while(temp->lhs)

temp = temp->lhs;

temp->lhs = node->lhs;

whichNode = node->rhs;

}

free(node);

return whichNode;

}

// 删除树

void BSTDeleteTree(BST node)

{

if(node)

{

BSTDeleteTree(node->lhs);

BSTDeleteTree(node->rhs);

free(node);

}

}

// 建造树，从数组构造

BST BSTBuildTree(int beg, int end)

{

BST root;

if(beg >= end)

return 0;

root = (BST)malloc(sizeof(BST));

root->data = beg++;

root->lhs = root->rhs = 0;

while(beg != end)

BSTInsertNode(root, beg++);

return root;

}

// 查找节点

BST BSTSearchNode(BST root, int elem)

{

if(root)

{

if(elem < root->data)

return BSTSearchNode(root->lhs, elem);

else if(elem > root->data)

return BSTSearchNode(root->rhs, elem);

else

return root;

}

else

return 0;

}

// 获得最小值

BST BSTGetMinimumNode(BST root)

{

while(root->lhs)

root = root->lhs;

return root;

}

// 获得最大值

BST BSTGetMaximumNode(BST root)

{

while(root->rhs)

root = root->rhs;

return root;

}

// 前序遍历

void BSTPreorderTraverse(BST node)

{

if(node)

{

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

BSTPreorderTraverse(node->lhs);

BSTPreorderTraverse(node->rhs);

}

}

// 中序遍历

void BSTInorderTraverse(BST node)

{

if(node)

{

BSTInorderTraverse(node->lhs);

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

BSTInorderTraverse(node->rhs);

}

}

// 后序遍历

void BSTPostorderTraverse(BST node)

{

if(node)

{

BSTPostorderTraverse(node->lhs);

BSTPostorderTraverse(node->rhs);

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

}

}

// 获得前继值

BST BSTGetPredecessor(BST root, BST node)

{

BST predecessor;

BST rightCld;

if(node->lhs)

return BSTGetMaximumNode(node->lhs);

predecessor = rightCld = node;

while((predecessor = BSTGetParentNode(root, predecessor)))

if(predecessor->rhs == rightCld)

return predecessor;

else

rightCld = predecessor;

return 0;

}

// 获得后继值

BST BSTGetSuccessor(BST root, BST node)

{

BST successor;

BST leftCld;

if(node->rhs)

return BSTGetMinimumNode(node->rhs);

successor = leftCld = node;

while((successor = BSTGetParentNode(root, successor)))

if(successor->lhs == leftCld)

return successor;

else

leftCld = successor;

return 0;

}

// 获得树高

int BSTGetTreeHeight(BST root)

{

int l;

int r;

if(root)

{

l = BSTGetTreeHeight(root->lhs);

r = BSTGetTreeHeight(root->rhs);

return 1 + (l > r l : r);

}

else

return -1;

}

// 计算子节点数

int BSTGetSubtreeNodeNum(BST node)

{

if(node)

return BSTGetSubtreeNodeNum(node->lhs)

+ BSTGetSubtreeNodeNum(node->rhs)

+ 1;

else

return 0;

}

// 用于打乱数组，交换

inline void Swap(int a, int b)

{

int temp;

temp = a;

a = b;

b = temp;

}

// 用于打乱数组，qsort的比较用过程

inline int CMP(const void lhs, const void rhs)

{

return (const int)lhs - (const int)rhs;

}

// 数组有序

int IsOrdered(int beg, int end)

{

int attri;

int cmpVal;

if(beg >= end)

return 0;

if(end - beg <= 2)

return 1;

if(beg < (beg + 1))

attri = 1;

else

attri = 0;

cmpVal = beg++;

while(++beg != end)

{

if(attri)

{

if(cmpVal > beg)

return 0;

}else

{

if(cmpVal < beg)

return 0;

}

}

return 1;

}

// 高层次打乱数组

void HighlyUnorderArray(int beg, int end)

{

int mid = beg + (end - beg)/2;

int folk;

if(!IsOrdered(beg, end))

qsort(beg, end - beg, sizeof(int), CMP);

if((mid - beg) & 1)

Swap(beg++, mid);

folk = beg + 2;

while(folk < mid)

{

Swap(beg++, folk++);

Swap(beg++, folk++);

}

folk = mid + 2;

while(folk < end)

{

Swap(folk, folk - 1);

folk += 2;

}

}

// 中序遍历结果输出到数组

void BSTInorderWalkToArray(BST root, int p)

{

if(root)

{

BSTInorderWalkToArray(root->lhs, p);

p = root->data;

(p)++;

BSTInorderWalkToArray(root->rhs, p);

}

}

// 平衡树，返回平衡好的新树

BST BSTBalanceTree(BST root)

{

int size = BSTGetSubtreeNodeNum(root);

int a = (int)malloc(sizeof(int) size);

int end = a;

BST balancedTree;

BSTInorderWalkToArray(root, &end);

HighlyUnorderArray(a, end);

balancedTree = BSTBuildTree(a, end);

free(a);

return balancedTree;

}

int main()

{

int a[] = {5,6,3,7,9,8,1,0,4,2};

int c[] = {50,17,76,9,23,54,14,19,72,12,67};

BST bstTree = BSTBuildTree(a, a + sizeof(a)/sizeof(a[0]));

BSTPreorderTraverse(bstTree);

putchar('\n');

BSTInorderTraverse(bstTree);

putchar('\n');

BSTPostorderTraverse(bstTree);

printf("\n\n");

BST balancedTree = BSTBalanceTree(bstTree);

printf("%d %d\n", BSTGetTreeHeight(bstTree), BSTGetTreeHeight(balancedTree));

BSTDeleteTree(bstTree);

BSTDeleteTree(balancedTree);

}

源程序(source code)是指未编译的按照一定的程序设计语言规范书写的文本文件。 源代码(也称源程序)，是指一系列人类可读的计算机语言指令。 在程序语言中，源代码可以是以书籍或者磁带的形式出现，但最为常用的格式是文本文件，这种典型格式的目的是为了编译出计算机程序。计算机源代码的最终目的是将人类可读的文本翻译成为计算机可以执行的二进制指令，这种过程叫做编译，通过编译器完成。C语言源代码即用C语言编写的一类可读的计算机语言指令。

//=======================

// 8个LED 闪烁

// 用来回循环亮

//-------------------------------------

#include <reg51h>

#include <intrinsh>

#define uchar unsigned char

#define uint unsigned int

uchar i ;

//--------------------------------

void DelayMS(uint ms)

{

uchar t;

while(ms--) for (t=0;t<120;t++);

}

//----------------------------------

void main()

{

P2= 0xfe;

while (1)

{

for ( i = 0; i < 7; i++)

{P2 =_crol_(P2,1); //左移

DelayMS(200);

}

for ( i = 0; i < 7; i++)

{P2 =_cror_(P2,1); //右移

DelayMS(200);

}

}

}

分类: 电脑/网络 >> 程序设计 >> 其他编程语言

解析:

C语言基础知识常量和变量分类:C/C++

1常 量: 程序执行过程中,值不变的量。 3 ，\'a\'

变 量：值可以改变的量。

一个变量有一个名字，在内存中有一定的存储单元，存放变量的值。

2常量类型：

a整 型：12，0，-3

b实 型：46,-12

c字 符 型: \'a\',\'d\'

d符号常量: #define PRICE 30 (PRICE不能再被赋值且要大写)

3变 量: 先定义,后使用。一个变量只能被指定为一确定类型。

4标识符：标识变量名，符号常量名，函数名，数组名，类型名，文件名的有效字符数列。

a由字母、数字、下划线三种字符组成，第一个字符必须为字母或下划线。

b大写字母、小写字母被认为是两个不同的字符。

c长度一般小于8个。

数据类型

一整 型:

1整型常量

a十 进 制:12,-3,0

b八 进 制:以0开头。

c十六进制:以0x开头。

2整型变量

a int -32768——32767

b short int -32768——32767

c long int

d unsigned int 0——65535

e unsigned short 0——65535

f unsigned long

int、short int、long int 第一位为符号位 0000001 （0为正，1为负）

unsigned 第一位不是符号位 0000001

所以int型和unsigned型的000001不是同一个值。

二实 型：

1实型常量：

a十进制数：数字和小数点组成。012，12，120，00

b指 数：e之前必须有数字，e后面必须为整数。12e3

2实型变量：

a单精度：float 7位有效数字 1111111可，11111111不可。

b双精度：double 15—16位有效数字 。

三字符型:

1字符常量:

a \'a\' , \'x\' , \'\' ,\'$\' 。

b 转义字符：‘\\n\'换。 \'\\t\'从第九列开始。\'\\r\'回车。 \'\\b\'退一格。

2字符变量：

char char=\'a\' 一个字符变量在内存占一个字节。

。将一个字符常量放到一个字符变量中，并不是把该字符本身放到内存单元中去，而是将该字符的ASC码

放到存储单元中，所以字符型数据和整型数据之间可以通用。一个字符型数据既可以以字符形式输出，

又可以以整数形式输出。

四字符串常量:

"how are you", "a","&12"

。不能把一个字符串赋给一个字符变量。 char c=\'a\'对,char c="how" 错。

。\'a\' :在内存中存a。

“a”:在内存中存a\\0。

‘\\0’是C语言中判断字符串是否结束的标志。

变量赋初值

a int a=3;

float f=72;

char c=\'a\';

b int a,b,c=5;

相当于 int a,b,c;

c=5;

c int a=3;b=3;c=3; 不可写： int a=b=c=3;

各类数值型数据间的混合运算

整型、实型、字符型数据可以混合运算：10+\'a\'+15-87654321\'b\'

double<--float

long

unsigned

int <--char,shot

float型转晃double型

char型,shot型转换为 int型

int型 转换为double型 等等

算术运算符和算术表达式

1基本算术运算符

+ 加

- 减

乘

/ 除 5/3=1

% 摸(MOD) 5%3=2

2强制类型转换运算符:将一个表达式转换成所需类型

(类型名)(表达式)

(double)a 将a转换为double型

(int)(x+y) 将x+y转换为int型

(float)(5%3) 将5%3转换为float型

putchar函数：输出一个字符

#include "stdioh"

a char a;

a=\'C\';

putchar(a);

b putchar(\'\\n\');

c putchar(\'\\102\');

getchar函数：输入一个字符

#include "stdioh"

a char c;

c=getchar();

putchar(c);

b putchar(getchar());

c printf("%c",getchar());

putchar函数:输出若干个任意类型的数据

a printf("%d,%d",a,b);

b printf("a=%d b=%d",a,b);

1d 输出十进制整数

a %d:

b%md: 指定输出的宽度。数据位数小于m，左端补空格；大于m，按实际位数输出。

a=123;b=12345;

printf("%4d,%4d",a,b);

输出结果为：_123,12345

c%ld: 输出长整型数据。

long a=123456;

printf("%ld",a); 用%d，错。

printf("%9ld",a); 输出结果为：___123456

2 o 输出八进制数

3 x 输出十六进制数

4 u 输出unsigned型数据

5 c 输出一个字符

6 s 输出一个字符串

a%s printf("%s""how");

b%ms

c%-ms

d%mns

e%-mns

7 f 以小数形式输出实数

a%f

b%mnf

c%-mnf

8 e 以指数形式输出实数

a%e

b%mne

c%-mne

scanf函数：输入任意类型的多个数据

scanf("%d%d%d",&a,&b,&c); &a指a在内存中的地址。

——按a,b,c在内存的地址将a,b,c的值存入。

if语句

1 if (A) B;

如果条件A满足，执行B，否则执行下一句。

2 if (A) B

else C;

如果条件A满足，执行B，否则执行C。

3 if (A)

if (B) C

else D;

else

if (F) H

else K;

输入三个数,按小到大输出。

main()

{ float a,b,c,t;

scanf("%f,%f,%f",&a,&b&c); 4 2 1

if (a>b)

{t=a;a=b;b=t;} 2 4 1

if (a>c)

{t=a;a=c;c=t} 1 4 2

if (b>c)

{t=b;b=c;c=t;} 1 2 4

printf("%f,%f,%f",a,bc);

}

switch 语句

switch(a)

{

case A : B; break;

case C : D; break;

default : F; break;

}

如果变量a=A,执行B；执行break语句，跳出swith语句。如果没有break语句，D，F语句也会执行。

如果变量a=C,执行B；其它情况执行F。

while 语句

while（A）

{

B;

}

如果条件A满足，执行B，否则执行下一句。(先判断，后执行。)

while(i<-5)

{

s=s+1;

i++;

}

如果i=1，则不满足i<-5，执行下一句。i值不变。

do-while 语句

do

{

A;

}

while(B);

先执行A，再判断B；如果B满足，再执行A，否则执行下一句。(先执行，后判断)

do

{

s=s+1;

i++;

}

while(i<-5)；

如果i=1，执行i++，i=4；不满足i<-5，执行下一句。

for 语句

for( A ; B ; C ) D;

A：为变量赋初值；

判断是否满足条件B；满足则执行D再执行C再判断B；

不满足则执行下一句。

for(i=1;i<=5;i++) s=s+1;

for(i=1,s=0;i<=5;i++) s=s+1;

for( ;i<=5;i++) s=s+1;

for( ;i<=5; ) { s=s+1; i++;}

break 语句

break 语句：终止循环。用于循环语句，switch语句。

while(A)

{

if (B) C; break;

}

执行break语句，跳出循环，执行后面的语句。

continue 语句

continue 语句：只结束本次循环，而不是终止整个循环。

while(A)

{

if (B) C; continue;

}

执行break语句，跳出循环，再判断A，继续执行循环。

题目01：在一个已知的字符串中查找最长单词，假定字符串中只含字母和空格，空格用来分隔不同的单词。

直接编译，程序执行结果如下图所示：

题目02：编写一个int string_len(char s)，返回字符串s的字符长度(不包括\0)。

直接编译，程序执行结果如下图所示：

扩展资料：

C语言是一门通用计算机编程语言，应用广泛。C语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

尽管C语言提供了许多低级处理的功能，但仍然保持着良好跨平台的特性，以一个标准规格写出的C语言程序可在许多电脑平台上进行编译，甚至包含一些嵌入式处理器（单片机或称MCU）以及超级电脑等作业平台。

C语言源程序是由：数据类型、常量与变量、数组、指针、字符串、文件输入/输出构成。

具体介绍：

1、数据类型

C的数据类型包括：整型、字符型、实型或浮点型（单精度和双精度）、枚举类型、数组类型、结构体类型、共用体类型、指针类型和空类型。

2、常量与变量

常量其值不可改变，符号常量名通常用大写。变量是以某标识符为名字，其值可以改变的量。标识符是以字母或下划线开头的一串由字母、数字或下划线构成的序列，请注意第一个字符必须为字母或下划线，否则为不合法的变量名。变量在编译时为其分配相应存储单元。

3、数组

如果一个变量名后面跟着一个有数字的中括号，这个声明就是数组声明。字符串也是一种数组。它们以ASCII的NULL作为数组的结束。要特别注意的是，方括内的索引值是从0算起的。

4、指针

指针不仅可以是变量的地址，还可以是数组、数组元素、函数的地址。通过指针作为形式参数可以在函数的调用过程得到一个以上的返回值，不同于return（z）这样的仅能得到一个返回值。

指针是一把双刃剑，许多 *** 作可以通过指针自然的表达，但是不正确的或者过分的使用指针又会给程序带来大量潜在的错误。

5、字符串

C语言的字符串其实就是以'\0'字符结尾的char型数组，使用字符型并不需要引用库，但是使用字符串就需要C标准库里面的一些用于对字符串进行 *** 作的函数。它们不同于字符数组。

6、文件输入/输出

在C语言中，输入和输出是经由标准库中的一组函数来实现的。在ANSI C中，这些函数被定义在头文件<stdioh>；中。

扩展资料：

语言特点

1、高级语言：它是把高级语言的基本结构和语句与低级语言的实用性结合起来的工作单元。

2、结构式语言：结构式语言的显著特点是代码及数据的分隔化，即程序的各个部分除了必要的信息交流外彼此独立。这种结构化方式可使程序层次清晰，便于使用、维护以及调试。

3、代码级别的跨平台：由于标准的存在，使得几乎同样的C代码可用于多种 *** 作系统，如Windows、DOS、UNIX等等；也适用于多种机型。C语言对编写需要进行硬件 *** 作的场合，优于其它高级语言。

4、使用指针：可以直接进行靠近硬件的 *** 作，但是C的指针 *** 作不做保护，也给它带来了很多不安全的因素。C++在这方面做了改进，在保留了指针 *** 作的同时又增强了安全性，受到了一些用户的支持。

以上就是关于平衡二叉排序树的设计与实现C语言源程序代码(一定要C的哟!)全部的内容，包括:平衡二叉排序树的设计与实现C语言源程序代码(一定要C的哟!)、C语言每个代码都是什么意思、《单片机C语言程序设计实训100例——基于8051+Proteus仿真》第03篇源代码等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！