二叉树-白红宇

二叉树

阅读量：4918 次

发布时间：2019-06-11

本文共 9104 字，大约阅读时间需要 30 分钟。

　　今天介绍二叉树，主要介绍c的代码实现，更多关于二叉树的概念，大家可以百度或者看书。

先介绍二叉树的存储结构

typedef struct node{    int data;    struct node * left;    struct node * right;} Node;typedef struct tree{    Node * root;} Tree;

Node节点的data是数据域，left，right是指针域。

Tree节点里只记录了root，也就是根。当然可以增加一些其他信息。

先说查找操作，因为之后的很多函数都会用。

//这个结构体是为了方便插入删除操作，child是找到的节点，parent是父节点typedef struct pair{    Node * parent;    Node * child;} Pair;

这个结构体主要是为了删除操作使用的，因为删除时我们要知道删除节点的父亲。而插入操作只要找到插入位置就可以了。

static Pair search_node(Tree * tree, const int key){    Pair pair;    pair.parent = NULL;//parent一直是child的父节点    pair.child = tree->root;        while ( pair.child != NULL )    {        if ( pair.child->data > key )//如果当前结点的值大于key，则向左查找        {            pair.parent = pair.child;            pair.child = pair.child->left;        }        else if ( pair.child->data  < key )//如果当前节点的值小于key，则向右查找        {            pair.parent = pair.child;            pair.child = pair.child->right;        }        else//如果相等，直接返回Pair结构体，结构体中的child就是找到的结点        {            return pair;        }    }    return pair;}

这个函数会返回一个pair结构体

如果找到关键字节点。child指向该节点，parent是该节点的父亲。

否则，child为NULL，parent是child的父亲节点。（如果是插入操作，parent的左孩子或者右孩子就是插入位置）

插入操作。

void t_insert(Tree * tree, const int data){    Pair pair;    pair = search_node(tree, data);//找到要插入的位置        if ( pair.parent == NULL )//第一次插入        tree->root = make_node(data);    else if (pair.child != NULL)//是否存在该节点        return;//存在则插入失败    else    {        if ( pair.parent->data > data)//根据新节点与父节点的比较，决定新节点的插入位置            pair.parent->left = make_node(data);        else            pair.parent->right = make_node(data);    }}

因为我们已经实现了查找功能。所以插入变的非常容易。先判断是不是根节点，再判断是否存在该元素。最后就是根据元素的大小判断插入位置。（这里不是必须左孩子比右孩子小）

查找函数就不介绍了。只是调用了search_node函数。

接下来介绍删除操作。

相比较插入而言，删除操作有点难度，但难度并不大。

首先要找到删除节点。然后将他的孩子连接到父亲上，释放删除节点内存就OK了。

这里分两种情况。删除节点有左右孩子，和只有一个孩子或者没有孩子。

一个孩子或者没有孩子的情况好处理，只要把这个孩子的父亲变成删除节点的父亲就可以了。

如果删除节点的有两个孩子。我们可以把左孩子的父亲变成右孩子的子树中最小的值。（右孩子的左子树的左子树…）

根据我们之前的对插入操作，我们可以知道，以某一节点为根，这棵树上的最小值一定是他的左子树的左子树…（while ( current->left != NULL ) current = current->left;）

当然这里还有其他方法，稍后会介绍一种叫替换的方法。里面涉及到删除点和真正的删除点。他是红黑树里使用的删除方法。

void t_remove(Tree * tree, const int key) {
        Pair pair = search_node(tree, key);     Node * current;     if ( pair.child == NULL )//没有找到关键字         return;     if ( pair.child->left && pair.child->right )     {
            current = pair.child->right;         while ( current->left != NULL )//找到删除节点左孩子的新位置             current = current->left;         current->left = pair.child->left;         if ( pair.parent )         {
                if ( pair.parent->left == pair.child )                 pair.parent->left = pair.child->right;             else                 pair.parent->right = pair.child->right;         }         else             tree->root = pair.child->right;     }     else     {
            if ( pair.parent )         {
                if ( pair.child->left )//只有左孩子             {
                    if ( pair.parent->left == pair.child )                     pair.parent->left = pair.child->left;                 else                     pair.parent->right = pair.child->left;             }             else//右孩子或者没有孩子             {
                    if ( pair.parent->left == pair.child )                     pair.parent->left = pair.child->right;                 else                     pair.parent->right = pair.child->right;             }         }         else         {
                if ( pair.child->left )                 tree->root = pair.child->left;               else                 tree->root = pair.child->right;           }     }         free(pair.child);

最后是二叉树的遍历

static void treaverse_node(Node * current, void (*func)(Node * current)){    if ( current == NULL )        return;    else//递归，中序遍历二叉树    {        treaverse_node(current->left, func);        func(current);        treaverse_node(current->right, func);    }}

前序遍历：根，左，右

中序遍历：左，根，右

后序遍历：左，右，根

我们可以简单的理解成，把func放到两个递归函数的前面就是前序，中间是中序，后面是后续。

之后我还会介绍非递归的遍历算法。

源码

btree.h

#ifndef _TREE_H#define _TREE_H#define MAXDEPTH 10typedef struct node{    int data;    struct node * left;    struct node * right;} Node;typedef struct tree{    Node * root;} Tree;void t_init(Tree * tree);//初始化void t_insert(Tree * tree, const int data);//添加Node* t_find(Tree * tree, const int key);//查找void t_remove(Tree * tree, const int key);//移除void t_treaverse(Tree * tree, void (*func)(Node * current));//遍历void t_destroy(Tree * tree);//销毁bool t_empty(Tree * tree);//为空int t_depth(Tree * tree);//深度Node* t_root(Tree * tree);//根int t_value(Node * current);//返回值#endif //_TREE_H

btree.c

#include 
     
      #include 
      
       #include 
       
        #include "btree.h"//这个结构体是为了方便插入删除操作，child是找到的节点，parent是父节点typedef struct pair{    Node * parent;    Node * child;} Pair;static Node* make_node(const int data);//创建static Pair search_node(Tree * tree, const int key);//查找static void treaverse_node(Node * current, void (*func)(Node * node));//遍历static void destroy_node(Node * current);//销毁static int depth_node(Node * current);//度void t_init(Tree * tree){    tree->root = NULL;}void t_insert(Tree * tree, const int data){    Pair pair;    pair = search_node(tree, data);//找到要插入的位置        if ( pair.parent == NULL )//第一次插入        tree->root = make_node(data);    else if (pair.child != NULL)//是否存在该节点        return;//存在则插入失败    else    {        if ( pair.parent->data > data)//根据新节点与父节点的比较，决定新节点的插入位置            pair.parent->left = make_node(data);        else            pair.parent->right = make_node(data);    }}Node* t_find(Tree * tree, const int key){    return search_node(tree, key).child;} void t_remove(Tree * tree, const int key) {
        Pair pair = search_node(tree, key);     Node * current;     if ( pair.child == NULL )//没有找到关键字         return;     if ( pair.child->left && pair.child->right )     {
            current = pair.child->right;         while ( current->left != NULL )//找到删除节点左孩子的新位置             current = current->left;         current->left = pair.child->left;         if ( pair.parent )         {
                if ( pair.parent->left == pair.child )                 pair.parent->left = pair.child->right;             else                 pair.parent->right = pair.child->right;         }         else             tree->root = pair.child->right;     }     else     {
            if ( pair.parent )         {
                if ( pair.child->left )//只有左孩子             {
                    if ( pair.parent->left == pair.child )                     pair.parent->left = pair.child->left;                 else                     pair.parent->right = pair.child->left;             }             else//右孩子或者没有孩子             {
                    if ( pair.parent->left == pair.child )                     pair.parent->left = pair.child->right;                 else                     pair.parent->right = pair.child->right;             }         }         else         {
                if ( pair.child->left )                 tree->root = pair.child->left;               else                 tree->root = pair.child->right;           }     }         free(pair.child); } void t_treaverse(Tree * tree, void (*func)(Node * current)){    assert( tree != NULL );    treaverse_node(tree->root, func);}void t_destroy(Tree * tree){    treaverse_node(tree->root, destroy_node);}bool t_empty(Tree * tree){    return tree->root == NULL;}int t_depth(Tree * tree){    depth_node(tree->root);}Node* t_root(Tree * tree){    return tree->root;}int t_value(Node * current){    assert( current != NULL );    return current->data;}static Node* make_node(const int data){    Node * node = (Node *)malloc( sizeof(Node) );    if (node == NULL)        exit(0);        node->data = data;    node->left = NULL;    node->right = NULL;    return node;}static Pair search_node(Tree * tree, const int key){    Pair pair;    pair.parent = NULL;//parent一直是child的父节点    pair.child = tree->root;        while ( pair.child != NULL )    {        if ( pair.child->data > key )//如果当前结点的值大于key，则向左查找        {            pair.parent = pair.child;            pair.child = pair.child->left;        }        else if ( pair.child->data  < key )//如果当前节点的值小于key，则向右查找        {            pair.parent = pair.child;            pair.child = pair.child->right;        }        else//如果相等，直接返回Pair结构体，结构体中的child就是找到的结点        {            return pair;        }    }    return pair;}static void treaverse_node(Node * current, void (*func)(Node * current)){    if ( current == NULL )        return;    else//递归，中序遍历二叉树    {        treaverse_node(current->left, func);        func(current);        treaverse_node(current->right, func);    }}static void destroy_node(Node * current){    assert( current != NULL );    free( current );}static int depth_node(Node * current){    int m, n;    if ( current == NULL )//当节点为NULL时返回０        return 0;    else    {        m = depth_node(current->left);//计算左子树深度        n = depth_node(current->right);//计算右子树深度        if ( m > n )//返回大的子树深度            return m + 1;        else            return n + 1;    }}

好吧，里面还有一些函数没有介绍，不过都很简单。数据结构的书上都有讲。

感谢大家的阅读，如有错误，欢迎指正。

转载于:https://www.cnblogs.com/ITgaozy/p/5150911.html

你可能感兴趣的文章