二叉树的建立、节点查找以及节点删除C和C++实现

程序是建立一颗二叉排序树，查找节点找到了返回其父节点，失败的时候返回NULL，删除节点分为四种情况：1、左子树和右子树都为空；2、左子树为空，右子树不为空；3、左子树不为空，右子树为空；4、左子树和右子树都不为空。

C语言版本（利用结构体实现）：

#include <stdio.h>
#include <stdlib.h>
 
typedef int DataType;
 
typedef struct BTree{
	DataType data;
	struct BTree *Tleft;
	struct BTree *Tright;	
}*BTree;

BTree CreateTree(); //建树 
BTree insert(BTree root, DataType data);//插入节点 
void InBTree(BTree root); //中序遍历 
void PreBTree(BTree root); //先序遍历 
void PostBTree(BTree root);//后序遍历 
BTree findPostion(BTree root, int deleteNode, int *flags);//寻找合适的插入点 
BTree delNode(BTree root, BTree parent, int flags); //删除树节点 

int main(){
	BTree root = NULL;
	int flags = 0;
	int deleteNode = 0; 
	BTree parent = NULL;//所删除节点的父节点 
	char choiceAgain = 'Y'; 
	root = CreateTree();
	printf("\n中序遍历: ");
	InBTree(root); 
	printf("\n前序遍历: "); 
	PreBTree(root);
	printf("\n后序遍历: ");
	PostBTree(root);
	printf("\n"); 
	
	do{	
		printf("需要删掉的节点: ");
		scanf("%d", &deleteNode); 
		parent = findPostion(root, deleteNode, &flags);
		root = delNode(root, parent, flags); 
		printf("删除后的结果: "); 
		printf("\n中序遍历: ");
		InBTree(root); 
		printf("\n前序遍历: ");
		PreBTree(root); 
		printf("\n后序遍历: ");
		PostBTree(root);
		choiceAgain = 'N';
		printf("\nDelete Again(Y) or N?: ");
		getchar(); 
		scanf("%c", &choiceAgain); 
	}while(choiceAgain == 'Y' || choiceAgain == 'y'); 
	
	printf("\nDone!\n"); 
	return 0; 
}

BTree CreateTree(){
	BTree root = NULL;
	DataType temp = 0;
	printf("请输入节点,以0结尾:\n"); 
	scanf("%d", &temp); 
	while(temp != 0){
	    root = insert(root, temp);	
		scanf("%d", &temp);  
	}
	
	return root; 
} 

BTree insert(BTree root, DataType data){
	BTree ptr = root;
	BTree tempNode; 
	BTree newNode = (BTree)malloc(sizeof(struct BTree)); 
	newNode->data = data ;
	newNode->Tleft = NULL;
	newNode->Tright = NULL;
	
	if(ptr == NULL){
		return newNode; 
	}else{
		while(ptr != NULL){
			tempNode = ptr; 
			if(ptr->data >= data){
				ptr = ptr->Tleft; 
			}else{
				ptr = ptr->Tright; 
			} 
		} 
		
		if(tempNode->data >= data){
			tempNode->Tleft =  newNode; 
		}else{
			tempNode->Tright =  newNode; 
		} 
	}
	return root; 
}

BTree findPostion(BTree root, int deleteNode, int *flags){
 	BTree parentNode = root;
	BTree temp = root; 
	*flags = 0;
	
	while(temp != NULL){
		if(temp->data == deleteNode){
			return parentNode;		 
		}else{
			parentNode = temp; 
			if(temp->data > deleteNode){
				temp = temp->Tleft;
				*flags = -1; 
			}else{
				temp = temp->Tright; 
				*flags = 1;
			}
		} 	 
	}
	
	return NULL; 
} 

BTree delNode(BTree root, BTree parent, int flags){
	BTree deleteNode = NULL;
	 
	if(parent == NULL){
		printf("未找到删除的节点!\n");
		return root; 
	}
	
	switch(flags){
	case -1:
		deleteNode = parent->Tleft;
		break;
	case 0:
		deleteNode = parent;
		break;
	case 1: 
		deleteNode = parent->Tright;
		break;
	default:
		printf("ERROR!\n"); 
		exit(1); 
	}
	
	if(deleteNode->Tleft == NULL && deleteNode->Tright == NULL){
		if(parent->Tleft == deleteNode){
			parent->Tleft = NULL; 
		}else if(parent->Tright == deleteNode){
			parent->Tright = NULL; 
		}else{
			parent = NULL; 
		} 
		free(deleteNode);
	}else if(deleteNode->Tleft == NULL && deleteNode->Tright != NULL){
		if(deleteNode->data == root->data){
			root = deleteNode->Tright; 
		}else{
			if(parent->Tleft->data == deleteNode->data){
				parent->Tleft = deleteNode->Tright;
			}else{
				parent->Tright = deleteNode->Tright;
			}
		} 
		free(deleteNode);
	}else if(deleteNode->Tleft != NULL && deleteNode->Tright == NULL){
		if(deleteNode->data == root->data){
			root = deleteNode->Tleft;
		}else{
			if(parent->Tleft->data == deleteNode->data){
				parent->Tleft = deleteNode->Tleft;
			}else{
 				parent->Tright = deleteNode->Tleft;
			}
		}
		free(deleteNode);
	}else{
		BTree temp = deleteNode->Tleft;
		BTree tempParent = deleteNode;
		while(temp->Tright != NULL){
			tempParent = temp;
			temp = temp->Tright;
		}
		
		deleteNode->data = temp->data;
		if(tempParent->Tleft == temp){
			tempParent->Tleft = temp->Tleft;	
		}else{
			tempParent->Tright = temp->Tleft;
		}
		
		printf("temp = %d\n", temp->data);
		free(temp);
	} 
	
	return root; 	
} 

void InBTree(BTree root){
	if(root != NULL){
		InBTree(root->Tleft); 
		printf("%d ", root->data); 
		InBTree(root->Tright);
	}
}

void PreBTree(BTree root){
	if(root != NULL){
		printf("%d ", root->data); 
		PreBTree(root->Tleft); 
		PreBTree(root->Tright);
	}
} 

void PostBTree(BTree root){
	if(root != NULL){
		PostBTree(root->Tleft); 
		PostBTree(root->Tright);
		printf("%d ", root->data);
	}
} 

C++版本(利用类实现)

#include <iostream.h>
#include <cstring>

typedef int KeyType;
#define NUM 11
class BinStree;
class BinSTreeNode
{
public:
    KeyType key;
    BinSTreeNode *lchild;
    BinSTreeNode *rchild;
    BinSTreeNode()
    {
        lchild = NULL;
        rchild = NULL;
    }
};

class BinSTree
{
public:
    BinSTreeNode *root;
    BinSTree()
    {
        root = NULL;
    }
    ~BinSTree()
    {
        //delete root;
    }
    BinSTreeNode *BSTreeSearch( BinSTreeNode *bt, KeyType k, BinSTreeNode *&p );
    void BSTreeInsert( BinSTreeNode *&bt, KeyType k );
    int BSTreeDelete( BinSTreeNode *&bt, KeyType k );
    void BSTreePreOrder(BinSTreeNode *bt);
    bool IsEmpty()
    {
        return root == NULL;
    }
};

/**
  *  二叉树排序查找算法
  *  在根指针为bt的二叉排序树中查找元素k的节点，若查找成功，则返回指向该节点的指针
  *  参数p指向查找到的结点，否则返回空指针，参数p指向k应插入的父结点
  */
BinSTreeNode* BinSTree::BSTreeSearch( BinSTreeNode *bt, KeyType k, BinSTreeNode *&p )
{
    BinSTreeNode *q = NULL;
    q = bt;
    while(q)
    {
        p = q;
        if( q->key == k )
        {
            return(p);
        }
        if( q->key > k )
            q = q->lchild;
        else
            q = q->rchild;
    }
    return NULL;
}

/**
  *  二叉排序树的插入节点算法
  *  bt指向二叉排序树的根结点，插入元素k的结点
  */
void BinSTree::BSTreeInsert( BinSTreeNode *&bt, KeyType k )
{
    BinSTreeNode *p = NULL, *q;
    q = bt;
    if( BSTreeSearch( q, k, p ) == NULL )
    {
        BinSTreeNode *r = new BinSTreeNode;
        r->key = k;
        r->lchild = r->rchild = NULL;
        if( q == NULL )
        {
            bt = r;         //被插入节点做为树的根节点
        }
        if( p && k < p->key )
            p->lchild = r;
        else if( p )
            p->rchild = r;
    }
}
/**
 * 中序遍历 
 */ 
void BinSTree::BSTreePreOrder(BinSTreeNode *bt)
{
    if(bt != NULL)
    {
        cout << bt->key << " ";
        BSTreePreOrder(bt->lchild);
        BSTreePreOrder(bt->rchild);
    }
}
/**
  * 二叉排序树的删除结点算法
  * 在二叉排序树中删除元素为k的结点，*bt指向二叉排序树的根节点
  * 删除成功返回1，不成功返回0.
  */
int BinSTree::BSTreeDelete( BinSTreeNode *&bt, KeyType k )
{
    BinSTreeNode *f, *p, *q, *s;
    p = bt;
    f = NULL;
    //查找关键字为k的结点，同时将此结点的双亲找出来
    while( p && p->key != k )
    {
        f = p;
        if( p->key > k )
            p = p->lchild;
        else
            p = p->rchild;
    }
    if( p == NULL )   //找不到待删除的结点时返回
        return 0;
    if( p->lchild == NULL )  //待删除结点的左子树为空
    {
        if( f == NULL )  //待删除结点为根节点
            bt = p->rchild;
        else if( f->lchild == p )  //待删结点是其双亲结点的左节点
            f->lchild = p->rchild;
        else
            f->rchild = p->rchild;  //待删结点是其双亲结点的右节点
        delete p;
    }
    else                    //待删除结点有左子树
    {
        q = p;
        s = p->lchild;
        while( s->rchild )  //在待删除结点的左子树中查找最右下结点
        {
            q = s;
            s = s->rchild;
        }
        if( q == p )
            q->lchild = s->lchild;
        else
            q->rchild = s->lchild;

        p->key = s->key;
        delete s;
    }
    return 1;
}
int main( void )
{
    int a[NUM] = { 34, 18, 76, 13, 52, 82, 16, 67, 58, 73, 72 };
    int i;
    BinSTree bst;
    BinSTreeNode *pBt = NULL, *p = NULL, *pT = NULL;

    for( i = 0; i < NUM; i++ )
    {
        bst.BSTreeInsert( pBt, a[i] ); //创建二叉排序树
    }
    pT = bst.BSTreeSearch( pBt, 52, p ); //搜索排序二叉树
    bst.BSTreePreOrder(pBt);
    cout << endl;
    bst.BSTreeDelete( pBt, 13 );   //删除无左孩子的情况
    bst.BSTreePreOrder(pBt);
    cout << endl;
    bst.BSTreeDelete( pBt, 76 );   //删除有左孩子的情况
    bst.BSTreePreOrder(pBt);
    cout << endl;
    return 0;
}