c++二叉查找樹(shù)怎么使用
本篇內(nèi)容介紹了“c++二叉查找樹(shù)怎么使用”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！
網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)建站！專注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、微信小程序開(kāi)發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了安岳免費(fèi)建站歡迎大家使用！
在數(shù)據(jù)順序存儲(chǔ)時(shí) 如果無(wú)序我們用順序查找， 有序時(shí)我們用折半查找法，插值查找法，斐波那契查找法。 但是當(dāng)需要插入跟刪除
時(shí)就需要用到鏈?zhǔn)?/p>
存儲(chǔ)了 這時(shí)我們引入二叉排序樹(shù)(二叉搜索樹(shù))。
線索二叉樹(shù)node->left .data < node.data < node->right.data;
中序遍歷時(shí)為遞增數(shù)列 InOrderTraverse;
刪除節(jié)點(diǎn)時(shí) 重點(diǎn)注意下；有4種
1.從node->left 找最大值替換node;
2.從node->right找最小值替換node;
3.將node->right整體移動(dòng)到node->left最大值的右邊；
4.將node->left整體移動(dòng)到node->right最小值的左邊；
不過(guò)考慮到樹(shù)的深度最好采用前兩種 這就設(shè)計(jì)到樹(shù)的左右節(jié)點(diǎn)平衡的問(wèn)題了AVL樹(shù)
#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;//二叉樹(shù)
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) //插入一個(gè)節(jié)點(diǎn)到那個(gè)位置
{
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) //插入一個(gè)節(jié)點(diǎn)
{
insert(create_node(data), &tree->root);
(tree->size)++;
}
TREE_NODE** bstree_find(int data, TREE_NODE** root) //查找DATA 對(duì)應(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) //樹(shù)中 插入 傳入的是地址 如果想修改 這一地址變量就要 根據(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;
}
//下面是左右子樹(shù)都不為空 刪除時(shí)任一種情況 最好用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;//類似左子樹(shù)
}
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;//類似右子樹(shù)
}
del_node(s);
--tree->size;
}
//node的左右都不為空,直接將右邊整體移動(dòng)到左邊最大值下面
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的左右都不為空,直接將左邊邊整體移動(dòng)到右邊最小值下面
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++二叉查找樹(shù)怎么使用”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！
文章名稱：c++二叉查找樹(shù)怎么使用
本文路徑：http://www.chinadenli.net/article2/giddoc.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站營(yíng)銷、小程序開(kāi)發(fā)、ChatGPT、外貿(mào)建站、定制開(kāi)發(fā)、關(guān)鍵詞優(yōu)化
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)
