二叉查找树(数据结构篇)

数据结构之二叉查找树

二叉查找树(二叉排序树)

概念：

• 二叉树的一个重要应用是它们在查找中的使用—二叉查找树
• 二叉查找树每个节点的值都不同，以后再处理值相同的情况
• 对于二叉查找树的每个节点，它的左子树中所有关键字值小于该节点的关键字值，而它的右子树中所有的关键字值大于该节点的关键字值
• 该数的所有元素可以用某种统一的方式排序----二叉查找树有序
• 二叉查找树的平均深度为O(logN)
• 二叉查找树应该用中序遍历方式遍历

代码:

struct binarysearch{
    int data;
    binarysearch* left;
    binarysearch* right;
};

binarysearch* createNode(int data){
    auto p=new binarysearch;
    p->data=data;
    p->right=NULL;
    p->left=NULL;
    return p;
}


//插入节点
binarysearch* insert(binarysearch* &root,int data){
    if (NULL==root){
        binarysearch* add= createNode(data);
        root=add;
    }else if(data<root->data){
        root->left= insert(root->left,data);
    }else if(data>root->data){
        root->right= insert(root->right,data);
    }
    return root;
}


//查找,直接判断大小然后递归分树查找(小就左子树，大就右子树，不然就是中间的树根节点)
binarysearch* Search(binarysearch* root,int data){
    if(NULL==root){
        return NULL;
    }
    if(data<root->data){
        return Search(root->left,data);
    } else if(data>root->data){
        return Search(root->right,data);
    }else{
        return root;
    }
}


//查找树的最小值,二叉查找树只需顺着左子树一路到最左就是最小
int findmin(binarysearch* root){
//    递归形式
    if(NULL==root){
        return root->data;
    }
    if(root->left==NULL){
        return root->data;
    }else{
        return findmin(root->left);
    }

    //非递归形式
//    if(NULL!=root){
//        while (root->left!=NULL){
//            root=root->left;
//        }
//    }else{
//        return NULL;
//    }
//    return root->data;
}

//查找树的最大值，二叉查找树只需顺着右子树一路到最右就是最大
int findmax(binarysearch* root){
    //递归形式
//    if(NULL==root){
//        return NULL;
//    }
//    if(root->right==NULL){
//        return root->data;
//    }else{
//        return findmax(root->right);
//    }

    //非递归形式
    if(NULL!=root){
        while (root->right!=NULL){
            root=root->right;
        }
    }else{
        cout<<"树没有数据"<<endl;
    }
    return root->data;
}


//遍历(使用中序遍历)
void inorderprint(binarysearch* root){
    if(NULL == root){
        return;
    }
    inorderprint(root->left);
    cout<<root->data<<" ";
    inorderprint(root->right);
}

//删除节点，如果只有一个节点就分析是左子树还是右子树，然后将子树代替该根节点
//如果既有左节点(子树)和右节点(子树)，就找到右子树的最小值节点代替该根节点！
binarysearch* del(binarysearch* &root,int data){
    if(NULL==root){
        return NULL;
    }else if(data<root->data){
        root->left= del(root->left,data);
    }else if(data>root->data){
        root->right=del(root->right,data);
    }else if(root->left&&root->right){     //找寻右子树的最小值节点，删除最小值节点只有两种情况就是只有右子树(节点)或者没有节点。
        int temp= findmin(root->right);
        root->data=temp;
        root->right=del(root->right,temp);
    }else{   //只有一个子节点或者没有子节点的情况
        binarysearch* p=root;
        if(NULL==root->left){
            root=root->right;
        }else if(NULL==root->right){
            root=root->left;
        }
        delete p;
    }
    return root;
}


//清空树
binarysearch* destroy(binarysearch* &root){
    if(NULL!=root){
        destroy(root->left);
        destroy(root->right);
        delete root;
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

尾言

完整版笔记也就是数据结构与算法专栏完整版可到我的博客进行查看，或者在github库中自取(包含源代码)

• 博客1： codebooks.xyz
• 博客2：moonfordream.github.io
• github项目地址：Data-Structure-and-Algorithms