数据结构之二叉树（C语言附详细代码）

一，树和二叉树

1.树

①定义

②关于树的一些概念

④二叉树的存储结构(顺序结构,只适用于完全二叉树)

一，树和二叉树

1.树

①定义

树的存储结构是层次结构，即一对多的数据结构，每棵树都有一个根结点，和若干个子结点与没有子节点的叶结点。树的定义：

树(Tree)是n(n≥0)个结点的有限集合。n=0时称为空树。在任意

一棵非空树中：(1)有且只有一个特定的称为根(Root)的结点；

(2)当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1,T2

,Tm，其中每一个集合本身又是一棵树，并且称为根的子树；

其中有子树T1:以结点B为子树根节点；有子树T2，以结点C为根节点。

②关于树的一些概念

度：结点拥有多少子树，结点的度就是多少；树的度为树内结点中度的最大值。

结点关系：结点称作双亲，结点的子节点称作孩子，根结点只作为双亲，叶结点只作为孩子。

层次：结点的层次从根开始定义，根为第一层，根下的子结点为第二层，然后依次向下排，叶结点为最后一层；树的结点的最大层次为树的深度或称高度。

叶结点：度为0的结点。

分支节点：度不为0的结点。

内部节点：除根和叶以外的结点。

2.二叉树

①定义

如果一棵树的每个结点的度最大为2，且结点的孩子是严格左右区分的，那么它就是一个二叉 $2^{k-1}$ 树。二叉树的定义：

二叉树是n(n≥0)个结点的有限集合，该集合或者为空集(空二叉树)，

或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和

右子树的二叉树组成。

上图所示的树就是一个二叉树。

②特殊的二叉树

二叉树中有两种比较特殊的，分别为完全二叉树和满二叉树；

满二叉树，顾名思义：树中所有的分支结点都存在左子树和右子树，所有的叶子都在同一层上，这样的树叫做满二叉树。

完全二叉树理解起来相对来说比较困难，但是我们只需要记住完全二叉树的特点，不必要去深究为什么这样就是完全二叉树；

完全二叉树中，结点得度不一定都是2，它的叶结点只能出现在最下面两层，也就是说最下面两层才能有度小于2的结点，且最下面一层的叶结点必须都位于左侧位置；如果倒数第二层有叶子结点，必须都是右侧子树。

③二叉树的性质

性质1：二叉树的第k层(k≥1)上最多有 $2^{k-1}$ 个结点。

性质2：二叉树高度为k，该二叉树中结点最多时有 $2^{k}-1$ 个，高度为k的完全二叉树结点最小有 $2^{k-1}$ 个。

性质3：在任意一个二叉树中，令 $n_{0}$ 等于度为0结点的数量，令 $n_{1}$ 等于度为1的结点数量，令 $n_{2}$ 等于度为2的结点数量，设该二叉树的总结点为，各结点数量之间有如下关系：

$n=n_{0}+n_{1}+n_{2}$ ;

$n_{0}=n_{2}+1$ ;

④二叉树的存储结构(顺序结构,只适用于完全二叉树)

完全二叉树结点的编号方法是从上到下，从左到右；如下两图：

结点与结点之间的编号关系一目了然；

⑤二叉树的遍历

前序遍历：根->左->右；

以上图为例：从根节点开始->输出A，然后找到左子树->输出B，再以B为子根，找到B的左子树->输出D，再以D为子根，找到D的左子树->输出H，然后找到D的右子树->输出I，同样的输出E；

然后到根A的右子树C，同样循环上述操作，右侧输出为CFJG；

总输出顺序为：A-B-D-H-I-E-C-F-J-G;

中序遍历：左->根->右；

通过顺序A->B->D->H,找到最左的H，并输出H，然后返回，输出H的子根D，然后找到D的右子树I并输出，然后继续输出D的子根B，找到B的右子树E并输出，然后找到B的根A并输出；

然后找根A的右子树C，然后通过顺序C->F->J找到J，并对右侧进行相同操作；

最后输出为:H-D-I-B-E-A-J-F-C-G；

通过中序遍历可以清楚的得出结点的左右位置；

后序遍历：左->右->根；

同样的，通过顺序A->B->D->H,找到最左的H，并输出H，然后返回输出H的同层次同根的结点I并输出，最后输出子根D，继续找D的同层次同子根结点E并输出，最后再输出子根B，然后找到与B同层次同根的结点C，然后通过C->F->J的顺序找到J，并重复上述操作；

最后的输出顺序：H-I-D-E-B-J-F-G-C-A;

二，二叉树操作代码

1.头文件

二叉树中除了根结点和叶结点以外，其他结点都具有左子树(lchild)或右子树(rchlid),并且所有的结点都需要一个区域来存储数据，由此我们可以设计出二叉树的结构体；

typedef char tree_datatype;
typedef struct tree_t
{
    tree_datatype data; //数据域
    struct tree_t *lchild; //指向左子树的结构体指针
    struct tree_t *rchild; //指向右子树的结构体指针
}bitree_t;

2.函数代码

①创建二叉树

二叉树的创建和遍历都需要用到函数的递归思想；

输入时，输入连续的字符串，可以理解为，先把二叉树的左侧部分的结点的左子树从上到下，全部创建完之后(叶结点输入#时表示无子树)，再从下到上创建左侧部分结点的右子树，然后创建右侧部分结点的左子树，最后创建右侧部分结点的右子树。

//1.创建一个树
bitree_t *CreateBitree(void)
{
    char ch;
    bitree_t *r = NULL;
    scanf("%c",&ch);
    if(ch == '#')
    {
        return NULL;
    }
    r = (bitree_t *)malloc(sizeof(bitree_t));
    if(NULL == r)
    {
        printf("create failn");
    }

    r->data = ch;
    r->lchild = CreateBitree();
    r->rchild = CreateBitree();
    return r;
}

②前序遍历二叉树

首先传入树的首地址，判断是否为空，非空则输出数据，然后循环本函数遍历左子树，根据前序遍历的特点：“根->左->右”，进行遍历输出；

//2.前序遍历树
void PreShowBitree(bitree_t *r)
{
    if(r == NULL)
    {
        return;
    }
    printf("%c",r->data);
    PreShowBitree(r->lchild);
    PreShowBitree(r->rchild);
}

③中序遍历二叉树

首先传入树的首地址，判断是否为空，非空则循环本函数遍历左子树，根据中序遍历的特点：“左->根->右”，进行遍历输出；

//3.中序遍历树
void midShowBitree(bitree_t *r)
{
    if(r == NULL)
    {
        return;
    }
    midShowBitree(r->lchild);
    printf("%c",r->data);
    midShowBitree(r->rchild);
}

④后序遍历二叉树

首先传入树的首地址，判断是否为空，非空则循环本函数遍历左子树，根据后序遍历的特点：“左->右->根”，进行遍历输出；

//4.后序遍历树
void PostShowBitree(bitree_t *r)
{
    if(r == NULL)
    {
        return;
    }
    PostShowBitree(r->lchild);
    PostShowBitree(r->rchild);
    printf("%c",r->data);
}

⑤层次遍历二叉树

层次遍历即从上到下，从左到右进行输出；

层次遍历需要使用学习队列时的函数，先让根结点入队，循环内先让根结点出队，然后让根结点的左子树入队，右子树入队，然后左子树出队，左子树的左子树入队，左子树的右子树入队，然后右子树出队，右子树的左子树和右子树分别入队，然后进行循环，直到队列为空，循环结束；

//5.层次遍历
void levelShowBitree(bitree_t *r)
{
    if (r == NULL)
    {
        return;
    }
    //创建队列
    queue_t *p = CreateQueue();
    //根节点入队
    IntoQueue(p,r);
    while(!isEpQueue(p))
    {
        //节点出队
        r = OutQueue(p);
        printf("%c",r->data);
        if(r->lchild != NULL)
        {
            IntoQueue(p,r->lchild);
        }
        if(r->rchild != NULL)
        {
            IntoQueue(p,r->rchild);
        }
    }
}

如果本文中存在代码逻辑，代码完善，解释不通或不清楚的错误，还请批评指正。