本文主要是介绍王道C语言督学营OJ课后习题(课时15),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef struct BSTNode{KeyType key;struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;
//递归
int BST_Insert(BiTree &T,KeyType k)
{if(NULL==T){//为新结点申请空间,第一个作为树根,后面递归再进入的不是树根,是为叶子结点T= (BiTree)calloc(1,sizeof(BSTNode) );T->key=k;return 1;} else if(k==T->key)return 0;//发现相同元素,不插入,考研不考else if(k<T->key)return BST_Insert(T->lchild,k);elsereturn BST_Insert(T->rchild,k);
}
void Creat_BST(BiTree &T,KeyType *str,int n)
{T=NULL;//T是树根int i=0;while (i<n){BST_Insert(T,str[i]);//把某一个结点放入二叉树i++;}
}
int element_pos=0;
void InOrder(BiTree T,int *arr)
{if(T!=NULL){InOrder(T->lchild,arr);printf("%3d",T->key);arr[element_pos++]=T->key;InOrder(T->rchild,arr);}
}
BSTNode *BST_Search(BiTree T,KeyType key,BiTree &p)
{p=NULL;while (T!=NULL&&key!=T->key){p=T;if (key<T->key)T=T->lchild;elseT=T->rchild;}return T;
}
int BinarySearch(int *str,KeyType key,int len)
{int low=0,high=len-1,mid;while (low<=high){mid=(low+high)/2;if(key>str[mid]){low=mid+1;} else if (key<str[mid]){high=mid-1;} else{return mid;}}return -1;
}
int main() {BiTree T=NULL;//树根BiTree parent;//存储父亲结点的地址值BiTree search;int pos;KeyType str[10];for (int i = 0; i < 10; ++i) {scanf("%d",&str[i]);}Creat_BST(T,str,10);InOrder(T,str);printf("\n");int key_pos;key_pos= BinarySearch(str,21,10);printf("%d",key_pos);return 0;
}
这篇关于王道C语言督学营OJ课后习题(课时15)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!