• 欢迎访问废江's博客 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏本站吧

搜索二叉树

算法笔记 站点默认 1个月前 (11-04) 23次浏览 已收录 1个评论
#include<bits/stdc++.h>
using namespace std;
typedef int ElementType ;
typedef struct tnode *BinTree;
typedef BinTree Position ;
struct tnode {
	ElementType Data;
	BinTree Left;
	BinTree Right;
};
Position FindMin( BinTree BST){
	if (!BST) return 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;
}
BinTree Insert( BinTree BST, ElementType X ) {
	if( !BST ) { 
		BST = (BinTree)malloc(sizeof(struct tnode));
		BST->Data = X;
		BST->Left = BST->Right = NULL;
	} else {
		if( X < BST->Data )
			BST->Left = Insert( BST->Left, X );   
		else  if( X > BST->Data )
			BST->Right = Insert( BST->Right, X ); 
		
	}
	return BST;
}
BinTree Delete( BinTree BST, ElementType X ) 
{ 
    Position Tmp; 
 
    if( !BST ) 
        printf("要删除的元素未找到"); 
    else {
        if( X < BST->Data ) 
            BST->Left = Delete( BST->Left, X );   /* 从左子树递归删除 */
        else if( X > BST->Data ) 
            BST->Right = Delete( BST->Right, X ); /* 从右子树递归删除 */
        else { /* BST就是要删除的结点 */
            /* 如果被删除结点有左右两个子结点 */ 
            if( BST->Left && BST->Right ) {
                /* 从右子树中找最小的元素填充删除结点 */
                Tmp = FindMin( BST->Right );
                BST->Data = Tmp->Data;
                /* 从右子树中删除最小元素 */
                BST->Right = Delete( BST->Right, BST->Data );
            }
            else { /* 被删除结点有一个或无子结点 */
                Tmp = BST; 
                if( !BST->Left )       /* 只有右孩子或无子结点 */
                    BST = BST->Right; 
                else                   /* 只有左孩子 */
                    BST = BST->Left;
                free( Tmp );
            }
        }
    }
    return BST;
}
BinTree Find( BinTree BST, ElementType X ) {
	if(!BST ) return NULL;
	if( X >BST->Data )
		return Find(BST->Right,X);
	else if(X<BST->Data)
		return Find(BST->Left,X);
	else
		return BST;
}
void preorder(BinTree BST){  //先序遍历 
	if(BST){
	printf("%d ",BST->Data);
	preorder(BST->Left);
	preorder(BST->Right);
}
}
void inorder(BinTree BST){  //中序遍历 
	if(BST){
	inorder(BST->Left);
	printf("%d ",BST->Data);
	inorder(BST->Right);
}
}
int main() {
    BinTree BST;
    BST=NULL;
//    int a[10];
//    for(int i=0;i<9;i++)
//    cin>>a[i];
//    for(int i=0;i<9;i++){
//    	BST=Insert(BST,a[i]);
//	}
	for(int i=0;i<9;i++){
    	BST=Insert(BST,i);
	}
    preorder(BST);
    cout<<endl;
    inorder(BST);
}

个人博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:搜索二叉树
喜欢 (4)
[]
分享 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到
(1)个小伙伴在吐槽