本文目录一览：
- 1、平衡二叉排序树的设计与实现C语言源程序代码(一定要C的哟!)
- 2、用C语言实现二叉排序树排序，并按递减顺序打印各个数据
- 3、用C语言实现二叉排序树的构造
- 4、c语言 二叉排序树 100分
- 5、二叉排序树的实现（c语言）
平衡二叉排序树的设计与实现C语言源程序代码(一定要C的哟!)
这是我前几天写的，看了下应该可以满足要求，由于测试还不够，不知道有没有bug。
第一点你自己改改，2、3都达到了，至于第四，不用说肯定是平衡了的二叉树相对查找效率要高一些，平衡，随机插入，打乱插入等操作都是为了防止最差情况的线性树的出现。测试的话用rand()生成随机数外加time.h里的几个函数，配合使用下就出来了。
#include stdio.h
#include stdlib.h
// 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);
}
用C语言实现二叉排序树排序，并按递减顺序打印各个数据
#include stdio.h
#include malloc.h
typedef int KeyType;
typedef char InfoType[10];
typedef struct node //记录类型
{
KeyType key; //关键字项
InfoType data; //其他数据域
struct node *lchild,*rchild; //左右孩子指针
} BSTNode;
int InsertBST(BSTNode *p,KeyType k)
{
if (p==NULL) //原树为空, 新插入的记录为根结点
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p-key=k;
p-lchild=p-rchild=NULL;
return 1;
}
else if (k==p-key) //树中存在相同关键字的结点,返回0
return 0;
else if (kp-key)
return InsertBST(p-lchild,k); //插入到*p的左子树中
else
return InsertBST(p-rchild,k); //插入到*p的右子树中
}
BSTNode *CreateBST(KeyType A[],int n) //返回BST树根结点指针
{
BSTNode *bt=NULL; //初始时bt为空树
int i=0;
while (in)
{
InsertBST(bt,A[i]); //将关键字A[i]插入二叉排序树T中
i++;
}
return bt; //返回建立的二叉排序树的根指针
}
void DispInDescrease(BSTNode *bt){ //按从小到大输出查找树中的内容，对该树中序遍历即可
if(bt){
DispInDescrease(bt-lchild);
printf("%d\t",bt-key);
DispInDescrease(bt-rchild);
}
}
void main()
{
BSTNode *bt,*p,*f;
int n=9;
KeyType a[]={1,12,5,8,3,10,7,13,9};
bt=CreateBST(a,n);
DispInDescrease(bt);
}
//已上机验证成功
用C语言实现二叉排序树的构造
#include stdio.h
#include stdlib.h
typedef struct bnode
{
int data;
struct bnode *left , *right ;
} btree ;
void insert(btree **b , btree *s)
{
if(*b==NULL) *b = s ;
else if((*b)-data == s-data)
return ;
else if(s-data (*b)-data)
insert((*b)-right , s);
else if(s-data (*b)-data)
insert((*b)-left , s);
}
void creatTree(btree **b)
{
int x ;
btree *s ;
*b = NULL ;
do
{
printf("Input data please : ");
scanf("%d",x);
s = (btree *)malloc(sizeof(btree)) ;
s-data = x ;
s-left = NULL ;
s-right = NULL ;
insert( b , s );
} while(x != 0 );
}
void print(btree *b)
{
if (b != NULL)
{
printf("%d",b-data);
if (b-left != NULL || b-right != NULL)
{
printf("(");
print(b-left);
if(b-right != NULL)
printf(", ");
print(b-right);
printf(")");
}
}
}
void preorder(btree *b)
{
if (b!=NULL)
{
printf("%d",b-data);
preorder(b-left);
preorder(b-right);
}
}
void main()
{
btree *t = NULL;
creatTree(t);
printf("The binary tree is : ");
print(t);
printf("\n");
preorder(t);
printf("\n");
}
c语言 二叉排序树 100分
#include stdio.h #include stdlib.h typedef struct _BiTNode { int val; struct _BiTNode* lhs; struct _BiTNode* rhs; }BiTNode; //建立二叉排序树 void inserttree(BiTNode** Tree, int val) //插入函数 { BiTNode* t, *p, *n; t = (BiTNode*)malloc(sizeof(BiTNode)); t-val = val; t-lhs = t-rhs = NULL; p = NULL, n = *Tree; while(n) { p = n; n = val n-val ? n-lhs : n-rhs; } (p ? val p-val ? p-lhs : p-rhs : *Tree) = t; } void buildBST(BiTNode** Tree) { int val; char c; *Tree = NULL; while(1) { scanf("%d", val); inserttree(Tree, val); if((c = getchar()) == '\n') break; else ungetc(c, stdin); } } //二叉排序树查找 BiTNode* search(BiTNode* Tree, int val) { while(Tree) { if(val Tree-val) Tree = Tree-lhs; else if(val Tree-val) Tree = Tree-rhs; else return Tree; } return NULL; } //二叉排序树删除 void del(BiTNode* Tree) { if(Tree) { del(Tree-lhs); del(Tree-rhs); free(Tree); } } int main() { return 0; }
二叉排序树的实现（c语言）
/*二叉树的基本运算与实现*/
#include stdio.h
#include malloc.h
#define MAXNODE 256
typedef int datatype;
typedef struct BiTNode
{
datatype data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef struct
{
BiTree link;
int flag;
}stacktype;void menu();
int Initiate(BiTree *bt,datatype x);
BiTree InsertL(BiTree bt,datatype x,BiTree parent);
BiTree InsertR(BiTree bt,datatype x,BiTree parent);
BiTree DeleteL(BiTree bt,BiTree parent);
BiTree DeleteR(BiTree bt,BiTree parent);
void PreOrder(BiTree bt);
void InOrder(BiTree bt);
void PostOrder(BiTree bt);
void LevelOrder(BiTree bt);
BiTree Find(BiTree parent,datatype a);
void NRPreOrder(BiTree bt);
void NRInOrder(BiTree bt);
void NRPostOrder(BiTree bt);void main()
{
int n,m=1;
BiTree t; /*clrscr();*/
while(m)
{
menu();
scanf("%d",n);
switch(n)
{
case 1:{/*初始化*/
int flag;
datatype x;
printf("please input head point x:\n");
scanf("%d",x);
flag=Initiate(t,x);
if(flag==1)
printf("\nInitiate success!");
else
printf("\nInitiate fail!");
break;
}
case 2:{/*建树*/
break;
}
case 3:{/*插入结点x作为a的左孩子*/
datatype a,x;/*x作为a的左孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",a,x);
parent=Find(parent,a);
parent=InsertL(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 4:{/*插入结点x作为a的右孩子*/
datatype a,x;/*x作为a的右孩子*/
BiTree parent=t;
printf("please input a and x:\n");
scanf("%d%d",a,x);
parent=Find(parent,a);
parent=InsertR(t,x,parent);
if(parent!=NULL)
t=parent;
break;
}
case 5:{/*删除结点a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",a);
parent=Find(parent,a);
parent=DeleteL(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 6:{/*删除结点a的左孩子*/
datatype a;
BiTree parent=t;
printf("please input a:\n");
scanf("%d",a);
parent=Find(parent,a);
parent=DeleteR(t,parent);
if(parent!=NULL)
t=parent;
break;
}
case 7:{/*递归先序遍历*/
PreOrder(t);
break;
}
case 8:{/*递归中序遍历*/
InOrder(t);
break;
}
case 9:{/*递归后序遍历*/
PostOrder(t);
break;
}
case 10:{/*层次遍历*/
LevelOrder(t);
break;
}
case 11:{/*先序遍历的非递归实现*/
NRPreOrder(t);
break;
}
case 12:{/*中序遍历的非递归实现*/
NRInOrder(t);
break;
}
case 13:{/*后序遍历的非递归实现*/
NRPostOrder(t);
break;
}
case 0:m=0;
}
}
}
void menu()
{
/*clrscr();*/
printf("\n");
printf("\t\t1.initiate\n\n");
printf("\t\t2.create thread\n\n");
printf("\t\t3.insert Left\n\n");
printf("\t\t4.insert Right\n\n");
printf("\t\t5.delete Left\n\n");
printf("\t\t6.delete Right\n\n");
printf("\t\t7.preorder\n\n");
printf("\t\t8.inorder\n\n");
printf("\t\t9.postorder\n\n");
printf("\t\t10.levelorder\n\n");
printf("\t\t11.nrpreorder\n\n");
printf("\t\t12.nrinorder\n\n");
printf("\t\t13.nrpostorder\n\n");
printf("\t\t0.exit\n\n");
printf("\n\n\n\tplease select:");
}
int Initiate(BiTree *bt,datatype x)
{
if((*bt=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return 0;
(*bt)-data=x;
(*bt)-lchild=NULL;
(*bt)-rchild=NULL;
return 1;
}
BiTree InsertL(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p-data=x;
p-lchild=NULL;
p-rchild=NULL;
if(parent-lchild==NULL)
parent-lchild=p;
else
{
p-lchild=parent-lchild;
parent-lchild=p;
}
return bt;
}
BiTree InsertR(BiTree bt,datatype x,BiTree parent)
{
BiTree p;
if(parent==NULL)
{
printf("\nerror!\n");
return NULL;
}
if((p=(BiTNode*)malloc(sizeof(BiTNode)))==NULL)
return NULL;
p-data=x;
p-lchild=NULL;
p-rchild=NULL;
if(parent-rchild==NULL)
parent-rchild=p;
else
{
p-rchild=parent-rchild;
parent-rchild=p;
}
return bt;
}
BiTree DeleteL(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent-lchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent-lchild;
parent-lchild=NULL;
free(p);
return bt;
}
BiTree DeleteR(BiTree bt,BiTree parent)
{
BiTree p;
if(parent==NULL||parent-rchild==NULL)
{
printf("\ndelete error!");
return NULL;
}
p=parent-rchild;
parent-rchild=NULL;
free(p);
return bt;
}
void PreOrder(BiTree bt)
{
if(bt==NULL)
return;
printf("%5d",bt-data);
PreOrder(bt-lchild);
PreOrder(bt-rchild);
}
void InOrder(BiTree bt)
{
if(bt==NULL)
return;
InOrder(bt-lchild);
printf("%5d",bt-data);
InOrder(bt-rchild);
}
void PostOrder(BiTree bt)
{
if(bt==NULL)
return;
PostOrder(bt-lchild);
PostOrder(bt-rchild);
printf("%5d",bt-data);
}
void LevelOrder(BiTree bt)
{
BiTree Queue[MAXNODE];
int front,rear;
if(bt==NULL)
{
return;
}
front = -1;
rear = 0;
Queue[rear] = bt;
while(front!=rear)
{
front++;
printf("%5d",Queue[front]-data);
if(Queue[front]-lchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]-lchild;
}
if(Queue[front]-rchild!=NULL)
{
rear++;
Queue[rear]=Queue[front]-rchild;
}
}//end while
}
BiTree Find(BiTree parent,datatype a)
{
BiTree p;
if(parent==NULL)
p=NULL;
else if(parent-data==a)
p=parent;
else
{
p=Find(parent-lchild,a);
if(p==NULL)
p=Find(parent-rchild,a);
}
return p;
}
void NRPreOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
printf("%5d",p-data);
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p-lchild;
} /* end while p */
p=stack[top];
top--;
p=p-rchild;
} /* end while p top */
}
void NRInOrder(BiTree bt)
{
BiTree stack[MAXNODE],p;
int top;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
while(p!=NULL)
{
if(top==MAXNODE-1)
{
printf("Stack overflow!\n");
return;
} /* end if */
else
{
top++;
stack[top]=p;
} /* end if-else */
p=p-lchild;
} /* end while p */
p=stack[top];
top--;
printf("%5d",p-data);
p=p-rchild;
} /* end while p top */
}
void NRPostOrder(BiTree bt)
{
stacktype stack[MAXNODE];
BiTree p;
int top,sign;
if(bt==NULL)
{
printf("Tree is empty!\n");
return;
}
top=-1;
p=bt;
while((p!=NULL)||(top!=-1))
{
if(p!=NULL) /*结点第一次入栈*/
{
top++;
stack[top].link=p;
stack[top].flag=1; /*标记第一次入栈*/
p=p-lchild;
} /* end if */
else
{
p=stack[top].link;
sign=stack[top].flag;
top--;
if(sign==1) /*结点第二次入栈*/
{
top++;
stack[top].link=p;
stack[top].flag=2; /*标记第二次入栈*/
p=p-rchild;
} /* end if */
else
{
printf("%5d",p-data);
p=NULL;
} /* end if-else */
} /* end if-else */
} /* end while */
}
