c++二叉查找树怎么使用

本篇内容介绍了"c++二叉查找树怎么使用"的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

在数据顺序存储时 如果无序我们用顺序查找， 有序时我们用折半查找法，插值查找法，斐波那契查找法。 但是当需要插入跟删除

时就需要用到链式

存储了 这时我们引入二叉排序树(二叉搜索树)。

线索二叉树node->left .data < node.data < node->right.data;

中序遍历时为递增数列 InOrderTraverse;

删除节点时 重点注意下；有4种

1.从node->left 找最大值替换node;

2.从node->right找最小值替换node;

3.将node->right整体移动到node->left最大值的右边；

4.将node->left整体移动到node->right最小值的左边；

不过考虑到树的深度最好采用前两种 这就设计到树的左右节点平衡的问题了AVL树

#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++二叉查找树怎么使用"的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注网站，小编将为大家输出更多高质量的实用文章！