本篇内容主要讲解“c++二叉搜索树怎么实现”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“c++二叉搜索树怎么实现”吧!
创新互联专注为客户提供全方位的互联网综合服务，包含不限于成都网站设计、网站建设、莒南网络推广、小程序设计、莒南网络营销、莒南企业策划、莒南品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；创新互联为所有大学生创业者提供莒南建站搭建服务，24小时服务热线：18982081108，官方网址：www.cdcxhl.com
// http://blog.csdn.net/fansongy/article/details/6798278/
#include
#include
using namespace std;
typedef struct treenode
{
int data;
struct treenode *left;
struct treenode *right;
}TREE_NODE;//节点
typedef struct Bstree
{
TREE_NODE* root;
int size;
}BSTREE;//二叉树
BSTREE* create_tree() //创建
{
BSTREE* tree = new(BSTREE);
tree->root = NULL;
tree->size = 0;
return tree;
}
TREE_NODE* create_node(int data) //创建节点
{
TREE_NODE* node =new(TREE_NODE);
node->data = data;
node->left = NULL;
node->right = NULL;
}
void insert(TREE_NODE* node, TREE_NODE** root) //插入一个节点到那个位置
{
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 <left);
PreOrderTraverse(root->right);
}
}
void InOrderTraverse(TREE_NODE* root) //中序遍历
{
if(root)
{
InOrderTraverse(root->left);
cout << root->data <right);
}
}
void PostOrderTraverse(TREE_NODE * root) //后序遍历
{
if(root)
{
PostOrderTraverse(root->left);
PostOrderTraverse(root->right);
cout << root->data <root);
(tree->size)++;
}
TREE_NODE** bstree_find(int data, TREE_NODE** root) //查找DATA 对应的位置
{
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) //删除 该节点
{
delete(node);
}
bool bstree_erase(int data, BSTREE* tree) //树中 插入 传入的是地址 如果想修改 这一地址变量就要 根据地址的地址 修改
{
TREE_NODE** node = bstree_find(data, & tree->root);
if(*node)
{
TREE_NODE* temp = *node;
if( ((*node)->right==NULL) &&((*node)->left==NULL))//如果为叶子节点
{
*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中最大的数顶替已经删除的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中最小的数顶替已经删除的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) //清楚节点
{
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;
}
vectorvec;
vec.push_back(root);
int cur=0;
int last =1;
while(curdata<<" ";
if(vec[cur]->left != NULL)
{
vec.push_back(vec[cur]->left);
}
if(vec[cur]->right != NULL)
{
vec.push_back(vec[cur]->right);
}
++cur;
}
cout<vec;
vec.push_back(root);
int cur=0;
while(curdata<<" ";
if(vec[cur]->left != NULL)
{
vec.push_back(vec[cur]->left);
}
if(vec[cur]->right != NULL)
{
vec.push_back(vec[cur]->right);
}
++cur;
}
cout<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<root)<root);
cout << "destroy the tree:\n";
bstree_destroy(tree);
return 0;
}
到此，相信大家对“c++二叉搜索树怎么实现”有了更深的了解，不妨来实际操作一番吧！这里是创新互联网站，更多相关内容可以进入相关频道进行查询，关注我们，继续学习！
新闻名称：c++二叉搜索树怎么实现
本文地址：
http://www.cdkjz.cn/article/ghohgs.html
