C语言实现二叉树---＞二叉查找树

柔情只为你懂 2023-01-13 06:19 153阅读 0赞

# 声明 #

代码实现都是自己写的，而且没有借鉴别人的代码，也没有看任何教程，只看了下二叉树的具体定义，知道大概是个什么东西  
说这些只是为了说明下列代码实现肯定不是最优的，甚至在你们看来都是很垃圾的代码，不过没关系，因为这是我自己动脑筋写出来的，记录一下  
ps: 我C语言功底不好，才学几天

## 定义 ##

二叉查找树是二叉树中最简单的了

1.  若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2.  若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3.  任意节点的左、右子树也分别为二叉查找树。
4.  没有键值相等的节点（no duplicate nodes）。

![在这里插入图片描述][20210422152955895.png]

假设有一个节点，这个节点的左右节点都有值，那么它左边的节点一定小于它本身，它右边的节点一定大于它本身，就和上面的图一样 （我这里实现了可以有相同元素，相同的元素会放到右子树）

# C语言实现 #

分别创建三个文件

1.  bin\_tree.h
2.  bin\_tree.c
3.  bin\_tree\_main.c

## bin\_tree.h ##

#pragma once
    
    #ifndef __BIN_TREE_HEAD_FILE__
    
    #define __BIN_TREE_HEAD_FILE__
    
    #include <stdio.h>
    #include <stdlib.h>
    
    
    
    typedef struct _node Node;
    
    
    typedef struct _tree Tree;
    
    typedef int BOOL;
    
    #define TRUE 1
    
    #define FALSE 0
    
    Tree* Tree_create();
    
    void add(Tree *self, int data);
    
    BOOL remove_data(Tree *self, int data);
    
    void foreach(Tree *self, void (*callback)(int data));
    
    Node* find_node(Node *root, int data);
    
    static void add_node(Node *root, Node *node);
    
    static void foreach_node(Node *root, void (*callback)(int data));
    
    static BOOL remove_node(Node *node, Node *del_node);
    
    static Node* get_node();
    
    Node *find_max_node(Node *root);
    
    void delete_node(Node **node);
    
    int if_left_or_right(Node *node);
    
    #endif

## bin\_tree.c ##

**注意下，删除节点的方法的返回值不可用，就是没有赋值正确的值，读者拿到代码后可以自己实现下**

#include "bin_tree.h"
    
    typedef struct _node
    { 
        struct _node *right; // 左子树
        struct _node *left; // 右子树
        struct _node *parent; // 父节点
        int data; //保存的数据
    }Node;
    
    
    typedef struct _tree
    { 
        Node *root;
    }Tree;
    
    
    Tree* Tree_create()
    { 
        Tree *tree = (Tree*) malloc(sizeof(Tree));
        tree->root = NULL; // 初始化内存
        return tree;
    
    }
    
    Node *find_max_node(Node *root)
    { 
        Node *result = root;
        if( root && root->right )
        { 
            result = find_max_node(root->right);
        }
    
        return result;
    }
    
    void delete_node(Node **node)
    { 
        free(*node);
        *node = NULL;
    
    }
    
    // 判断当前节点是处于左子树还是右子树
    // 位于左子树返回 1
    // 位于右子树返回 2
    // 返回 0 没有根节点
    int if_left_or_right(Node *node)
    { 
        int result = 0;
        if( !node->parent )
        { 
            result = 0;
        } else if( node == node->parent->left )
        { 
            result = 1;
        } else if( node == node->parent->right )
        { 
            result = 2;
        }
        
        return result;
    }
    
    void add(Tree* self, int data)
    { 
        Node *c = get_node();
        c->data = data;
        if( self->root )
        { 
            add_node(self->root, c);
        } else 
        { 
            self->root = c;
        }
    
    }
    
    BOOL remove_data(Tree* self, int data)
    {    BOOL result = FALSE;
        Node *root = self->root;
        if( !root )
        { 
            return result;
        }
    
        // 找到要删除的节点
        Node *del_node = find_node(root, data);
        if( !del_node )
        { 
            return result;
        }
     
    
        if( root == del_node && !del_node->left && !del_node->right ) // 只有根节点
        { 
            self->root = NULL;
            delete_node(&root);
        } else if( root == del_node && root->left )
        { 
            Node *max_node = find_max_node(root->left);
            self->root = max_node;
            if( max_node != root->left ) 
            { 
                max_node->parent->right = max_node->left;
                max_node->left = root->left;
                //root->left->parent = max_node;
            }  
            max_node->right = root->right;
            max_node->parent = NULL;
            root->left->parent = max_node;
            if( root->right )
            { 
                root->right->parent = max_node;    
            }
            delete_node(&root);
        } else if( root == del_node && root->right )
        { 
            self->root = root->right;
            root->right->parent = NULL;
            delete_node(&root);
        } else
        { 
            result = remove_node(self->root, del_node);
        }
    
        return result;
    }
    
    void foreach(Tree* self, void (*callback)(int data))
    { 
    
        if( self->root )
        { 
            foreach_node(self->root, callback);
        }
    
    }
    
    static void add_node(Node* root, Node* node)
    { 
        if( node->data >= root->data && !root->right )
        { 
            root->right = node;
            node->parent = root;
        } else if( node->data < root->data && !root->left )
        { 
            root->left = node;
            node->parent = root;
        } else if( node->data >= root->data )
        { 
            add_node(root->right, node);
        } else if( node->data < root->data )
        { 
            add_node(root->left, node);
        }
    }
    
    Node* find_node(Node* root, int data)
    { 
        Node *result = NULL;
        if( !root )
        { 
            return result;
        }
        if( data == root->data )
        { 
            result = root;
        } else if( data > root->data && root->right )
        { 
            result = find_node(root->right, data);
        } else if( root->left )
        { 
            result = find_node(root->left, data);
        }
    
        return result;
    
    }
    
    static void foreach_node(Node* root, void (*callback)(int data))
    { 
        if( root->left )
        { 
            foreach_node(root->left, callback);
        }
        callback(root->data);
        if( root->right )
        { 
            foreach_node(root->right, callback);
        }
    }
    
    static BOOL remove_node(Node *node, Node *del_node)
    { 
    
       // 如果当前节点没有任何子节点则直接删除
        if( !del_node->left && !del_node->right )
        { 
            if( if_left_or_right(del_node) == 1 )
            { 
                del_node->parent->left = NULL;
                delete_node(&del_node);
                
            } else if ( if_left_or_right(del_node) == 2 )
            { 
                del_node->parent->right = NULL;
                delete_node(&del_node);
            }
        }
        // 如果当前节点有右节点或者左节点则让他的父节点指向它的孩子节点
        else if( del_node->left && !del_node->right )  // 有左子树但没有右子树
        {   
    
            if( if_left_or_right(del_node) == 1 )
            { 
                del_node->parent->left = del_node->left;
            } else if( if_left_or_right(del_node) == 2 )
            { 
                del_node->parent->right = del_node->left;
            }
            del_node->left->parent = del_node->parent;
            delete_node(&del_node);
        }
        else if( del_node->right && !del_node->left )  // 有右子树但没有左子树
        { 
            if( if_left_or_right(del_node) == 1 )
            { 
                del_node->parent->left = del_node->right;
            } else if( if_left_or_right(del_node) == 2 )
            { 
                del_node->parent->right = del_node->right; 
            }
            del_node->right->parent = del_node->parent;
            delete_node(&del_node);
        }
        // 如果当前节点又有左节点又有右节点则需要找到要删除节点左子树中最大的节点
        // 然后再删除当前节点
        else if( del_node->left && del_node->right )
        { 
            // 找到要删除的左子树的最大节点
            Node *max_node = find_max_node(del_node->left);
            if( if_left_or_right(del_node) == 1 )
            { 
                del_node->parent->left = max_node;
                if( del_node->left != max_node )
                { 
                    max_node->parent->right = max_node->left; // 最大节点肯定是在它父节点的右边，且最大节点没有右子树
                    max_node->left = del_node->left;
                    del_node->left->parent = max_node;
                }
                max_node->right = del_node->right;
                del_node->right->parent = max_node;
    
                delete_node(&del_node);
            } else if( if_left_or_right(del_node) == 2 )
            { 
                del_node->parent->right = max_node;
                if( del_node->left != max_node )
                { 
                    max_node->parent->right = max_node->left; // 最大节点肯定是在它父节点的右边，且最大节点没有右子树
                    max_node->left = del_node->left;
                    del_node->left->parent = max_node;
                }
                max_node->right = del_node->right;
                del_node->right->parent = max_node;
                delete_node(&del_node);
     
            }
        }
    
        return TRUE;
    }
    
    static Node* get_node()
    { 
        Node *node = (Node*) malloc(sizeof(Node));
        node->right = NULL;
        node->left = NULL;
        node->parent = NULL;
        return node;
    
    }

## bin\_tree\_main.c ##

#include "bin_tree.h"
    
    void print(int data);
    
    
    int main()
    { 
        Tree* tree = Tree_create();
        add(tree, 11);
        add(tree, 1);
        add(tree, 12);
        add(tree, 15);
        add(tree, 14);
        add(tree, 9);
        foreach(tree, print);
        printf("删除节点之后再遍历\n");
        remove_data(tree, 15);
        remove_data(tree, 9);
        remove_data(tree, 11);
        remove_data(tree, 1);
        remove_data(tree, 12);
        foreach(tree, print);
        return 0;
    }
    
    void print(int data)
    { 
        printf("%d\n", data);
    }

![在这里插入图片描述][20210422153604871.png]

[20210422152955895.png]: /images/20221022/14b6628ca98f45b894e485f565f0e28a.png
[20210422153604871.png]: /images/20221022/12b374e2414e405f8e3aead378755316.png