二叉树查找-二分法查找二叉树

二分法查找二叉树方法：左大右小，找不到的时候就分支限定的查找 #include

#include

using namespace std;

struct tree{ // 声明树的结构

struct tree *left;

int data;

struct tree *right;

};

typedef struct tree treenode;//声明新类型的树的结构

typedef treenode *b_tree;//声明二叉树的链表

/*递归建立二叉树*/

b_tree creat_btree(int *nodelist,int position)//看好了某些定义b_tree {

b_tree newnode;//声明树根指针

if(nodelist[position]==0||position>15)

{//cout

return NULL;}

else{

newnode = (b_tree) malloc(sizeof(treenode));//申请空间

newnode->data=nodelist[position];//建立节点内容

//cout data;

newnode->left=creat_btree(nodelist,2*position); //递归建立左子树 newnode->right=creat_btree(nodelist,2*position+1);//递归建立右子树 return newnode;

}

//建立二叉树

//二叉树遍历方式查找

b_tree btree_travesal_search(b_tree point,int findnode)

{

b_tree point1,point2;//声名往左和往右查询的指针

if(point!=NULL)

{

if(point->data==findnode)

return point;

else

//找左子树

point1=btree_travesal_search(point->left,findnode);

//找右子树

point2=btree_travesal_search(point->right,findnode);

if(point1 != NULL)

return point1;

else if(point2!=NULL)

return point2;

else return NULL;

}

else

return NULL;

}

//二叉树二分查找法

b_tree btree_travesal_search1(b_tree point, int findnode)

{

while(point!=NULL)

{

if(point->data==findnode)//找到了数据

return point;//返回找到节点的指针

else

if(point->data>findnode)

{point=point->left;}//向左子树找

else {point=point->right;}//向右子树找

}

return NULL;

}

void inoder(b_tree point)

{

if(point!=NULL)

{

inoder(point->left);

cout data

inoder(point->right);

}

};

int main(int argc, char *argv[])

{

b_tree root = NULL;//树根指针

b_tree point = NULL;

int findnode;

int i;

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

//---------------建立树状结构-----------//

root = creat_btree(nodelist,1); //建立

printf("\n The node content of arrary_structure is:\n");

printf("\nPlease input the node value(1...9) you want search:");

scanf("%d",&findnode);

//进行遍历查找

point=btree_travesal_search(root,findnode);

if(point!=NULL)

{

cout

printf(" The finding node value is [%d]\n",point->data);

}

else

printf("\nTravesal search result: NOT found!!\n");

//二分查找

point = btree_travesal_search1(root,findnode);

if(point!=NULL)

{

cout

printf(" The finding node value is [%d]\n",point->data);

}

else cout

inoder(root);

for(i=1;i

cout

//打印树状结构连表的内容

//cout

inoder(root);*/

system("PAUSE");

return EXIT_SUCCESS;

}

#include

using namespace std;

struct tree{ // 声明树的结构

struct tree *left;

int data;

struct tree *right;

};

typedef struct tree treenode;//声明新类型的树的结构

typedef treenode *b_tree;//声明二叉树的链表

b_tree creat_btree(int *nodelist,int position)//看好了某些定义b_tree

{

b_tree newnode;//声明树根指针

if(nodelist[position]==0||position>15)

{cout

else{

newnode = (b_tree) malloc(sizeof(treenode));//申请空间

newnode->data=nodelist[position];//建立节点内容

newnode->left=creat_btree(nodelist,2*position); //递归建立左子树

newnode->right=creat_btree(nodelist,2*position+1);//递归建立右子树

return newnode;

}

//建立二叉树

void inoder(b_tree point)

{

if(point!=NULL)

{

inoder(point->left);

cout data

inoder(point->right);

}

int main(int argc, char *argv[])

{

b_tree root = NULL;//树根指针

int i;

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

//---------------建立树状结构-----------//

root = creat_btree(nodelist,1);

printf("\n The node content of arrary_structure is:\n");

for(i=1;i

cout

//打印树状结构连表的内容

//cout

inoder(root);

system("PAUSE");

return EXIT_SUCCESS;

}

注：递归的构建二叉树只是单独的递归调用构造函数，并没有按照一定的大小比较规则进行排序。

二叉树后序遍历的思想：

从根节点开始，沿左子树一直走到没有左孩子的节点为止，

并将所经[节点]的地址第一次进栈；

当找到没有左孩子的节点时，此节点的左子树已访问完毕；

从栈顶退出该节点，判断该节点是否为第一次进栈，如是，再

将所经[节点]的地址第二次进栈，并沿该节点的右子树一直走到

没有右孩子的节点为止，如否，则访问该节点；此时，该节点的

左、右子树都已完全遍历，且令指针p = NULL;

如此重复到栈空为止。

例如有如上图所示二叉树，则后序遍历的顺序是：O J / I * H + G A 实现程序如下：

#include

using namespace std;

struct tree{ // 声明树的结构

struct tree *left;

int data;

struct tree *right;

};

typedef struct tree treenode;//声明新类型的树的结构

typedef treenode *b_tree;//声明二叉树的链表

b_tree insert_node(b_tree root,int node)//看好了某些定义b_tree {

b_tree newnode;//声明树根指针

b_tree currentnode;//声明目前节点指针

b_tree parentnode;//声明父亲接点指针

//建立新节点的内存空间

newnode = (b_tree) malloc(sizeof(treenode));

//建立新节点的内存空间

newnode->data=node;//存入节点的内容

newnode->right=NULL;//设置右指针的初值

newnode->left=NULL;//设置左指针的初值

if(root == NULL) return newnode;

else

{

currentnode = root;

while(currentnode!=NULL)

{

parentnode = currentnode;

if(node data)//比较节点的数值大小

{currentnode = currentnode->left;}//坐子树

else currentnode =currentnode->right;//右子树

}//寻找空的节点便插入

if(parentnode->data > node)

{parentnode->left = newnode;}

else parentnode->right = newnode;//插入了哈哈

}

return root;

}

//建立二叉树

b_tree creat_btree(int *data,int len)

{

b_tree root = NULL;//根节点指针

int i;

for(i=0;i

{ root=insert_node(root,data[i]);}

return root;

}

//打印二叉树

/*void print_btree(b_tree root)

{

b_tree pointer;

pointer = root->left;

printf("Print left_subtree node of root:\n");

while(pointer!=NULL)

{

printf("[%2d]\n",pointer->data);

pointer = pointer->left;//指向左节点

}

pointer = root->right;

printf("Print right_subtree node of root:\n");

while(pointer!=NULL)

{

printf("[%2d]\n",pointer->data);//打印节点的内容

pointer = pointer->right;//指向右节点

}

}*/

void postoder(b_tree point)

{

if(point!=NULL)

{

postoder(point->left);//左--右--根

postoder(point->right);

cout data

}

int main(int argc, char *argv[])

{

b_tree root = NULL;

int i,index;

int value;

int nodelist[20];

printf("\n Please input the elsements of binary tree (Exit for 0):\n"); index = 0;

scanf("%d",&value);

while (value!= 0)

{

nodelist[index]=value;

index++;

scanf("%d",&value);

}

root= creat_btree(nodelist,index);//建立二叉树

// print_btree(root);//打印二叉树节点的内容

cout

postoder(root);

system("PAUSE");

return EXIT_SUCCESS;

}

#include

#include #include #include #define OK 1

#define ERROR 0

#define MAXSIZE 100 #define MAXRC 20 typedef int Status; typedef int ElemType; typedef struct

{

int i,j;

ElemType e;

}Triple;

typedef struct

{

Triple data[MAXSIZE+1]; int rpos[MAXRC+1]; int mu,nu,tu;

}RLSMatrix;

typedef struct OLNode {

int i,j;

ElemType e;

struct OLNode *right,*down; }OLNode,*OLink; typedef struct

{

OLink *rhead,*chead;

}CrossList;

Status CreateSMatrix(RLSMatrix *M);

void DestroySMatrix(RLSMatrix *M);

void PrintSMatrix(RLSMatrix M);

Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);

Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);

Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);

Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T);

int menu_select();

Status Operate(RLSMatrix A,RLSMatrix B,RLSMatrix *C);

Status Exchange(RLSMatrix M,CrossList *N);

Status Show(CrossList N);

Status Change(RLSMatrix A,RLSMatrix B,RLSMatrix C,CrossList *M);

Status DestoryCrossList(CrossList *M);

void About();

main()

{

RLSMatrix A,B,C;

CrossList N;

clrscr();

About();

for(;;)

{

switch(menu_select())

{

case 1:clrscr();

printf("\n\n\n\t-------------Create Sparse Matrix A-----------------");

CreateSMatrix(&A); break;

printf("\n\n\n\t-------------Create Sparse Matrix B-----------------");

CreateSMatrix(&B); break;

case 3:

Operate(A,B,&C);

break;

case 4:Change(A,B,C,&N); break;

case 5:About();break;

case 6:

DestroySMatrix(&A);

DestroySMatrix(&B);

DestroySMatrix(&C);

DestoryCrossList(&N);

exit(0);

}

int menu_select()

{

char *menu[]={

"",

" +--------------MENU--------------+",

" | |",

" | 1.Create Sparse Matrix A |",

" | 2.Create Sparse Matrix B |",

" | 3.Operate |",

" | 4.Change into CrossList |",

" | 5.About... |",

" | 6.Quit |",

" | |",

" +-----------------------------------+",

" By Teacher",

" 10/10/07",};

char s[3];

int c,i;

gotoxy(1,25);

printf("Any key to enter menu......\n");

getch();

clrscr();

for(i=0;i

{ gotoxy(10,i+1);

cprintf("%s",menu[i]);

}

window(1,1,80,25);

gotoxy(10,21);

do{printf("\n Enter your choice(1~6):");

scanf("%s",s);

c=atoi(s);

}while(c6);

return c;

}

Status CreateSMatrix(RLSMatrix *M)

{

int i;

Triple T;

int flag=0,mis;

printf("\nPlease input the row,col,and nonzero element number of the Sparse Matrix."); printf("\nForm:row num,col num,nonzero element num\n");

scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);

(*M).data[0].i=0;

for(i=1;i

{ mis=0;

{

if(flag)

{

printf("ERROR INPUT!\n");

flag=0;

mis++;}

if(mis==3)

{

printf("Fail Create !");

return OK;}

printf("Please input the row,col and value of the %dth nonzero element:",i);

scanf("%d,%d,%d",&T.i,&T.j,&T.e);

if(T.i(*M).mu||T.j(*M).nu)

flag=1;

if(T.i

flag=1;

}while(flag);

(*M).data[i]=T;

}

for(i=1;i

for(T.i=0;T.i

(*M).rpos[(*M).data[i].i-T.i]=i;

for(i=(*M).data[(*M).tu].i+1;i

(*M).rpos[i]=(*M).tu+1;

PrintSMatrix(*M);

return OK;

}

void PrintSMatrix(RLSMatrix M)

{

int i,j,k;

printf("\n ");

for(i=1,k=1;i

{

for(j=1;j

{

if(M.data[k].i==i&&M.data[k].j==j)

{printf("%d\t",M.data[k].e); k++;}

else printf("0\t");

while(j==M.nu)

{printf("\n ");break;}

}

Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)

{

int k,p,q;

if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;

(*Q).mu=M.mu;

(*Q).nu=M.nu;

(*Q).tu=0;

M.rpos[M.mu+1]=M.tu+1;

N.rpos[N.mu+1]=N.tu+1;

for(k=1;k

{

(*Q).rpos[k]=(*Q).tu+1;

p=M.rpos[k];

q=N.rpos[k];

while(p

{

if(M.data[p].j==N.data[q].j)

{

(*Q).data[(*Q).tu+1].e=M.data[p].e+N.data[q].e;

if((*Q).data[(*Q).tu+1].e!=0)

{

++(*Q).tu;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=M.data[p].j;

}

++p;

++q;

}

else if(M.data[p].j

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=M.data[p].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=M.data[p].j;

++p;

}

else

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=N.data[q].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=N.data[q].j;

++q;

}

while(p

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=M.data[p].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=M.data[p].j;

++p;

}

while(q

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=N.data[q].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=N.data[q].j;

++q;

}

return OK;

}

Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)

{

int i;

if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;

for(i=1;i

N.data[i].e*=-1;

ADD(M,N,Q);

return OK;

}

Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)

{

int arow,brow,p,q,ccol,ctemp[MAXRC+1];

if(M.nu!=N.mu) return ERROR;

(*Q).mu=M.mu;

(*Q).nu=N.nu;

(*Q).tu=0;

M.rpos[M.mu+1]=M.tu+1;

N.rpos[N.mu+1]=N.tu+1;

if(M.tu*N.tu!=0)

{

for(arow=1;arow

{

for(ccol=1;ccol

ctemp[ccol]=0;

(*Q).rpos[arow]=(*Q).tu+1;

for(p=M.rpos[arow];p

{

brow=M.data[p].j;

for(q=N.rpos[brow];q

{

ccol=N.data[q].j;

ctemp[ccol]+=M.data[p].e*N.data[q].e;

}

for(ccol=1;ccol

if(ctemp[ccol])

{

if(++(*Q).tu>MAXSIZE) return ERROR;

(*Q).data[(*Q).tu].i=arow;

(*Q).data[(*Q).tu].j=ccol;

(*Q).data[(*Q).tu].e=ctemp[ccol];

}

return OK;

}

Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T)

{

int col,p,q,t,num[MAXRC+1],cpot[MAXRC+1];

(*T).mu=M.nu;

(*T).nu=M.mu;

(*T).tu=M.tu;

if((*T).tu){

for(col=1;col

for(t=1;t

cpot[1]=1;

for(col=2;col

for(p=1;p

col=M.data[p].j; q=cpot[col];

(*T).data[q].i=M.data[p].j;

(*T).data[q].j=M.data[p].i;

(*T).data[q].e=M.data[p].e;

++cpot[col];

}

PrintSMatrix(M);

printf("\nTranspose:\n");

PrintSMatrix(*T);

return OK;

}

Status Operate(RLSMatrix A,RLSMatrix B,RLSMatrix *C)

{

int c;

char t;

do{

clrscr();

printf("\nInput your choice:\n(ADD--1,SUB--2,MUL--3,Transpose A--4,Transpose B--5,QUIT--any except 1~5)\n");

scanf("%d",&c);

switch(c)

{

case 1:

if(A.mu!=B.mu||A.nu!=B.nu)

{

printf("Can't,condition misfit!\n");

break;

}

ADD(A,B,C);

PrintSMatrix(A);

printf("\n\t(+)\n");

PrintSMatrix(B);

printf("\n\t(=)\n");

PrintSMatrix(*C);break;

case 2:

if(A.mu!=B.mu||A.nu!=B.nu)

{

printf("Can't,condition misfit!\n");

break;

}

SubtS(A,B,C);

PrintSMatrix(A);

printf("\n\t(-)\n");

PrintSMatrix(B);

printf("\n\t(=)\n");

PrintSMatrix(*C);break;

case 3:

if(A.nu!=B.mu)

{

printf("Can't,condition misfit\n");

break;

}

Mult(A,B,C);

PrintSMatrix(A);

printf("\n\t(*)\n");

PrintSMatrix(B);

printf("\n\t(=)\n");

PrintSMatrix(*C);break;

case 4:

FastTransposeSMatrix(A,C);break;

case 5:

FastTransposeSMatrix(B,C);break;

default: return OK;

}/* switch */

printf("Want to continue? (y/n)?");

t=getch();

}while(t=='y');

return OK;

}

void DestroySMatrix(RLSMatrix *M)

{

(*M).mu=0;

(*M).nu=0;

(*M).tu=0;

}

Status Exchange(RLSMatrix M,CrossList *N)

{

int i;

OLNode *p,*Q;

(*N).mu=M.mu;

(*N).nu=M.nu;

(*N).tu=M.tu;

(*N).rhead=(OLink*)malloc((MAXRC+1)*sizeof(OLink));

(*N).chead=(OLink*)malloc((MAXRC+1)*sizeof(OLink));

for(i=1;i

{

Q=(OLNode*)malloc(sizeof(OLNode));

Q->i=M.data[i].i;

Q->j=M.data[i].j;

Q->e=M.data[i].e;

if(!(*N).rhead[M.data[i].i])

{(*N).rhead[M.data[i].i]=Q;Q->right=NULL;}

else{

for(p=(*N).rhead[M.data[i].i];p->right;p=p->right);

p->right=Q;

Q->right=NULL;

}

if(!(*N).chead[M.data[i].j])

{(*N).chead[M.data[i].j]=Q;Q->down=NULL;}

else{

for(p=(*N).rhead[M.data[i].j];p->down;p=p->down);

p->down=Q;

Q->down=NULL;

}

return OK;

}

Status Show(CrossList N)

{

int i,j,sub;

int x,y;

OLNode *q;

printf("\n\n ");

for(i=1;i

printf("N.chead\n\nN.rhead\n");

for(i=1;i

{

if(N.rhead[i])

{

q=N.rhead[i];

printf(" |");

for(j=0;q;j=q->j,q=q->right)

{

sub=q->j-j;

while(sub>1)

{printf("-----------");

sub--;

}

printf("--->|%d|%d|%d|",q->i,q->j,q->e);

x=wherex();y=wherey();

gotoxy(x-4,y-1);

printf("V",x);

gotoxy(x-4,y-2);

printf("|");

gotoxy(x,y);

}

printf("\n\n\n");

}

else printf(" |^\n\n");;

}

return OK;

}

Status Change(RLSMatrix A,RLSMatrix B,RLSMatrix C,CrossList *M)

{

int cho;

clrscr();

printf("\n\n\nChoose the RLSMatrix you want to change into CrossList\n");

printf("(1--A,2--B,3--C,any but 123 back) :");

scanf("%d",&cho);

switch(cho)

{

case 1:Exchange(A,M);

Show(*M);break;

case 2:Exchange(B,M);

Show(*M);break;

case 3:Exchange(C,M);

Show(*M);break;

}

return OK;

}

Status DestoryCrossList(CrossList *M)

{

free((*M).rhead);

free((*M).chead);

(*M).chead=(*M).rhead=NULL;

return OK;

}

void About()

{

clrscr();

gotoxy(20,10);

printf("Made By: \n\n\t\t\t");

printf("\ The College of Information Engineering \n\n\t\t\t");

printf(" in AnHui University Of Finance & Economics ");

}

#include

void swap(int *a, int *b)

{

int temp = *a;

*a = *b;

*b = temp;

}

int partition(int *array, int low, int high)

{

int middle = (low + high)/2;

for(int i=low,j=high; i

while(array[i]

if(i

swap(&array[i], &array[middle]);

middle = i;

}

while(array[j] > array[middle]) --j;

if(i

swap(&array[j], &array[middle]);

middle = j;

}

return middle;

}

int quicksort(int *array, int low, int high)

{

int piovt_pos;

if(low

piovt_pos = partition(array, low, high);

quicksort(array, low, piovt_pos - 1);

quicksort(array, piovt_pos + 1, high);

}

struct barrel {

int a[10];

int count;

};

int main()

{

int data[] = {23, 12, 3, 54, 1, 98, 24, 34};

int min = data[0];

int max = data[0];

for(int i=1; i

min = min

max = max > data[i] ? max : data[i];

}

int num = (max - min + 1)/10 + 1;

barrel *pBarrel = new barrel[num];

for(int i=0; i

int j = (pBarrel+((data[i]-min+1)/10))->count;

(pBarrel+((data[i]-min+1)/10))->a[j] = data[i];

(pBarrel+((data[i]-min+1)/10))->count++;

}

static int pos = 0;

for(int i=0; i

quicksort((pBarrel+i)->a, 0, (pBarrel+i)->count-1);

for(int j=0; jcount; ++j) {

data[pos++] = (pBarrel+i)->a[j];

}

for(int i=0; i

printf("%d ", data[i]);

}

return 0;

}

简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储

(10..20]的整数，……集合B[i]存储( (i-1)*10, i*10]的整数，i = 1,2,..100。总共有 100个桶。

然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。

然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任

何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序，那么整个算法的复杂度是

O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

从上式看出，当m接近n的时候，桶排序复杂度接近O(n)

当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的

，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

二叉树查找-二分法查找二叉树

二分法查找二叉树方法：左大右小，找不到的时候就分支限定的查找 #include

#include

using namespace std;

struct tree{ // 声明树的结构

struct tree *left;

int data;

struct tree *right;

};

typedef struct tree treenode;//声明新类型的树的结构

typedef treenode *b_tree;//声明二叉树的链表

/*递归建立二叉树*/

b_tree creat_btree(int *nodelist,int position)//看好了某些定义b_tree {

b_tree newnode;//声明树根指针

if(nodelist[position]==0||position>15)

{//cout

return NULL;}

else{

newnode = (b_tree) malloc(sizeof(treenode));//申请空间

newnode->data=nodelist[position];//建立节点内容

//cout data;

newnode->left=creat_btree(nodelist,2*position); //递归建立左子树 newnode->right=creat_btree(nodelist,2*position+1);//递归建立右子树 return newnode;

}

//建立二叉树

//二叉树遍历方式查找

b_tree btree_travesal_search(b_tree point,int findnode)

{

b_tree point1,point2;//声名往左和往右查询的指针

if(point!=NULL)

{

if(point->data==findnode)

return point;

else

//找左子树

point1=btree_travesal_search(point->left,findnode);

//找右子树

point2=btree_travesal_search(point->right,findnode);

if(point1 != NULL)

return point1;

else if(point2!=NULL)

return point2;

else return NULL;

}

else

return NULL;

}

//二叉树二分查找法

b_tree btree_travesal_search1(b_tree point, int findnode)

{

while(point!=NULL)

{

if(point->data==findnode)//找到了数据

return point;//返回找到节点的指针

else

if(point->data>findnode)

{point=point->left;}//向左子树找

else {point=point->right;}//向右子树找

}

return NULL;

}

void inoder(b_tree point)

{

if(point!=NULL)

{

inoder(point->left);

cout data

inoder(point->right);

}

};

int main(int argc, char *argv[])

{

b_tree root = NULL;//树根指针

b_tree point = NULL;

int findnode;

int i;

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

//---------------建立树状结构-----------//

root = creat_btree(nodelist,1); //建立

printf("\n The node content of arrary_structure is:\n");

printf("\nPlease input the node value(1...9) you want search:");

scanf("%d",&findnode);

//进行遍历查找

point=btree_travesal_search(root,findnode);

if(point!=NULL)

{

cout

printf(" The finding node value is [%d]\n",point->data);

}

else

printf("\nTravesal search result: NOT found!!\n");

//二分查找

point = btree_travesal_search1(root,findnode);

if(point!=NULL)

{

cout

printf(" The finding node value is [%d]\n",point->data);

}

else cout

inoder(root);

for(i=1;i

cout

//打印树状结构连表的内容

//cout

inoder(root);*/

system("PAUSE");

return EXIT_SUCCESS;

}

#include

using namespace std;

struct tree{ // 声明树的结构

struct tree *left;

int data;

struct tree *right;

};

typedef struct tree treenode;//声明新类型的树的结构

typedef treenode *b_tree;//声明二叉树的链表

b_tree creat_btree(int *nodelist,int position)//看好了某些定义b_tree

{

b_tree newnode;//声明树根指针

if(nodelist[position]==0||position>15)

{cout

else{

newnode = (b_tree) malloc(sizeof(treenode));//申请空间

newnode->data=nodelist[position];//建立节点内容

newnode->left=creat_btree(nodelist,2*position); //递归建立左子树

newnode->right=creat_btree(nodelist,2*position+1);//递归建立右子树

return newnode;

}

//建立二叉树

void inoder(b_tree point)

{

if(point!=NULL)

{

inoder(point->left);

cout data

inoder(point->right);

}

int main(int argc, char *argv[])

{

b_tree root = NULL;//树根指针

int i;

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

//---------------建立树状结构-----------//

root = creat_btree(nodelist,1);

printf("\n The node content of arrary_structure is:\n");

for(i=1;i

cout

//打印树状结构连表的内容

//cout

inoder(root);

system("PAUSE");

return EXIT_SUCCESS;

}

注：递归的构建二叉树只是单独的递归调用构造函数，并没有按照一定的大小比较规则进行排序。

二叉树后序遍历的思想：

从根节点开始，沿左子树一直走到没有左孩子的节点为止，

并将所经[节点]的地址第一次进栈；

当找到没有左孩子的节点时，此节点的左子树已访问完毕；

从栈顶退出该节点，判断该节点是否为第一次进栈，如是，再

将所经[节点]的地址第二次进栈，并沿该节点的右子树一直走到

没有右孩子的节点为止，如否，则访问该节点；此时，该节点的

左、右子树都已完全遍历，且令指针p = NULL;

如此重复到栈空为止。

例如有如上图所示二叉树，则后序遍历的顺序是：O J / I * H + G A 实现程序如下：

#include

using namespace std;

struct tree{ // 声明树的结构

struct tree *left;

int data;

struct tree *right;

};

typedef struct tree treenode;//声明新类型的树的结构

typedef treenode *b_tree;//声明二叉树的链表

b_tree insert_node(b_tree root,int node)//看好了某些定义b_tree {

b_tree newnode;//声明树根指针

b_tree currentnode;//声明目前节点指针

b_tree parentnode;//声明父亲接点指针

//建立新节点的内存空间

newnode = (b_tree) malloc(sizeof(treenode));

//建立新节点的内存空间

newnode->data=node;//存入节点的内容

newnode->right=NULL;//设置右指针的初值

newnode->left=NULL;//设置左指针的初值

if(root == NULL) return newnode;

else

{

currentnode = root;

while(currentnode!=NULL)

{

parentnode = currentnode;

if(node data)//比较节点的数值大小

{currentnode = currentnode->left;}//坐子树

else currentnode =currentnode->right;//右子树

}//寻找空的节点便插入

if(parentnode->data > node)

{parentnode->left = newnode;}

else parentnode->right = newnode;//插入了哈哈

}

return root;

}

//建立二叉树

b_tree creat_btree(int *data,int len)

{

b_tree root = NULL;//根节点指针

int i;

for(i=0;i

{ root=insert_node(root,data[i]);}

return root;

}

//打印二叉树

/*void print_btree(b_tree root)

{

b_tree pointer;

pointer = root->left;

printf("Print left_subtree node of root:\n");

while(pointer!=NULL)

{

printf("[%2d]\n",pointer->data);

pointer = pointer->left;//指向左节点

}

pointer = root->right;

printf("Print right_subtree node of root:\n");

while(pointer!=NULL)

{

printf("[%2d]\n",pointer->data);//打印节点的内容

pointer = pointer->right;//指向右节点

}

}*/

void postoder(b_tree point)

{

if(point!=NULL)

{

postoder(point->left);//左--右--根

postoder(point->right);

cout data

}

int main(int argc, char *argv[])

{

b_tree root = NULL;

int i,index;

int value;

int nodelist[20];

printf("\n Please input the elsements of binary tree (Exit for 0):\n"); index = 0;

scanf("%d",&value);

while (value!= 0)

{

nodelist[index]=value;

index++;

scanf("%d",&value);

}

root= creat_btree(nodelist,index);//建立二叉树

// print_btree(root);//打印二叉树节点的内容

cout

postoder(root);

system("PAUSE");

return EXIT_SUCCESS;

}

#include

#include #include #include #define OK 1

#define ERROR 0

#define MAXSIZE 100 #define MAXRC 20 typedef int Status; typedef int ElemType; typedef struct

{

int i,j;

ElemType e;

}Triple;

typedef struct

{

Triple data[MAXSIZE+1]; int rpos[MAXRC+1]; int mu,nu,tu;

}RLSMatrix;

typedef struct OLNode {

int i,j;

ElemType e;

struct OLNode *right,*down; }OLNode,*OLink; typedef struct

{

OLink *rhead,*chead;

}CrossList;

Status CreateSMatrix(RLSMatrix *M);

void DestroySMatrix(RLSMatrix *M);

void PrintSMatrix(RLSMatrix M);

Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);

Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);

Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);

Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T);

int menu_select();

Status Operate(RLSMatrix A,RLSMatrix B,RLSMatrix *C);

Status Exchange(RLSMatrix M,CrossList *N);

Status Show(CrossList N);

Status Change(RLSMatrix A,RLSMatrix B,RLSMatrix C,CrossList *M);

Status DestoryCrossList(CrossList *M);

void About();

main()

{

RLSMatrix A,B,C;

CrossList N;

clrscr();

About();

for(;;)

{

switch(menu_select())

{

case 1:clrscr();

printf("\n\n\n\t-------------Create Sparse Matrix A-----------------");

CreateSMatrix(&A); break;

printf("\n\n\n\t-------------Create Sparse Matrix B-----------------");

CreateSMatrix(&B); break;

case 3:

Operate(A,B,&C);

break;

case 4:Change(A,B,C,&N); break;

case 5:About();break;

case 6:

DestroySMatrix(&A);

DestroySMatrix(&B);

DestroySMatrix(&C);

DestoryCrossList(&N);

exit(0);

}

int menu_select()

{

char *menu[]={

"",

" +--------------MENU--------------+",

" | |",

" | 1.Create Sparse Matrix A |",

" | 2.Create Sparse Matrix B |",

" | 3.Operate |",

" | 4.Change into CrossList |",

" | 5.About... |",

" | 6.Quit |",

" | |",

" +-----------------------------------+",

" By Teacher",

" 10/10/07",};

char s[3];

int c,i;

gotoxy(1,25);

printf("Any key to enter menu......\n");

getch();

clrscr();

for(i=0;i

{ gotoxy(10,i+1);

cprintf("%s",menu[i]);

}

window(1,1,80,25);

gotoxy(10,21);

do{printf("\n Enter your choice(1~6):");

scanf("%s",s);

c=atoi(s);

}while(c6);

return c;

}

Status CreateSMatrix(RLSMatrix *M)

{

int i;

Triple T;

int flag=0,mis;

printf("\nPlease input the row,col,and nonzero element number of the Sparse Matrix."); printf("\nForm:row num,col num,nonzero element num\n");

scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);

(*M).data[0].i=0;

for(i=1;i

{ mis=0;

{

if(flag)

{

printf("ERROR INPUT!\n");

flag=0;

mis++;}

if(mis==3)

{

printf("Fail Create !");

return OK;}

printf("Please input the row,col and value of the %dth nonzero element:",i);

scanf("%d,%d,%d",&T.i,&T.j,&T.e);

if(T.i(*M).mu||T.j(*M).nu)

flag=1;

if(T.i

flag=1;

}while(flag);

(*M).data[i]=T;

}

for(i=1;i

for(T.i=0;T.i

(*M).rpos[(*M).data[i].i-T.i]=i;

for(i=(*M).data[(*M).tu].i+1;i

(*M).rpos[i]=(*M).tu+1;

PrintSMatrix(*M);

return OK;

}

void PrintSMatrix(RLSMatrix M)

{

int i,j,k;

printf("\n ");

for(i=1,k=1;i

{

for(j=1;j

{

if(M.data[k].i==i&&M.data[k].j==j)

{printf("%d\t",M.data[k].e); k++;}

else printf("0\t");

while(j==M.nu)

{printf("\n ");break;}

}

Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)

{

int k,p,q;

if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;

(*Q).mu=M.mu;

(*Q).nu=M.nu;

(*Q).tu=0;

M.rpos[M.mu+1]=M.tu+1;

N.rpos[N.mu+1]=N.tu+1;

for(k=1;k

{

(*Q).rpos[k]=(*Q).tu+1;

p=M.rpos[k];

q=N.rpos[k];

while(p

{

if(M.data[p].j==N.data[q].j)

{

(*Q).data[(*Q).tu+1].e=M.data[p].e+N.data[q].e;

if((*Q).data[(*Q).tu+1].e!=0)

{

++(*Q).tu;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=M.data[p].j;

}

++p;

++q;

}

else if(M.data[p].j

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=M.data[p].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=M.data[p].j;

++p;

}

else

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=N.data[q].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=N.data[q].j;

++q;

}

while(p

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=M.data[p].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=M.data[p].j;

++p;

}

while(q

{

++(*Q).tu;

(*Q).data[(*Q).tu].e=N.data[q].e;

(*Q).data[(*Q).tu].i=k;

(*Q).data[(*Q).tu].j=N.data[q].j;

++q;

}

return OK;

}

Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)

{

int i;

if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;

for(i=1;i

N.data[i].e*=-1;

ADD(M,N,Q);

return OK;

}

Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q)

{

int arow,brow,p,q,ccol,ctemp[MAXRC+1];

if(M.nu!=N.mu) return ERROR;

(*Q).mu=M.mu;

(*Q).nu=N.nu;

(*Q).tu=0;

M.rpos[M.mu+1]=M.tu+1;

N.rpos[N.mu+1]=N.tu+1;

if(M.tu*N.tu!=0)

{

for(arow=1;arow

{

for(ccol=1;ccol

ctemp[ccol]=0;

(*Q).rpos[arow]=(*Q).tu+1;

for(p=M.rpos[arow];p

{

brow=M.data[p].j;

for(q=N.rpos[brow];q

{

ccol=N.data[q].j;

ctemp[ccol]+=M.data[p].e*N.data[q].e;

}

for(ccol=1;ccol

if(ctemp[ccol])

{

if(++(*Q).tu>MAXSIZE) return ERROR;

(*Q).data[(*Q).tu].i=arow;

(*Q).data[(*Q).tu].j=ccol;

(*Q).data[(*Q).tu].e=ctemp[ccol];

}

return OK;

}

Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T)

{

int col,p,q,t,num[MAXRC+1],cpot[MAXRC+1];

(*T).mu=M.nu;

(*T).nu=M.mu;

(*T).tu=M.tu;

if((*T).tu){

for(col=1;col

for(t=1;t

cpot[1]=1;

for(col=2;col

for(p=1;p

col=M.data[p].j; q=cpot[col];

(*T).data[q].i=M.data[p].j;

(*T).data[q].j=M.data[p].i;

(*T).data[q].e=M.data[p].e;

++cpot[col];

}

PrintSMatrix(M);

printf("\nTranspose:\n");

PrintSMatrix(*T);

return OK;

}

Status Operate(RLSMatrix A,RLSMatrix B,RLSMatrix *C)

{

int c;

char t;

do{

clrscr();

printf("\nInput your choice:\n(ADD--1,SUB--2,MUL--3,Transpose A--4,Transpose B--5,QUIT--any except 1~5)\n");

scanf("%d",&c);

switch(c)

{

case 1:

if(A.mu!=B.mu||A.nu!=B.nu)

{

printf("Can't,condition misfit!\n");

break;

}

ADD(A,B,C);

PrintSMatrix(A);

printf("\n\t(+)\n");

PrintSMatrix(B);

printf("\n\t(=)\n");

PrintSMatrix(*C);break;

case 2:

if(A.mu!=B.mu||A.nu!=B.nu)

{

printf("Can't,condition misfit!\n");

break;

}

SubtS(A,B,C);

PrintSMatrix(A);

printf("\n\t(-)\n");

PrintSMatrix(B);

printf("\n\t(=)\n");

PrintSMatrix(*C);break;

case 3:

if(A.nu!=B.mu)

{

printf("Can't,condition misfit\n");

break;

}

Mult(A,B,C);

PrintSMatrix(A);

printf("\n\t(*)\n");

PrintSMatrix(B);

printf("\n\t(=)\n");

PrintSMatrix(*C);break;

case 4:

FastTransposeSMatrix(A,C);break;

case 5:

FastTransposeSMatrix(B,C);break;

default: return OK;

}/* switch */

printf("Want to continue? (y/n)?");

t=getch();

}while(t=='y');

return OK;

}

void DestroySMatrix(RLSMatrix *M)

{

(*M).mu=0;

(*M).nu=0;

(*M).tu=0;

}

Status Exchange(RLSMatrix M,CrossList *N)

{

int i;

OLNode *p,*Q;

(*N).mu=M.mu;

(*N).nu=M.nu;

(*N).tu=M.tu;

(*N).rhead=(OLink*)malloc((MAXRC+1)*sizeof(OLink));

(*N).chead=(OLink*)malloc((MAXRC+1)*sizeof(OLink));

for(i=1;i

{

Q=(OLNode*)malloc(sizeof(OLNode));

Q->i=M.data[i].i;

Q->j=M.data[i].j;

Q->e=M.data[i].e;

if(!(*N).rhead[M.data[i].i])

{(*N).rhead[M.data[i].i]=Q;Q->right=NULL;}

else{

for(p=(*N).rhead[M.data[i].i];p->right;p=p->right);

p->right=Q;

Q->right=NULL;

}

if(!(*N).chead[M.data[i].j])

{(*N).chead[M.data[i].j]=Q;Q->down=NULL;}

else{

for(p=(*N).rhead[M.data[i].j];p->down;p=p->down);

p->down=Q;

Q->down=NULL;

}

return OK;

}

Status Show(CrossList N)

{

int i,j,sub;

int x,y;

OLNode *q;

printf("\n\n ");

for(i=1;i

printf("N.chead\n\nN.rhead\n");

for(i=1;i

{

if(N.rhead[i])

{

q=N.rhead[i];

printf(" |");

for(j=0;q;j=q->j,q=q->right)

{

sub=q->j-j;

while(sub>1)

{printf("-----------");

sub--;

}

printf("--->|%d|%d|%d|",q->i,q->j,q->e);

x=wherex();y=wherey();

gotoxy(x-4,y-1);

printf("V",x);

gotoxy(x-4,y-2);

printf("|");

gotoxy(x,y);

}

printf("\n\n\n");

}

else printf(" |^\n\n");;

}

return OK;

}

Status Change(RLSMatrix A,RLSMatrix B,RLSMatrix C,CrossList *M)

{

int cho;

clrscr();

printf("\n\n\nChoose the RLSMatrix you want to change into CrossList\n");

printf("(1--A,2--B,3--C,any but 123 back) :");

scanf("%d",&cho);

switch(cho)

{

case 1:Exchange(A,M);

Show(*M);break;

case 2:Exchange(B,M);

Show(*M);break;

case 3:Exchange(C,M);

Show(*M);break;

}

return OK;

}

Status DestoryCrossList(CrossList *M)

{

free((*M).rhead);

free((*M).chead);

(*M).chead=(*M).rhead=NULL;

return OK;

}

void About()

{

clrscr();

gotoxy(20,10);

printf("Made By: \n\n\t\t\t");

printf("\ The College of Information Engineering \n\n\t\t\t");

printf(" in AnHui University Of Finance & Economics ");

}

#include

void swap(int *a, int *b)

{

int temp = *a;

*a = *b;

*b = temp;

}

int partition(int *array, int low, int high)

{

int middle = (low + high)/2;

for(int i=low,j=high; i

while(array[i]

if(i

swap(&array[i], &array[middle]);

middle = i;

}

while(array[j] > array[middle]) --j;

if(i

swap(&array[j], &array[middle]);

middle = j;

}

return middle;

}

int quicksort(int *array, int low, int high)

{

int piovt_pos;

if(low

piovt_pos = partition(array, low, high);

quicksort(array, low, piovt_pos - 1);

quicksort(array, piovt_pos + 1, high);

}

struct barrel {

int a[10];

int count;

};

int main()

{

int data[] = {23, 12, 3, 54, 1, 98, 24, 34};

int min = data[0];

int max = data[0];

for(int i=1; i

min = min

max = max > data[i] ? max : data[i];

}

int num = (max - min + 1)/10 + 1;

barrel *pBarrel = new barrel[num];

for(int i=0; i

int j = (pBarrel+((data[i]-min+1)/10))->count;

(pBarrel+((data[i]-min+1)/10))->a[j] = data[i];

(pBarrel+((data[i]-min+1)/10))->count++;

}

static int pos = 0;

for(int i=0; i

quicksort((pBarrel+i)->a, 0, (pBarrel+i)->count-1);

for(int j=0; jcount; ++j) {

data[pos++] = (pBarrel+i)->a[j];

}

for(int i=0; i

printf("%d ", data[i]);

}

return 0;

}

简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储

(10..20]的整数，……集合B[i]存储( (i-1)*10, i*10]的整数，i = 1,2,..100。总共有 100个桶。

然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。

然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任

何排序法都可以。最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。

假设有n个数字，有m个桶，如果数字是平均分布的，则每个桶里面平均有n/m个数字。如果

对每个桶中的数字采用快速排序，那么整个算法的复杂度是

O(n + m * n/m*log(n/m)) = O(n + nlogn - nlogm)

从上式看出，当m接近n的时候，桶排序复杂度接近O(n)

当然，以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的

，实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中，那就退化成一般的排序了。

二叉树查找-二分法查找二叉树

相关文章