二叉树的基本操作(创建，遍历，求高度，叶子节点个数...)

首先，说一些简单的概念：

二叉树：

• 一棵二叉树是结点的一个有限集合，该集合或者为空，或者是一个根结点加上两颗分别称为左子树和右子树的二叉树组成。

二叉树的特点：

• 每个结点最多有两棵子树，即二叉树不存在度大于2 的结点
• 二叉树的子树有左右之分，其子树的次序不能颠倒

//BTree.h
#pragma once
#include<assert.h>
#include<malloc.h>
#include<stdio.h>

#define NULL 0
typedef char BDataType;
typedef struct BTNode
{
    struct BTNode* pLift;
    struct BTNode* pRight;
    BDataType data;
}BTNode;


void CreateBinTree(BTNode** pRoot, char* str, int size, int* index, BDataType invalid);//创建二叉树
void PreOrder(BTNode* pRoot);//前序遍历
void InOrder(BTNode* pRoot);//中序遍历
void PostOrder(BTNode* pRoot);//后序遍历
void PreOrderNor(BTNode* pRoot);//非递归前序遍历
void PreOrderNorTwo(BTNode* pRoot);
void InOrderNor(BTNode* pRoot);//非递归 中序遍历
void InOrderNor2(BTNode* pRoot);
void PostOrderNor(BTNode* pRoot);//非递归   后序遍历
BTNode* CopyBinTree(BTNode* pRoot);//拷贝二叉树
void DestroyBinTree(BTNode** pRoot);//销毁二叉树  后序
int GetBTNodeCount(BTNode* pRoot);//求二叉树节点的个数
int GetLeafNodeCount(BTNode* pRoot);//求叶子节点的个数
int GetKLevelNodeCount(BTNode* pRoot, int K);//求第K层叶子节点个数
int Hight(BTNode* pRoot);//求二叉树的深度
//BTNode* LeftChild(BTNode* pRoot, BTNode* pNode, int* k);//获取一个节点的左孩子节点
//BTNode* RightChild(BTNode* pRoot, BTNode* pNode, int* k);//获取一个节点的右孩子节点
BTNode* LeftChild(BTNode* pNode);
BTNode* RightChild(BTNode* pNode);
void LevelOrder(BTNode* pRoot);//层序遍历
int ISBTNodeInBinTree(BTNode* pRoot, BTNode* pNode);//判断一个节点是否在一颗二叉树中
BTNode* GetBTNodeParent(BTNode* pRoot, BTNode* pNode);//获取一个节点的双亲

void MirrorBinTree(BTNode* pRoot);//求二叉树的镜像  递归
void MirrorBinTreeNor(BTNode* pRoot);//求二叉树的镜像  非递归
int IsCompleteBinTree(BTNode* pRoot);//判断一棵二叉树是否为完全二叉树

//BTree.c
#include"BTree.h"
#include"Queue.h"
#include"stack.h"

BTNode* BuyBTNode(BDataType data)
{
    BTNode* NewNode = (BTNode*)malloc(sizeof(BTNode));
    if (NewNode == NULL)
    {
        assert(0);
        return;
    }
    NewNode->data = data;
    NewNode->pLift = NULL;
    NewNode->pRight = NULL;
    return NewNode;
}

void CreateBinTree(BTNode** pRoot, char* str, int size, int* index, BDataType invalid)//创建二叉树

{
    //BTNode *NewNode = NULL;
    assert(pRoot);
    assert(index);

    if (*index < size && invalid != str[*index])
    {
        //根节点
        (*pRoot) = BuyBTNode(str[*index]);
        //左子树
        ++(*index);
        CreateBinTree(&(*pRoot)->pLift, str, size, index, invalid);
        //右子树
        ++(*index);
        CreateBinTree(&(*pRoot)->pRight, str, size, index, invalid);
    }
}

void PreOrder(BTNode* pRoot)  //前序遍历  递归
{
    //assert(pRoot);
    if (pRoot)
    {
        printf("%c  ", pRoot->data);
        PreOrder(pRoot->pLift);
        PreOrder(pRoot->pRight);
    }
}

void InOrder(BTNode* pRoot)//中序遍历  递归
{
    if (pRoot)
    {

        InOrder(pRoot->pLift);
        printf("%c  ", pRoot->data);
        InOrder(pRoot->pRight);
    }
}

void PostOrder(BTNode* pRoot)//后序遍历  递归
{
    if (pRoot)
    {

        PostOrder(pRoot->pLift);

        PostOrder(pRoot->pRight);
        printf("%c  ", pRoot->data);
    }
}

void PreOrderNor(BTNode* pRoot)//非递归前序遍历
{
    Stack s;
    if (pRoot == NULL)
        return;
    StackInit(&s);
    StackPush(&s, pRoot);
    while (!StackEmpty(&s))
    {
        BTNode* pCur = StackTop(&s);
        StackPop(&s);
        printf("%c  ", pCur->data);
        if (pCur->pRight)
            StackPush(&s, pCur->pRight);
        if (pCur->pLift)
            StackPush(&s, pCur->pLift);


    }
}

void PreOrderNorTwo(BTNode* pRoot)
{
    Stack s;
    if (pRoot == NULL)
        return;
    StackInit(&s);
    StackPush(&s, pRoot);
    while (!StackEmpty(&s))
    {
        BTNode* pCur = StackTop(&s);
        StackPop(&s);
        while (pCur)
        {
            printf("%c  ", pCur->data);
            StackPush(&s, pCur->pRight);
            pCur = pCur->pLift;
        }
    }
}

void InOrderNor(BTNode* pRoot)//非递归 中序遍历
{
    Stack s;
    if (pRoot == NULL)
        return;
    StackInit(&s);
    BTNode* pCur = pRoot;
    while (!StackEmpty(&s)|| pCur)
    {
        if (pCur)
        {
            StackPush(&s, pCur);
            pCur = pCur->pLift;

        }
        else
        {
            pCur = StackTop(&s);
            printf("%c ", pCur->data);
            StackPop(&s);
            pCur = pCur->pRight;
        }
    }



}

void InOrderNor2(BTNode* pRoot)
{
    Stack s;
    if (pRoot == NULL)
        return;
    StackInit(&s);
    BTNode* pCur = pRoot;
    while (!StackEmpty(&s) || pCur)
    {
        while (pCur)
        {
            StackPush(&s, pCur);
            pCur = pCur->pLift;
        }

        pCur = StackTop(&s);
        printf("%c  ", pCur->data);
        StackPop(&s);
        pCur = pCur->pRight;
    }

}

void PostOrderNor(BTNode* pRoot)//非递归   后序遍历
{
    Stack s;
    BTNode* Top = NULL;
    BTNode* pPre = NULL;

    if (pRoot == NULL)
        return;
    StackInit(&s);
    BTNode* pCur = pRoot;
    while (!StackEmpty(&s) || pCur)
    {
        while (pCur)
        {
            StackPush(&s, pCur);
            pCur = pCur->pLift;
        }
        Top = StackTop(&s);
        if (Top->pRight == NULL || pPre == Top->pRight)
        {
            printf("%c  ", Top->data);
            pPre = Top;
            StackPop(&s);
        }
        else
        {
            pCur = Top->pRight;
        }
    }
}

BTNode* CopyBinTree(BTNode* pRoot)//拷贝二叉树
{
    BTNode* NewRoot = NULL;
    if (pRoot)
    {
        NewRoot = BuyBTNode(pRoot->data);
        NewRoot->pLift = CopyBinTree(pRoot->pLift);
        NewRoot->pRight = CopyBinTree(pRoot->pRight);

    }
    return NewRoot;
}

void DestroyBinTree(BTNode** pRoot)//销毁二叉树
{
    if (*pRoot)
    {
        DestroyBinTree(&(*pRoot)->pLift);
        DestroyBinTree(&(*pRoot)->pRight);
        free(*pRoot);
        *pRoot = NULL;
    }
}

int GetBTNodeCount(BTNode* pRoot)//求二叉树节点的个数
{
    if (pRoot == NULL)
        return 0;
    return GetBTNodeCount(pRoot->pLift) + GetBTNodeCount(pRoot->pRight) + 1;
}

int GetLeafNodeCount(BTNode* pRoot)//求叶子节点的个数
{
    if (pRoot == NULL)
        return 0;
    if (pRoot->pLift == NULL && pRoot->pRight == NULL)
        return 1;
    return GetLeafNodeCount(pRoot->pLift) + GetLeafNodeCount(pRoot->pRight);
}

int GetKLevelNodeCount(BTNode* pRoot, int K)//求第K层叶子节点个数
{
    if (pRoot == NULL || K < 0)
        return 0;
    if (K == 1)
        return 1;
    return GetKLevelNodeCount(pRoot->pLift, K - 1) + GetKLevelNodeCount(pRoot->pRight, K - 1);
}

int Hight(BTNode* pRoot)//求二叉树的深度
{
    if (pRoot == NULL)
        return 0;
    return Hight(pRoot->pLift) > Hight(pRoot->pRight) ? Hight(pRoot->pLift) + 1 : Hight(pRoot->pRight) + 1;
}
#if 0

BTNode* LeftChild(BTNode* pRoot,BTNode* pNode,int* k)//获取一个节点的左孩子节点   测试过的可行版  就是感觉有点绕
{
    BTNode* PNodeLift = NULL;
    if (pNode == NULL || pRoot == NULL)
        return 0;
    if (pNode == pRoot)
    { 
        (*k)++;
        return pRoot->pLift;
    }
        PNodeLift = LeftChild(pRoot->pLift, pNode, k);
    if (*k == 0)
    {
        PNodeLift = LeftChild(pRoot->pRight, pNode, k);
    }
    return PNodeLift;
}

BTNode* RightChild(BTNode* pRoot, BTNode* pNode, int* k)//获取一个节点的右孩子节点
{
    BTNode* PNodeRight = NULL;
    if (pNode == NULL || pRoot == NULL)
        return 0;
    if (pNode == pRoot)
    {
        (*k)++;
        return pRoot->pRight;
    }
    PNodeRight = RightChild(pRoot->pLift, pNode, k);
    if (*k == 0)
    {
        PNodeRight = RightChild(pRoot->pRight, pNode, k);
    }
    return PNodeRight;
}
#endif

//这个可能没有什么技术含量，接受吐槽
BTNode* LeftChild(BTNode* pNode)//获取一个节点的左孩子节点     
{
    return (pNode != NULL) ? pNode->pLift : NULL;
}

BTNode* RightChild(BTNode* pNode)//获取一个节点的右孩子节点
{
    return (pNode != NULL) ? pNode->pRight : NULL;
}

void LevelOrder(BTNode* pRoot)//层序遍历
{
    Queue q;
    assert(pRoot);
    QueueInit(&q);
    QueuePush(&q, pRoot);
    while (!(QueueEmpty(&q)))
    {
        BTNode* pCur = QueueFront(&q);
        printf("%c ", pCur->data);
        QueuePop(&q);
        if (pCur->pLift)
            QueuePush(&q, pCur->pLift);
        if (pCur->pRight)
            QueuePush(&q, pCur->pRight);

    }
}

int ISBTNodeInBinTree(BTNode* pRoot, BTNode* pNode)//判断一个节点是否在一颗二叉树中
{
    if (pRoot == NULL || pNode == NULL)
        return 0;
    if (pRoot == pNode)
        return 1;
    if (ISBTNodeInBinTree(pRoot->pLift, pNode))
        return 1;

    return ISBTNodeInBinTree(pRoot->pRight, pNode);
}

BTNode* GetBTNodeParent(BTNode* pRoot, BTNode* pNode)//获取一个节点的双亲
{
    BTNode* Parent = NULL;
    if (pRoot == NULL || pNode == NULL || (pRoot->pLift == NULL && pRoot->pRight == NULL))
        return NULL;
    if (pRoot->pLift == pNode || pRoot->pRight == pNode)
        return pRoot;
    if(Parent = GetBTNodeParent(pRoot->pLift, pNode))
        return Parent;
    return GetBTNodeParent(pRoot->pRight, pNode);

}


void Swap(BTNode** Lift, BTNode** Right)
{
    BTNode* tmp = *Lift;
    *Lift = *Right;
    *Right = tmp;
}

void MirrorBinTree(BTNode* pRoot)//求二叉树的镜像  递归
{
    if (pRoot == NULL || (pRoot->pLift == NULL && pRoot->pRight == NULL))
        return;

    Swap(&pRoot->pLift, &pRoot->pRight);
    MirrorBinTree(pRoot->pLift);
    MirrorBinTree(pRoot->pRight);

}

void MirrorBinTreeNor(BTNode* pRoot)//求二叉树的镜像  非递归
{
    Queue q;
    if (pRoot == NULL || (pRoot->pLift == NULL && pRoot->pRight == NULL))
        return;

    QueueInit(&q);
    QueuePush(&q, pRoot);
    while (!(QueueEmpty(&q)))
    {
        BTNode* pCur = QueueFront(&q);
        Swap(&pCur->pLift, &pCur->pRight);
        QueuePop(&q);
        if (pCur->pLift)
            QueuePush(&q, pCur->pLift);
        if (pCur->pRight)
            QueuePush(&q, pCur->pRight);

    }
}

int IsCompleteBinTree(BTNode* pRoot)//判断一棵二叉树是否为完全二叉树
{
    Queue s;
    int flag = 0;
    if (pRoot == NULL)
        return 1;
    QueueInit(&s);
    QueuePush(&s, pRoot);
    while (!(QueueEmpty(&s)))
    {
        BTNode* pCur = QueueFront(&s);
        QueuePop(&s);
        if (flag == 1)
        {
            if (pCur->pLift || pCur->pRight)
                return 0;
        }

        else
        {
            if (pCur->pLift && pCur->pRight)
            {
                QueuePush(&s, pCur->pRight);
                QueuePush(&s, pCur->pLift);
            }
            else if (pCur->pLift)
            {
                QueuePush(&s, pCur->pLift);
                flag = 1;
            }
            else if (pCur->pRight)
                return 0;
            else
                flag = 1;
        }

    }
    return 1;
}

上面有几个函数用到了栈和队列，这里没有给出栈和队列的函数，可以去之前有关栈的和队列的文章中查找，函数名都是一样的。
有疑问或者建议欢迎留言。