c语言用二叉链实现二叉树的创建、二叉树的先序/中序/后序递归遍历、统计二叉树的高度、统计结点的个数、叶子结点的个数、先序/中序非递归遍历、层序遍历等运算。

好的，下面我来为您介绍一下C语言如何用二叉链表实现二叉树的创建，以及实现二叉树的各种操作。

1. 二叉树的结构体定义

typedef struct BiTNode
{
    char data; // 数据域
    struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode, *BiTree;

2. 二叉树的创建

二叉树的创建可以采用递归的方式，每次递归创建左右子树。

void CreateBiTree(BiTree *T)
{
    char ch;
    scanf("%c", &ch);
    if(ch == '#') // 如果输入的是'#'，则表示该节点为空
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = ch;
        CreateBiTree(&((*T)->lchild)); // 递归创建左子树
        CreateBiTree(&((*T)->rchild)); // 递归创建右子树
    }
}

3. 二叉树的先序/中序/后序递归遍历

先序遍历：根节点 -> 左子树 -> 右子树

void PreOrderTraverse(BiTree T)
{
    if(T != NULL)
    {
        printf("%c ", T->data);
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}

中序遍历：左子树 -> 根节点 -> 右子树

void InOrderTraverse(BiTree T)
{
    if(T != NULL)
    {
        InOrderTraverse(T->lchild);
        printf("%c ", T->data);
        InOrderTraverse(T->rchild);
    }
}

后序遍历：左子树 -> 右子树 -> 根节点

void PostOrderTraverse(BiTree T)
{
    if(T != NULL)
    {
        PostOrderTraverse(T->lchild);
        PostOrderTraverse(T->rchild);
        printf("%c ", T->data);
    }
}

4. 统计二叉树的高度

二叉树的高度可以采用递归的方式，每次递归计算左右子树的高度，并取最大值。

int TreeHeight(BiTree T)
{
    int leftHeight, rightHeight;
    if(T == NULL)
        return 0;
    else
    {
        leftHeight = TreeHeight(T->lchild);
        rightHeight = TreeHeight(T->rchild);
        return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
    }
}

5. 统计节点的个数

节点的个数可以采用递归的方式，每次递归计算左右子树的节点个数，并加上根节点。

int NodeCount(BiTree T)
{
    if(T == NULL)
        return 0;
    else
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

6. 统计叶子节点的个数

叶子节点的个数可以采用递归的方式，如果当前节点是叶子节点，则返回1，否则返回左右子树叶子节点的个数之和。

int LeafCount(BiTree T)
{
    if(T == NULL)
        return 0;
    else if(T->lchild == NULL && T->rchild == NULL)
        return 1;
    else
        return LeafCount(T->lchild) + LeafCount(T->rchild);
}

7. 先序/中序非递归遍历

先序非递归遍历可以采用栈的方式，先入根节点，然后依次入栈右子树、左子树。每次出栈打印节点即可。

void PreOrderTraverse2(BiTree T)
{
    if(T == NULL)
        return;
    BiTree p;
    Stack stack;
    InitStack(&stack);
    Push(&stack, T);
    while(!StackEmpty(stack))
    {
        Pop(&stack, &p);
        printf("%c ", p->data);
        if(p->rchild != NULL)
            Push(&stack, p->rchild);
        if(p->lchild != NULL)
            Push(&stack, p->lchild);
    }
}

中序非递归遍历可以采用栈的方式，先入根节点和左子树，然后依次入栈右子树。每次出栈打印节点即可。

void InOrderTraverse2(BiTree T)
{
    if(T == NULL)
        return;
    BiTree p;
    Stack stack;
    InitStack(&stack);
    Push(&stack, T);
    while(!StackEmpty(stack))
    {
        while(GetTop(stack, &p) && p != NULL)
            Push(&stack, p->lchild);
        Pop(&stack, &p);
        if(!StackEmpty(stack))
        {
            Pop(&stack, &p);
            printf("%c ", p->data);
            Push(&stack, p->rchild);
        }
    }
}

8. 层序遍历

层序遍历可以采用队列的方式，先入根节点，然后依次入队左右子树。每次出队打印节点即可。

void LevelOrderTraverse(BiTree T)
{
    if(T == NULL)
        return;
    BiTree p;
    Queue queue;
    InitQueue(&queue);
    EnQueue(&queue, T);
    while(!QueueEmpty(queue))
    {
        DeQueue(&queue, &p);
        printf("%c ", p->data);
        if(p->lchild != NULL)
            EnQueue(&queue, p->lchild);
        if(p->rchild != NULL)
            EnQueue(&queue, p->rchild);
    }
}

以上就是C语言用二叉链表实现二叉树的各种操作的代码实现。