关于二叉树一些接口函数递归实现（有详细递归过程）

二叉树的前序遍历，前序遍历的顺序是，根，左子树，右子树

//二叉树的前序遍历
void PreOrnder(BTNode* root)
{
    if(root == NULL)
    {
        printf("NULl ");
        return;
    }
    printf("%c ",root->data);
    PreOrnder(root->left);
    PreOrnder(root->right);
}

二叉树的中序遍历，中序遍历的顺序是，左子树，根，右子树，下面是详细的递归过程

//二叉树的中序遍历
void InOrnder(BTNode* root)
{
    if(root == NULL)
    {
        printf("NULl ");
        return;
    }
    InOrnder(root->left);
    printf("%d ",root->data);

    InOrnder(root->right);
}

二叉树的后序遍历，遍历的顺序是左子树，右子树，根，比较类似于深度优先算法，DFS

//二叉树的后序遍历
void PostOrder(BTNode* root)
{
    if(root == NULL)
    {
        printf("NULl ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ",root->data);
}

如何计算二叉树的叶子个数，叶子的特性是左子树是NULL，右子树也是NULL，所以我们可以用递归遍历的方法，加个if判断，左子树是NULL，右子树也是NULL，则这个是叶子

//二叉树的叶子个数
int TreeLeafSize(BTNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    if(root->left == NULL && root->right == NULL)
    {
        return 1;
    }
    return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

寻找二叉树中的某个数，找到了返回那个数的地址，没有找到就返回NULL

//寻找二叉树中的某个数
BTNode* TreeFind(BTNode* root,BTDataType x)
{
    if(root == NULL)
    {
        return NULL;
    }
    if(root->data == x)
    {
        return root;
    }
    
   BTNode* lret = TreeFind(root->left, x);
    if(lret)
    {
        return lret;
    }
   BTNode* rret = TreeFind(root->right, x);
    if(rret)
    {
        return rret;
    }
    return  NULL;
}

 获取二叉树的节点个数，也是用递归来实现的，每递归到一个树的时候，只要不为空就返回1，把返回的1都加上再返回到调用这个函数的位置

int TreeSize(BTNode* root)
{
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right)+1;
}

查找第K层的节点个数，也是递归遍历，等递归到K层后，开始返回节点个数，跟上一个获取节点个数是一样的，只不过多了一个判断，到达K层才开始返回

//查找第K层的节点个数
int TreeKLevel(BTNode* root, int k)
{
    assert(k > 0);
    if(root == NULL)
    {
        return 0;
    }
    if(k == 1)
    {
        return 1;
    }
    return TreeKLevel(root->left, k-1)+TreeKLevel(root->right, k-1);
}

获取二叉树的最高高度

//二叉树的高度
int TreeHight(BTNode* root)
{
    if(root == NULL)
    {
        return 0;
    }
    int lh = TreeHight(root->left)+1;
    int rh = TreeHight(root->right)+1;
    return lh > rh ? lh : rh;
}

二叉树的层序遍历，层序遍历是比较像广度算法BFS的，实现过程需要有一个队列

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if(root)
    {
        QueuePush(&q, root);
    }
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%c ",front->data);
        if(front->left)
        {
            QueuePush(&q, front->left);
        }
        if(front->right)
        {
            QueuePush(&q, front->right);
        }
    }
    printf("
");
    QueueDestroy(&q);
}

//队列的几个接口代码

typedef BTNode* QDataType;
// 链式结构：表示队列
typedef struct QListNode
{
    struct QListNode* _next;
    QDataType _data;
}QNode;
 
// 队列的结构
typedef struct Queue
{
    QNode* _front;
    QNode* _rear;
    int size;
}Queue;

//队列的初始化
void QueueInit(Queue* q)
{
    assert(q);
    q->size = 0;
    q->_front = q->_rear = NULL;
}
// 删除队头
void QueuePop(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    
    if(q->_front->_next == NULL)
    {
        free(q->_front);
        q->_rear = q->_front = NULL;
        
    }
    else
    {
        QNode* del = q->_front;
        q->_front = del->_next;
        free(del);
        del = NULL;
    }
    q->size--;
}
// 获取队列头部元素
QDataType QueueFront(Queue* q)
{
    assert(q);
    assert(!QueueEmpty(q));
    
    return q->_front->_data;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0
int QueueEmpty(Queue* q)
{
    assert(q);
    if(q->_front == NULL && q->_rear == NULL)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}
// 队尾入队列
void QueuePush(Queue* q, QDataType data)
{
    assert(q);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if(newnode == NULL)
    {
        perror("Queuepush malloc fail");
        exit(-1);
    }
    else
    {
        newnode->_data = data;
        newnode->_next = NULL;
    }
    if(q->_rear == NULL)
    {
        q->_rear = q->_front = newnode;
    }
    else
    {
        q->_rear->_next = newnode;
        q->_rear = newnode;
        
    }
    q->size++;
}

​​​​​​​

判断这棵树是否完全二叉树，完全二叉树的特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。需要注意的是，满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树，这里还是用层序的方法去判断，如果一个二叉树在遍历到NULL的时候，后面还有，不是空的树出现。这棵树就一定不是完全二叉树。

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
    Queue q;
    QueueInit(&q);
    if(root)
    {
        QueuePush(&q, root);
    }
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if(front == NULL)
        {
            break;
        }
        QueuePush(&q, front->left);
        QueuePush(&q, front->right);
    }
    while(!QueueEmpty(&q))
    {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        if(front != NULL)
        {
            QueueDestroy(&q);
            return false;
        }
    }
    QueueDestroy(&q);
    return true;
}

通过遍历一个数组，根据数组里面的内容，来创建一棵树

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{
    if(a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    
    root->data = a[(*pi)];
    (*pi)++;
    root->left = BinaryTreeCreate(a,pi);
    root->right = BinaryTreeCreate(a,pi);
    
    return root;
}