c語言二叉排序,c語言創建排序二叉樹

本文目錄一覽：

• 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 */

}