数据结构 - 树与二叉树

一.普通有序树的定义

1.树的概念及特性

二.二叉树的定义

1.二叉树的性质

2.二叉树的分类

        ①.满二叉树

             每一层的结点数都为最大值

        ②.完全二叉树

                完全二叉树是由满二叉树，从下向上，从右向左依次擦除若干个结点

3.二叉树的结构

三.链式二叉树的创建

1.链式二叉树的结构体定义

typedef int data_t;

typedef struct btreenode
{
    data_t data;                            //数据域
    struct btreenode *lchild,*rchild;       //左结点与右结点的指针
}btree_node_t;

2.二叉树的创建

/**
 * @description:            使用键盘输入，创建一个二叉树
 * @param           :       无
 * @return          :       创建的二叉树的根结点指针
*/
btree_node_t *Btree_Create(void)
{
    data_t ch;                  //存储键盘输入的数据
    btree_node_t *new;          //指向新创建的结点

    /* 1.键盘输入要创建的结点的 data域 的值 */
    scanf("%c",&ch);
    if('#' == ch)
        return NULL;
    else
    {
        /* 2.创建根结点 */
        new = (btree_node_t *)malloc(sizeof(btree_node_t));
        if(NULL == new)
        {
            perror("malloc error");
            return NULL;
        }

        /* 3.为根结点填充数据 */
        new->data = ch;

        /* 4.用相同的方法创建左子树 */
        new->lchild = Btree_Create();

        /* 5.用相同的办法创建右子树 */
        new->rchild = Btree_Create();
    }

    /* 6.返回根结点指针 */
    return new;
    
}

四.二叉树的遍历

1.先序序列、中序序列、后序序列

①.先序序列：

        第一次经过结点的时候，去访问这个结点

②.中序序列：

        第二次经过结点的时候，去访问这个结点

③.后续序列：

        第三次经过结点的时候，去访问这个结点

④.层次遍历

2.遍历算法

①.先序递归遍历算法

/**
 * @description:            二叉树的先序遍历递归算法
 * @param - t       :       要遍历二叉树的指针
 * @return          :       无
*/
void Pre_order(btree_node_t *t)
{
    /* 树不为空 */
    if(NULL != t)
    {
        /* 1.访问根结点 */
        printf("%c  ",t->data);

        /* 2.先序遍历左子树 */
        Pre_order(t->lchild);

        /* 3.先序遍历右子树 */
        Pre_order(t->rchild);
    }
}

②.中序递归遍历算法

/**
 * @description:            二叉树的中序遍历递归算法
 * @param - t       :       要遍历的二叉树的指针
 * @return          :       无
*/
void Mid_order(btree_node_t *t)
{
    /* 树不为空 */
    if(NULL != t)
    {
        /* 1.中序遍历左子树 */
        Mid_order(t->lchild);

        /* 2.访问根结点 */
        printf("%c  ",t->data);

        /* 3.中序遍历右子树 */
        Mid_order(t->rchild);
    }
}

③.后序递归遍历算法啊

/**
 * @description:            二叉树的后序遍历递归算法
 * @param - t       :       要遍历的二叉树的指针
 * @return          :       无       
*/
void Post_order(btree_node_t *t)
{
    /* 树不为空 */
    if(NULL != t)
    {
        /* 1.后序遍历左子树 */
        Post_order(t->lchild);

        /* 2.后序遍历右子树 */
        Post_order(t->rchild);

        /* 3.访问根结点 */
        printf("%c  ",t->data);
    }
}

④.层次遍历算法

/**
 * @description:            二叉树的层次遍历算法
 * @param - t       :       要遍历的二叉树的指针
 * @return          :       无
*/
void Level_order(btree_node_t *t)
{
    linkqueue_t *q;         //链式队列

    /* 一.初始化一个链式队列 */
    q = Linkqueue_Create();

    /* 二.开始层次遍历 */
    while(t != NULL)
    {
        /* 1.访问 t 指向的结点数据 */
        printf("%c  ",t->data);

        /* 2.若 t 的左指针不为空 ， 则入队 */
        if(t->lchild != NULL)
        {
            Linkqueue_In(q,t->lchild);
        }

        /* 3.当 t 的右指针不为空 ， 则入队 */
        if(t->rchild != NULL)
        {
            Linkqueue_In(q,t->rchild);
        }

        /* 4.队列不为空 ， 则出队 */
        if(!Linkqueue_is_empty(q))
            Linkqueue_Out(q,&t);
        else
            break;
    }
}

⑤.先序非递归遍历算法