概念

树的数据元素之间的关系是一对多，每个节点最多有一个前驱，但可以有多个后继。
1.度数：一个节点的子树的个数称为该节点的度数
2.树度数：树中节点的最大度数
3.叶节点或终端节点: 度数为零的节点
4.节点层次: 根节点的层次为1，根节点子树的根为第2层，以此类推
5.树的深度或高度: 树中所有节点层次的最大值

二叉树

二叉树每个根节点最多有两个子节点，而且子节点严格区分左右子节点，根节点只有一个子节点时也要区分左右。

二叉树的性质

1.二叉树第k（k>=1）层上的节点最多为2的k-1次幂个。
2.深度为k（k>=1）的二叉树最多有2的k次幂-1个节点。
3.在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。

满二叉树

深度为k（k>=1）时节点为2k-1。

完全二叉树

只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。

二叉树的顺序存储

完全二叉树的编号方法是从上到下，从左到右。设完全二叉树的节点数为n，根节点编号为1.某一节点编号为i，该节点的左节点编号为2i，右节点的编号为2i+1。
不完全二叉树通过添加虚节点构成完全二叉树，然后用数组存储，这要浪费一些存储空间。

二叉树的遍历

前序：根、左、右
中序：左、根、右
后序：左、右、根

二叉树的链式存储

结构体

typedef char datatype_tree;
typedef struct tree_node_t
{
    datatype_tree data;         // 数据域
    struct tree_node_t *lchild; // 左子left
    struct tree_node_t *rchild; // 右子right
} bitree_node_t, *bitree_list_t;

和单向链表相比，二叉树的链式存储的结构体的指针域又分为左节点和右节点的指针。

创建一棵有n个节点的树

bitree_list_t CreateBitree(int n, int i)
{
    bitree_node_t *r = (bitree_node_t *)malloc(sizeof(bitree_node_t));
    if (r == NULL)
    {
        perror("r malloc error");
        return NULL;
    }
    r->data = i;
    if (2 * i <= n)
        r->lchild = CreateBitree(n, 2 * i);
    else
        r->lchild = NULL;
    if (2 * i + 1 <= n)
        r->rchild = CreateBitree(n, 2 * i + 1);
    else
        r->rchild = NULL;
    return r;
}

1.开辟一个节点的空间
2.判断是否有左节点
3.判断是否有右节点

前序遍历

void PreOrder(bitree_list_t r)
{
    if (r == NULL)
        return;
    printf("%d ", r->data);
    if (r->lchild != NULL)
        PreOrder(r->lchild);
    if (r->rchild != NULL)
        PreOrder(r->rchild);
}

中序遍历

void InOrder(bitree_list_t r)
{
    if (r == NULL)
        return;
    if (r->lchild != NULL)
        InOrder(r->lchild);
    printf("%d ", r->data);
    if (r->rchild != NULL)
        InOrder(r->rchild);
}

后序遍历

void PostOrder(bitree_list_t r)
{
    if (r == NULL)
        return;
    if (r->lchild != NULL)
        PostOrder(r->lchild);
    if (r->rchild != NULL)
        PostOrder(r->rchild);
    printf("%d ", r->data);
}

删除

void Delete(bitree_list_t r)
{
    if (r == NULL)
        return;
    if (r->lchild != NULL)
        Delete(r->lchild);
    if (r->rchild != NULL)
        Delete(r->rchild);
    free(r);
    r = NULL;
}

概念

二叉树