c++二叉搜索樹怎么實現(xiàn)

本篇內(nèi)容主要講解“c++二叉搜索樹怎么實現(xiàn)”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“c++二叉搜索樹怎么實現(xiàn)”吧!

//  http://blog.csdn.net/fansongy/article/details/6798278/ 
#include <iostream>    
#include <vector>    
using namespace std;    
typedef struct treenode    
{    
    int data;    
    struct treenode *left;    
    struct treenode *right;    
}TREE_NODE;//節(jié)點(diǎn)    
typedef struct Bstree    
{    
    TREE_NODE* root;    
    int size;    
}BSTREE;//二叉樹    
BSTREE* create_tree() //創(chuàng)建    
{    
    BSTREE* tree = new(BSTREE);    
    tree->root = NULL;    
    tree->size = 0;    
    return tree;    
}    
TREE_NODE* create_node(int data) //創(chuàng)建節(jié)點(diǎn)    
{    
    TREE_NODE* node =new(TREE_NODE);    
    node->data = data;    
    node->left = NULL;    
    node->right = NULL;    
}    
void insert(TREE_NODE* node, TREE_NODE** root)  //插入一個節(jié)點(diǎn)到那個位置    
{    
    if(NULL == *root)    
    {    
        *root = node;    
    }    
    else    
    {    
        if(node->data > (*root)->data)    
        {    
            insert(node, & (*root)->right);    
        }    
        else    
        {    
            insert(node, &(*root)->left);    
        }    
    }    
}    
void PreOrderTraverse(TREE_NODE* root) //先序遍歷    
{    
    if(root)    
    {    
        cout << root->data <<endl;    
        PreOrderTraverse(root->left);    
        PreOrderTraverse(root->right);    
    }    
}    
void InOrderTraverse(TREE_NODE* root) //中序遍歷    
{    
    if(root)    
    {    
        InOrderTraverse(root->left);    
        cout << root->data <<endl;    
        InOrderTraverse(root->right);    
    }    
}    
void PostOrderTraverse(TREE_NODE * root) //后序遍歷    
{    
    if(root)    
    {    
        PostOrderTraverse(root->left);    
        PostOrderTraverse(root->right);    
        cout << root->data <<endl;    
    }    
}    
void bstree_insert(int data, BSTREE* tree) //插入一個節(jié)點(diǎn)    
{    
    insert(create_node(data), &tree->root);    
    (tree->size)++;    
}    
TREE_NODE** bstree_find(int data, TREE_NODE** root)  //查找DATA 對應(yīng)的位置    
{    
    if(NULL==*root)    
    {    
        return root;    
    }    
    if(data >(*root)->data)    
    {    
        return bstree_find(data,& (*root)->right);    
    }    
    else if(data < (*root)->data)    
    {    
        return bstree_find(data, & (*root)->left);    
    }    
    else    
    {    
        return root;    
    }
	
	//下面是非遞歸查找*root
	if(NULL==*root)
	{
		return root;
	}
	TREE_NODE* temp = *root;
	while(temp && ( temp->data !=data ))
	{
		if(data > temp->data)
		{
			temp = temp->right;
		}
		else if(data < temp->data)
		{
			temp = temp->left;
		}
		if(temp)
		{
			return &temp;
		}
		else
		{
			return &temp;
		}
	}
}    
void del_node(TREE_NODE* node) //刪除 該節(jié)點(diǎn)    
{    
    delete(node);    
}
  
bool bstree_erase(int data, BSTREE* tree)  //樹中 插入  傳入的是地址 如果想修改 這一地址變量就要 根據(jù)地址的地址 修改    
{    
    TREE_NODE** node = bstree_find(data, & tree->root);    
    if(*node)    
    {    
        TREE_NODE* temp = *node;
		if( ((*node)->right==NULL) &&((*node)->left==NULL))//如果為葉子節(jié)點(diǎn)
		{
			*node = NULL;
			del_node(temp);    
			--tree->size;
		}
		if(((*node)->right==NULL) &&((*node)->left!=NULL))//node的right為空
		{
			*node = (*node)->left;
			del_node(temp);    
			--tree->size;
		}
		else if(((*node)->right!=NULL) &&((*node)->left==NULL))//node的left為空
		{
			*node = (*node)->right;
			del_node(temp);    
			--tree->size;
		}
		//下面是左右子樹都不為空 刪除時任一種情況 最好用1 2 種
		
		//node的左右都不為空將left中最大的數(shù)頂替已經(jīng)刪除的node
        if(((*node)->left != NULL) && ((*node)->right != NULL))    
        {
			TREE_NODE* s = (*node)->left;
			while(s->right)
			{
				temp=s;
				s=s->right;
			}
			(*node)->data = s->data;
			if(temp != *node)
			{
				temp->righ = s->left;
			}
			else
			{
				temp->left =s->left;//類似左子樹
			}
			del_node(s);    
			--tree->size;
        }
		
		//node的左右都不為空將right中最小的數(shù)頂替已經(jīng)刪除的node
		if(((*node)->left != NULL) && ((*node)->right != NULL))    
        {
			TREE_NODE* s = (*node)->right;
			while(s->left)
			{
				temp=s;
				s=s->left;
			}
			(*node)->data = s->data;
			if(temp != *node)
			{
				temp->left = s->right;
			}
			else
			{
				temp->right =s->right;//類似右子樹
			}
			del_node(s);    
			--tree->size;
        }
		//node的左右都不為空,直接將右邊整體移動到左邊最大值下面
		if(((*node)->left != NULL) && ((*node)->right != NULL))    
        {
			TREE_NODE* s = (*node)->left;
			while(s->right)
			{
				s=s->right;
			}
			s->right = (*node)->right;
			*node = (*node)->left;
			del_node(s);    
			--tree->size;
        }
		//node的左右都不為空,直接將左邊邊整體移動到右邊最小值下面
		if(((*node)->left != NULL) && ((*node)->right != NULL))    
        {
			TREE_NODE* s = (*node)->right;
			while(s->left)
			{
				s=s->left;
			}
			s->left = (*node)->left;
			*node = (*node)->right;
			del_node(s);    
			--tree->size;
        }
        return true;    
    }    
    return false;    
}
 
void bstree_updata(BSTREE* tree,int old,int now) //新舊替換更新    
{    
    while(bstree_erase(old,tree))    
    {    
        bstree_insert(now,tree);    
    }    
}    
void clear_node(TREE_NODE** root)  //清楚節(jié)點(diǎn)    
{    
    if(*root)    
    {    
        clear_node(&(*root)->left);    
        clear_node(&(*root)->right);    
        del_node(*root);    
        *root = NULL;    
    }    
}    
void clear_tree(BSTREE* tree)  //clear_tree    
{    
    clear_node(&tree->root);    
    tree->size = 0;    
}    
void bstree_destroy(BSTREE* tree) //bstree_destroy    
{    
    clear_tree(tree);    
    delete(tree);    
}    
int bstree_size(BSTREE* tree) //大小    
{    
    return tree->size;    
}    
int bstree_deep(TREE_NODE* root)  //深度DEPTH    
{    
    if(root)    
    {    
        int Hleft = bstree_deep(root->left);    
        int Hright = bstree_deep(root->right);    
        return Hleft>Hright ? Hleft+1 : Hright+1;    
    }    
    return 0;    
}    
void printNodeByLevel(TREE_NODE* root) //層序遍歷    
{    
    if(root ==NULL)    
    {    
        return;    
    }    
    vector<TREE_NODE*>vec;    
    vec.push_back(root);    
    int cur=0;    
    int last =1;    
    while(cur<vec.size() )    
    {    
        last = vec.size();    
        while(cur<last)    
        {    
            cout<<vec[cur]->data<<" ";    
            if(vec[cur]->left != NULL)    
            {    
                vec.push_back(vec[cur]->left);    
            }    
            if(vec[cur]->right != NULL)    
            {    
                vec.push_back(vec[cur]->right);    
            }    
            ++cur;    
        }    
        cout<<endl;    
    }    
}   
void print(TREE_NODE* root)  
{  
    if(root==NULL)  
    {  
        return;  
    }  
    vector<TREE_NODE*>vec;  
    vec.push_back(root);  
    int cur=0;  
    while(cur<vec.size())  
    {  
        cout<<vec[cur]->data<<" ";  
        if(vec[cur]->left != NULL)  
        {  
            vec.push_back(vec[cur]->left);  
        }  
        if(vec[cur]->right != NULL)  
        {  
            vec.push_back(vec[cur]->right);  
        }  
        ++cur;  
    }  
    cout<<endl;  
}   
int main()    
{    
    BSTREE* tree = create_tree();    
    bstree_insert(5, tree);    
    bstree_insert(6, tree);    
    bstree_insert(2, tree);    
    bstree_insert(1, tree);    
    bstree_insert(4, tree);    
    bstree_insert(3, tree);    
    cout << "the level print:\n";    
    printNodeByLevel(tree->root);    
    cout << "the first print:\n";    
    PreOrderTraverse(tree->root);    
    cout << "the middle print:\n";    
    InOrderTraverse(tree->root);    
    cout << "the endl print:\n";    
    PostOrderTraverse(tree->root);    
    cout<<"the tree deep:\n";    
    cout<<bstree_deep(tree->root)<<endl;    
    bstree_erase(2,tree);    
    cout << "delete  num of 2:\n";    
    cout << "after delete 2  print:\n";    
    PreOrderTraverse(tree->root);    
    cout << "destroy the tree:\n";    
    bstree_destroy(tree);    
    return 0;    
}

到此，相信大家對“c++二叉搜索樹怎么實現(xiàn)”有了更深的了解，不妨來實際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！