#include<bits/stdc++.h> #define maxsize 100 using namespace std; typedef struct treenode {//定义二叉树结构 char data; struct node *lchild,*rchild; }*bitree,bitnode; //查找1 bitnode find( int x, bitree bst ) { if( !bst ) return null; /*查找失败*/ if( x > bst->data ) return find( x, bst->rchild ); /*在右子树中继续查找*/ else if( x < bst->data ) return find( x, bst->lchild ); /*在左子树中继续查找*/ else /* x == bst->data */ return bst; /*查找成功,返回结点的找到结点的地址*/ } //查找2(非递归) bitnode iterfind( int x, bitree bst ) { while( bst ) { if( x > bst->data ) bst = bst->rchild; /*向右子树中移动,继续查找*/ else if( x < bst->data ) bst = bst->lchild; /*向左子树中移动,继续查找*/ else /* x == bst->data */ return bst; /*查找成功,返回结点的找到结点的地址*/ } return null; /*查找失败*/ } //查最小(递归) bitnode findmin(bitree bst){ if(!bst) return null; else if(!bst->lchild) return bst; else return findmin(bst->lchild); } //查最大(迭代) bitnode findmax(bitree bst){ if(bst) while(bst->rchild) bst = bst->rchild; return bst; } //插入 bitree insert( int x, bitree bst ) { if( !bst ){ /*若原树为空,生成并返回一个结点的二叉搜索树*/ bst = malloc(sizeof(struct treenode)); bst->data = x; bst->lchild = bst->rchild = null; }else /*开始找要插入元素的位置*/ if( x < bst->data ) bst->lchild = insert( x, bst->lchild); /*递归插入左子树*/ else if( x > bst->data ) bst->rchild = insert( x, bst->rchild); /*递归插入右子树*/ /* else x已经存在,什么都不做 */ return bst; } //删除 bitree delete( int x, bitree bst ) { bitnode tmp; if( !bst ) printf("要删除的元素未找到"); else if( x < bst->data ) bst->lchild = delete( x, bst->lchild); /* 左子树递归删除 */ else if( x > bst->data ) bst->rchild = delete( x, bst->rchild); /* 右子树递归删除 */ else /*找到要删除的结点 */ if( bst->lchild && bst->rchild ) { /*被删除结点有左右两个子结点 */ tmp = findmin( bst->rchild ); /*在右子树中找最小的元素填充删除结点*/ bst->data = tmp->data; bst->rchild = delete( bst->data, bst->rchild); /*在删除结点的右子树中删除最小元素*/ } else { /*被删除结点有一个或无子结点*/ tmp = bst; if( !bst->lchild ) /* 有右孩子或无子结点*/ bst = bst->rchild; else if( !bst->rchild ) /*有左孩子或无子结点*/ bst = bst->lchild; free( tmp ); } return bst; }
分类: 未分类
0 条评论