当前位置： 移动技术网 > IT编程>开发语言>C/C++ > PTA-BinarySearchTree BasicOperation

PTA-BinarySearchTree BasicOperation

2019年02月18日  | 移动技术网IT编程  | 我要评论

堤莎也佳,雅家公仔,十大名车

 

/*  二叉查找树 基本操作  */
#include <stdio.h>
#include <stdlib.h>

typedef int elementtype;
typedef struct tnode *position;
typedef position bintree;

struct tnode {
    elementtype element;
    bintree left;
　　bintree right;
};

int preorderjudge( bintree t );        /*  判断是否满足bst */
void preordertraversal( bintree bst ); /* 先序遍历 */ 
void inordertraversal( bintree bst ); /* 中序遍历 */

bintree insert( bintree bst, elementtype x );
bintree delete( bintree bst, elementtype x );
position find( bintree bst, elementtype x );
position findmin( bintree bst );
position findmax( bintree bst );
int main() { 　　
   bintree bst, minp, maxp, tmp; 　　
   elementtype x; 　
 　int n, i; 　　

　　/*  insert node to build a bst */
   bst = null;  
　　scanf("%d", &n);  
　　for ( i = 0; i < n; i++ ) {
　　　　scanf("%d", &x);
　　　　bst = insert(bst, x);
　　}
　　printf("preorder: "); 
　　preordertraversal(bst); 
　　printf("\ninorder: "); 
　　inordertraversal(bst); 　　
　　printf("\n");　　　　
　　minp = findmin(bst); 　   
　　maxp = findmax(bst);　　
　　scanf("%d", &n); /* search n numebr */
　　for ( i = 0; i < n; i++ ) {
　　　　scanf("%d", &x);
　　　　tmp = find(bst, x);
　　　　if ( tmp == null ) 
　　　　　　printf("%d is not found\n", x);
　　　　else {
　　　　　　printf("%d is found\n", tmp->element);
　　　　　　if ( tmp == minp ) 
　　　　　　　　printf("%d is the smallest key\n", tmp->element);
　　　　　　if ( tmp == maxp ) 
　　　　　　　　printf("%d is the largest key\n", tmp->element);
　　　　}
　　} /* for */

   /* delete all nodes */
　　scanf("%d", &n);
　　for ( i = 0; i < n; i++ ) {
　　　　scanf("%d", &x);
　　　　bst = delete(bst, x);
　　}

　　return 0;
}

bintree insert( bintree bst, elementtype x )
{
　　if ( !bst ) {
　　　　/* 若原树为空，生成并返回一个结点的二叉搜索树 */
　　　　bst = (bintree)malloc(sizeof(struct tnode));
　　　　bst->element = x;
　　　　bst->left = bst->right = null;
　　}　else { 
　　　　/* 开始找要插入元素的位置 */
　　　　if ( x < bst->element )
　　　　　　bst->left = insert( bst->left, x ); /*递归插入左子树*/
　　　　else if ( x > bst->element )
　　　　　　bst->right = insert( bst->right, x ); /*递归插入右子树*/
　　　　　　/* else x已经存在，什么都不做 */
　　}
　　return bst;
}

bintree delete( bintree bst, elementtype x ) 
{ 
　　position tmp; 

　　if ( !bst ) 
　　　　printf("not found\n"); 
　　else {
　　　　if ( x < bst->element ) 
　　　　　　bst->left = delete( bst->left, x ); /* 从左子树递归删除 */
　　　　else if ( x > bst->element ) 
　　　　　　bst->right = delete( bst->right, x ); /* 从右子树递归删除 */
　　　　else { /* bst就是要删除的结点 */
　　　　　　/* 如果被删除结点有左右两个子结点 */ 
　　　　　　if ( bst->left && bst->right ) {
　　　　　　　　/* 从右子树中找最小的元素填充删除结点 */
　　　　　　　　tmp = findmin( bst->right );
　　　　　　　　bst->element = tmp->element;
　　　　　　　　/* 从右子树中删除最小元素 */
　　　　　　　　bst->right = delete( bst->right, bst->element );
　　　　　　}　else {
　　　　　　　　/* 被删除结点有一个或无子结点 */
　　　　　　　　tmp = bst; 
　　　　　　　　if( !bst->left ) /* 只有右孩子或无子结点 */
　　　　　　　　　　bst = bst->right; 
　　　　　　　　else /* 只有左孩子 */
　　　　　　　　　　bst = bst->left;
　　　　　　　　free( tmp );
　　　　　　}
　　　　} /* else  */
　　}
　　return bst;
}

position find( bintree bst , elementtype x )
{
　　if ( !bst ) return null; /*查找失败*/
　　if ( x > bst->element )
　　　　return find( bst->right, x ); /*在右子树中继续查找*/
　　else if ( x < bst->element )
　　　　return find( bst->left, x); /*在左子树中继续查找*/
　　else /* x == bst->element */
　　　　return bst; /*查找成功，返回结点的找到结点的地址*/
}

position findmin( bintree bst )
{
　　if ( !bst ) return null; /*空的二叉搜索树，返回null*/
　　else if ( !bst->left )
　　　　return bst; /*找到最左叶结点并返回*/
　　else
　　　　return findmin( bst->left ); /*沿左分支继续查找*/
}

position findmax( bintree bst )
{
　　if ( bst ) {
　　　　while( bst->right ) 
　　　　　　bst = bst->right;
　　　　　　/*沿右分支继续查找，直到最右叶结点*/
　　　　return bst;
　　}
}

void inordertraversal( bintree bst )
{
　　if ( bst ) {
　　　　inordertraversal( bst->left );
　　　　printf("%d", bst->element);
　　　　inordertraversal( bst->right );
　　}
}

void preordertraversal( bintree bt )
{
　　if( bt ) {
　　　　printf("%d ", bt->element);
　　　　preordertraversal( bt->left );
　　　　preordertraversal( bt->right );
　　}
} 

void preorderjudge( bintree bst )
{
　　if ( bst == null ) {
　　　　printf("empty tree!");
　　　　return;    
　　}　else if ( bst )  {
　　　　if ( bst->left ) {
　　　　　　/* 左儿子更大 */
　　　　　　if( bst->left->element >= bst->element )
　　　　　　　　return;
　　　　}
　　　　if ( bst->right ) {
　　   　　/* 右儿子更小 */
　　　　　　if ( bst->right->element <= bst->element )
　　　　　　　　return;
　　　　}    
　　　　preorderjudge( bst->left );
　　　　preorderjudge( bst->right );
　　}
}

 

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网