首页 > 代码库 > C语言实现二叉树的基本操作

C语言实现二叉树的基本操作

       我在前面的博客中解说了链表、栈和队列。这些数据结构事实上都是线性表,而且给出了具体的实现。

从今天開始。我们将要来学习树,树作为一种数据结构我们常常会用到,作为起步和基础。我们先来实现二叉树。也就是每一个节点有不超过2个子节点的树。对于树的操作,最主要的创建、遍历、求树高、节点数等。代码上传至 https://github.com/chenyufeng1991/BinaryTree 。

(1)节点的定义

typedef struct BTNode{
    int data;
    struct BTNode *lChild;
    struct BTNode *rChild;
}BiTNode;


(2)二叉树的创建

//先序创建二叉树
int CreateBiTree(BiTNode **T)
{
    int ch;
    scanf("%d",&ch);
    if (ch == -1)
    {
        *T = NULL;
        return 0;
    }
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        if (T == NULL)
        {
            printf("failed\n");
            return 0;
        }
        else
        {
            (*T)->data = http://www.mamicode.com/ch;>


(3)先序遍历二叉树

//先序遍历二叉树
void PreOrderBiTree(BiTNode *T)
{
    if (T == NULL)
    {
        return;
    }
    else
    {
        printf("%d ",T->data);
        PreOrderBiTree(T->lChild);
        PreOrderBiTree(T->rChild);
    }
}



(4)中序遍历二叉树

//中序遍历二叉树
void MiddleOrderBiTree(BiTNode *T)
{
    if (T == NULL)
    {
        return;
    }
    else
    {
        MiddleOrderBiTree(T->lChild);
        printf("%d ",T->data);
        MiddleOrderBiTree(T->rChild);
    }
}



(5)兴许遍历二叉树

//兴许遍历二叉树
void PostOrderBiTree(BiTNode *T)
{
    if (T == NULL)
    {
        return;
    }
    else
    {
        PostOrderBiTree(T->lChild);
        PostOrderBiTree(T->rChild);
        printf("%d ",T->data);
    }
}



(6)二叉树的深度

//二叉树的深度
int TreeDeep(BiTNode *T)
{
    int deep = 0;
    if (T != NULL)
    {
        int leftdeep = TreeDeep(T->lChild);
        int rightdeep = TreeDeep(T->rChild);
        deep = leftdeep >= rightdeep?leftdeep+1:rightdeep+1;
    }

    return deep;
}



(7)叶子节点个数

//叶子节点个数
int LeafCount(BiTNode *T)
{
    static int count;
    if (T != NULL)
    {
        if (T->lChild == NULL && T->rChild == NULL)
        {
            count++;
        }

        LeafCount(T->lChild);
        LeafCount(T->rChild);
    }

    return count;
}



(8)測试函数

//主函数
int main(int argc,const char *argv[])
{
    BiTNode *T;
    int depth,leafCount = 0;
    printf("请输入第一个节点的值,-1表示没有叶节点:\n");
    CreateBiTree(&T);

    printf("先序遍历二叉树:");
    PreOrderBiTree(T);
    printf("\n");

    printf("中序遍历二叉树:");
    MiddleOrderBiTree(T);
    printf("\n");

    printf("兴许遍历二叉树:");
    PostOrderBiTree(T);
    printf("\n");

    depth = TreeDeep(T);
    printf("树的深度为:%d\n",depth);
    
    leafCount = LeafCount(T);
    printf("叶子节点个数:%d\n",leafCount);

    return 0;
}


C语言实现二叉树的基本操作