概述

之前讲解的数据结构都是一对一的线性结构，每个结点最多只有一个前驱和一个后继结点，但现实生活中，还有很多一对多的情况需要处理，所以我们需要研究一对多的数据结构。典型的一对多数据结构是*树（Tree）*，比如文件目录就是典型的树状结构。通过树的各种特性，可以解决编程中碰到的很多问题。

树（Tree）是n(n >= 0)个结点的有限集合，n = 0时称为空树。在任意一棵非空树中：
(1)有且仅有一个特定的称为根(Root)的结点；
(2)当n > 1时，其余结点可分为m(m > 0)个互不相交的有限集T1,T2,……Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree);
Alt text

注意两点：

  1. 根节点是唯一的；
  2. 子树互不相交；

相关概念

根结点：所有结点的根；
结点的度(Degree)：结点拥有有的子树个数称为结点的度；
树的度：树内各结点的度的最大值；
叶子结点（终端结点）：度为0的结点；
分支结点（非终端结点）：度不为0的结点；
孩子(Child)结点、双亲(Parent)结点、兄弟结(Sibling)点：结点的子树的根称为该结点的孩子，该结点称为孩子的双亲，同一个双亲的孩子之间互称为兄弟；
树的层次(Level)：从根开始，根为第一层，根的孩子为第二层，以此类推；
树的深度(Depth)：树中结点的最大层次；
树的顺序类型：如果树中各结点的孩子结点从左到右有序，则该称有序树，否则称为无序树；
Alt text

二叉树

二叉树是一种特殊的树，它的特点是每个结点最多有两个子树（即二叉树的度不能大于2），并且，二叉树的子树有左右之分，其次序不能颠倒。

一棵深度为k且有2^k -1 个结点的二叉树称为满二叉树，如下图所示。按图示结每个结点编号，如果有深度为k的，有n个结点的二叉树，如果其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应，则称之为完全二叉树。
Alt text
二叉树性质
性质1：在二叉树的第i层上最多有2^(i – 1)个结点
性质2：深度为k的二叉树至多有2^i – 1个结点
性质3：具有n个结点的完全二叉树的为log2n + 1
性质4：对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1

二叉树数据结构

对于二叉树，可以把它当成具有两个指针域的链表来看待，两个指针域分别指向自己左右孩子结点，所以二叉树的数据结构按如下方式定义：

typedef int type_t;
typedef struct node
{
    type_t data;        /*数据域*/
    struct node *left;  /*左结点指针*/
    struct node *right; /*右结点指针*/
}Node;

二叉树操作接口

创建结点

/*创建二叉树结点*/
Node *node_create(type_t data)
{
    Node *p = (Node *)malloc(sizeof(Node));
    assert(p);
    p->data = data;
    p->left = NULL;
    p->right = NULL;
    return p;
}

插入结点

对于结点的插入，需要考虑将结点插入到树的左边还是右边，对此，我们以有序二叉树来举例。有序二叉树是指，左结点、根结点、右结点有明确大小关系的树，比如，左结点不大于根结点，右结点不小于根结点。下面我们来实现有序二叉树的两种插入方法，以左结点<=根结点<=右结点的顺序进行插入。
Alt text

/*非递归法，将结点插入到有序二叉树*/
void node_insert(Node **pTree, Node *pNode)
{
    if(*pTree == NULL)  /*空树*/
    {
        *pTree = pNode;
    }
    else
    {
        Node *p = *pTree;
        Node *parent = NULL;
        while(p != NULL)
        {
            parent = p;     /*保存该结点的双亲结点*/
            if(pNode->data <= p->data)  /*插入到该结点的左边*/
            {
                p = p->left;
            }
            else /*右边*/ 
            {
                p = p->right;
            }
        }
        if(pNode->data <= parent->data)
            parent->left = pNode;
        else
            parent->right = pNode;
    }
}

/*递归法，将结点插入到有序二叉树*/
void node_insert_by_recursion(Node **pTree, Node *pNode)
{
    if(*pTree == NULL)
    {
        *pTree = pNode;
    }
    else
    {
        if(pNode->data <= (*pTree)->data) /*递归对左子树进行插入操作*/
        {
            node_insert_by_recursion( &((*pTree)->left) , pNode);
        }
        else    /*右子树*/
        {
            node_insert_by_recursion( &((*pTree)->right) , pNode);
        }
    }
}

遍历结点

二叉树的结点遍历是一个非常重要的话题，按照遍历顺序的不同，有三种比较典型的遍历方法，如下：
前序遍历：先访问根结点，再遍历左子树，再遍历右子树
中序遍历：先遍历左子树，再访问根结点，再遍历右子树
后序遍历：先遍历左子树，再访问右子树，再遍历根结点

/*前序遍历二叉树并打印*/
void tree_pre_order(Node *tree)
{
    if(tree == NULL)
    {
        return;
    }
    else
    {
        printf("%d ", tree->data);
        tree_pre_order(tree->left);
        tree_pre_order(tree->right);
    }
}

/*中序遍历二叉树并打印*/
void tree_in_order(Node *tree)
{
    if(tree == NULL)
    {
        return;
    }
    else
    {
        tree_in_order(tree->left);
        printf("%d ", tree->data);
        tree_in_order(tree->right);
    }
}

/*后序遍历二叉树并打印*/
void tree_post_order(Node *tree)
{
    if(tree == NULL)
    {
        return;
    }
    else
    {
        tree_post_order(tree->left);
        tree_post_order(tree->right);
        printf("%d ", tree->data);
    }
}

查找结点

/*非递归法，查找结点*/
Node *tree_search(Node *tree, int data)
{
    Node *p = tree;
    while(p != NULL)
    {
        if(p->data == data)
            return p;
        else if(data < p->data)
            p = p->left;
        else
            p = p->right;
    }
    return p;
}

/*递归法，查找结点*/
Node *tree_search_by_recursion(Node *tree, int data)
{
    if(tree == NULL)
        return NULL;
    else if(tree->data == data)
        return tree;
    else if(data < tree->data)
        return tree_search_by_recursion(tree->left, data);
    else
        return tree_search_by_recursion(tree->right, data);
}

求二叉树的高度

/*求二叉树高度*/
int tree_height(Node *tree)
{
    if(tree == NULL)
        return 0;
    int lh = tree_height(tree->left); /*求左子树高度*/
    int rh = tree_height(tree->right);/*求右子树高度*/
    if(lh < rh)
        return rh + 1;
    else
        return lh + 1;
}

删除结点

/*删除结点*/
void node_delete(Node **pTree, int data)
{
    Node *pFind = *pTree;
    Node *pParent = NULL;
    Node *pDelete = NULL;
    /*查找要删除的结点及其父结点*/
    while(pFind != NULL)
    {
        if(pFind->data == data)
            break;
        else if(data < pFind->data)
        {
            pParent = pFind;
            pFind = pFind->left;
        }
        else
        {
            pParent = pFind;
            pFind = pFind->right;
        }
    }
    if(pFind == NULL)/*查找完毕，未找到要删除的数据*/
    {
        return;
    }
    else if(pFind->left == NULL)  /*要删除的结点没有左子树，则直接将右子树的数据移过来*/
    {
        if(pParent == NULL) /*待删除结点是根结点*/
        {
            *pTree = pFind->right;
        }
        else
        {        
            if(pParent->left == pFind){
                pParent->left = pFind->right;
            }else{
                pParent->right = pFind->right;
            }
        }
        free(pFind);
        return;
    }
    else if(pFind->left->right == NULL)/*待删除结点的左子树没有右结点，则删除find->left结点*/
    {
        pDelete = pFind->left;
        pFind->data = pDelete->data;
        pFind->left = pDelete->left;
        free(pDelete);
        return;
    }
    else /*待删除结点的右子树至少有一个结点，需要查找到右子树的最右结点，将其删除*/
    {
        pParent = pFind->left;
        pDelete = pParent->right;
        while(pDelete->right != NULL)
        {
            pParent = pDelete;
            pDelete = pDelete->right;
        }
        pParent->right = pDelete->left;
        pFind->data = pDelete->data;
        free(pDelete);
        return;
    }
}

销毁二叉树

/*销毁二叉树*/
void tree_destroy(Node **pTree)
{
    if(*pTree == NULL)
        return;
    Node *tree = *pTree;
    tree_destroy(&(tree->left));
    tree_destroy(&(tree->right));
    printf("delete %d\n", tree->data);
    free(tree);
    *pTree = NULL;
}

测试代码

int main()
{
    int i;
    Node *p = NULL;
    Node *tree = NULL;
    int a[] = {12, 10, 9, 11, 14, 13, 15, 16};
    /*创建结点将插入到二叉树*/
    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        p = node_create(a[i]);
        printf("%d:%p\n", a[i], p);
        node_insert_by_recursion(&tree, p);
    }
    /*中序遍历*/
    printf("in order:");
    tree_in_order(tree);
    printf("\n");
    /*循环查找*/
    p = tree_search(tree, 13);
    printf("13:%p\n", p);
    /*递归查找*/
    p = tree_search_by_recursion(tree, 13);
    printf("13:%p\n", p);
    /*打印树的高度*/
    printf("tree height:%d\n", tree_height(tree));
    /*删除结点*/
    for(i = 0; i < sizeof(a) / sizeof(a[0]); i++)
    {
        printf("delete:%d\n", a[i]);
        node_delete(&tree, a[i]);
        printf("in order:");
        tree_in_order(tree);
        printf("\n");
    }
    /*销毁树*/
    tree_destroy(&tree);
    return 0;
}

  • 无标签