二叉树实现的相关函数

1.二叉树的创建

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{   
 
    if (n==0||a[*pi] == '#')
    {   
        (*pi)++;
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->_data = a[(*pi)++];
    root->_left = BinaryTreeCreate(a, --n, pi);
    root->_right = BinaryTreeCreate(a, --n, pi);
    return root;
 
}

形参中BTDataType* a是自定义类型的数组，用与给二叉树的结点赋值，int n是数组元素的个数，int*pi是当前将要放入二叉树的元素的下标。本方法适用于用前序遍历的结果来创建二叉树。若采用别的遍历方式需修改代码中调用函数和数组赋值的位置。

2.二叉树的销毁

// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{
    if (root == NULL)
    {
        return;
    }
 
    if ((*root)->_left)
    {
        free((*root)->_left);
        (*root)->_left = NULL;
    }
 
    if ((*root)->_right)
    {
        free((*root)->_right);
        (*root)->_right = NULL;
    }
 
    free(*root);
    *root = NULL;
    return;
}

销毁采用后序遍历的方式，先销毁结点的左右子树，再销毁当前结点。若先销毁当前结点，无法找到该结点的左右子树的位置。

3.求二叉树结点的个数

 
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
 
    return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
 
}

采用后续遍历的方式，求出当前结点的左右子树的结点个数，相加后再加上当前结点（+1的由来）。

4.求叶子结点的个数

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
 
    if (root == NULL)
    {
        return 0;
    }
 
    if (root->_left==NULL && root->_right==NULL)
    {
        return 1;
    }
 
    return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
 
 
}

叶子结点是左右子树都为空且自己本身不为空的结点，由于此处需要通过访问左右子树来判断，所以在这之前必须判断当前结点是否为空。在当前结点有子结点的时候，则访问子树，返回子树的叶子结点个数。

5.求第k层结点的个数

// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
 
    if (root == NULL)
    {
        return 0;
    }
 
    if (k == 1)
    {
        return 1;
    }
 
    return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
 
 
}

对当前结点的第k层，就是对当前结点的子节点的第k-1层。对于结点为空的判断和对层的判断先后顺序不能修改，因为可能会有k==1的时候是空结点的情况，此时不应该加1.（即k=2的时候恰好是叶子结点的情况）

6.查找值为x的结点

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root->_data == x)
    {
        return root;
    }
    BTNode* left = BinaryTreeFind(root->_left, x);
    if (left != NULL)
    {
        return left;
    }
    return BinaryTreeFind(root->_right, x);
 
}

通过先序遍历的方式遍历所有结点，找到值符合的就返回，都不符合的时候返回NULL。

此处判断左子树是否为空不判断右子树的原因是此时左子树已经为空，若右子树有则返回右子树，若右子树为空则返回右子树(也是空结点)。

7.层序遍历

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
    queue<BTNode*> q;
 
    if (root == NULL)
    {  
        
 
        return;
    }
 
    q.push(root); 
    while (!q.empty())
    {
        BTNode* tmp = q.front();
        printf("%c ", tmp->_data);
        q.pop();
        if (tmp->_left)
        {
            q.push(tmp->_left);
        }
        if (tmp->_right)
        {
            q.push(tmp->_right);
        }
 
    }
 
    printf("\n");
 
    return;
 
 
}

思路：通过队列先进先出的特性，使得当前队列中恒保持只有相邻两层或只有一层的结点的情况。

8.判断是否是满二叉树

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
    queue<BTNode*> q;
 
    if (root == NULL)
    {
        return 1;
    }
 
    int count = 0;
    q.push(root);
    while (!q.empty())
    {
        BTNode* tmp = q.front();
        q.pop();
        if (tmp->_left&&count==0)
        {
            q.push(tmp->_left);
        }
        else if (tmp->_left && count == 1)
        {
            return 0;
        }
        else if(tmp->_left==NULL&&count==0)
        {
            count = 1;
        }
       
 
        if (tmp->_right&&count==0)
        {
            q.push(tmp->_right);
        }
        else if (tmp->_right && count == 1)
        {
            return 0;
        }
        else if (tmp->_right == NULL && count == 0)
        {
            count = 1;
        }
    
    }
 
 
    return 1;
 
 
 
 
}

满二叉树的特性就是层序遍历的情况下，出现一次结点为空以后，就不会再有结点不为空的情况，此处用count=1表示第一次遇到结点为空，此后存在两种情况，一种是后面的结点全是空，最后队列为空退出，此时是满二叉树。一种情况是后面又遇到非空结点，由于此时count已经等于1了，则不是满二叉树。