经典面试题：二叉树系列（1）

分手后的思念是犯贱 2022-06-02 09:15 116阅读 0赞

**一、先介绍如何用代码实现二叉树的创建：**

第一步：将实际的二叉树数组化：

![这里写图片描述][SouthEast]

第二步：读取数组内的数据，以链表的方式建树：

//下面的代码仅仅是用来配合图解释说明的，读者不可以直接拿来复制粘贴运行
    //完整代码会在末尾粘贴，如需要，读者可以选用它来测试运行
    typedef int BTDataType;
    
    typedef struct BinaryTreeNode
    {
        struct BinaryTreeNode* _left;//指向左子树
        struct BinaryTreeNode* _right;//指向右子树
        BTDataType _data;
    }BTNode;
    
    BTNode* BuyBTNode(BTDataType x)//创建新结点
    {
        BTNode* node = (BTNode*)malloc(sizeof(BTNode));
        assert(node);
        node->_left = NULL;
        node->_right = NULL;
        node->_data = x;
        return node;
    }
    
    BTNode* CreateBTree(BTDataType* a, size_t* pIndex, BTDataType invalid)
    //这里的下标Index不是传值，而是传地址（传指针）
    //因为传参形成临时变量，导致递归的某一层中的变量发生改变不会使上一层的值改变
    //因此要传指针，以保证下标随着递归的次数改变而改变
    {
        BTNode* root = NULL;//创建树的根
        if (a[*pIndex] != invalid)//遍历数组内容，遇到的不是非法值时，创建结点
        {
            root = BuyBTNode(a[*pIndex]);
            ++(*pIndex);
            root->_left = CreateBTree(a, pIndex, invalid);
            ++(*pIndex);
            root->_right = CreateBTree(a, pIndex, invalid);
        }
        return root;
    }
    //CreateBTree()函数的作用由下面动图演示

![这里写图片描述][SouthEast 1]

**二、二叉树的基本操作**  
了解代码如何实现二叉树的创建后我们开始进入正题：

①基础：遍历二叉树
    1>:前序遍历
    void BTreePrevOrder(BTNode* root)//前序遍历(递归)
    {
        if (root == NULL)
        {
            return;
        }
        printf("%d ",root->_data);
        BTreePrevOrder(root->_left);
        BTreePrevOrder(root->_right);
    }
    2>:中序遍历
    void BTreeInOrder(BTNode* root)//中序遍历
    {
        if (root == NULL)
        {
            return;
        }
        BTreeInOrder(root->_left);
        printf("%d ", root->_data);
        BTreeInOrder(root->_right);
    }
    3>:后续遍历
    void BTreePostOrder(BTNode* root)//后序遍历
    {
        if (root == NULL)
        {
            return;
        }
        BTreePostOrder(root->_left);
        BTreePostOrder(root->_right);
        printf("%d ", root->_data);
    }
    //这部分很简单，顺序遍历的不同就是printf的位置的不同，即访问（输出）数据的位置不同

②一般面试题：二叉树的属性
    1>:求树的结点数
    //思路：递归遍历一遍二叉树，每递归一次就加一
    size_t BTreeSize(BTNode* root)//求树的结点数
    {
        if (root == NULL)
        {
            return 0;
        }
        return BTreeSize(root->_left) + BTreeSize(root->_right) + 1;
    }
    2>:求树的叶子数
    //思路：在1>的基础上，添加限制条件：当该结点的左子树和右子树同时为空，即为叶子的时候加一
    size_t BTreeLeafSize(BTNode* root)//求树的叶子数
    {
        if (root == NULL)
        {
            return 0;
        }
        if (root->_left == NULL && root->_right == NULL)
        {
            return 1;
        }
        return BTreeLeafSize(root->_left) + BTreeLeafSize(root->_right);
    }
    3>:求树的第k层的结点数
    //思路：从根往下走，走k层，k在这个过程中不停自减，当k等于1时代表走到第k层了
    size_t BTreeKLevelSize(BTNode* root, size_t k)//求树的第k层的结点数
    {
        if (root == NULL)
        {
            return 0;
        }
        if (k == 1)//从根往下走，走k层，k在这个过程中不停自减，当k等于1时代表走到第k层了
        {
            return 1;
        }
        return BTreeKLevelSize(root->_left, k - 1) + BTreeKLevelSize(root->_right, k - 1);
    }

4>:求树的深度
    //思路：如下图
    size_t BTreeDepth(BTNode* root)//求树的深度
    {
        if (root == NULL)
        {
            return 0;
        }
        size_t leftDepth = BTreeDepth(root->_left);
        size_t rightDepth = BTreeDepth(root->_right);
        return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
    }

![这里写图片描述][SouthEast 2]

5>:找树中的结点
    //思路：遍历二叉树查找
    BTNode* BTreeFind(BTNode* root, BTDataType x)//找树中的结点
    {
        if (root == NULL)
        {
            return NULL;
        }
        if (root->_data == x)
        {
            return root;
        }
        //定义两个变量接收查找的结果再用if判断的好处是，如果找到了，就不再往下递归了，节省时间
        BTNode* leftRet = BTreeFind(root->_left, x);
        if (leftRet)
        {
            return leftRet;
        }
        BTNode* rightRet = BTreeFind(root->_right, x);
        if (rightRet)
        {
            return rightRet;
        }
        return NULL;
    }

③进阶面试题：判断是否为完全二叉树
    1>:先介绍一个函数：层序遍历，即一层一层的访问二叉树，用到了队列
    void BTreeLevelOrder(BTNode* root)//层序遍历
    {
        Queue q;
        QueueInit(&q);
        if (root)//先把根结点入队，以保证第一次检验队不为空
        {
            QueuePush(&q, root);
        }
        while (QueueEmpty(&q)!= 0)//队列不为空
        {
            BTNode* front = QueueFront(&q);
            printf("%d ",front->_data);
            QueuePop(&q);
            if (front->_left!=NULL)
            {
                QueuePush(&q, front->_left);
            }
            if (front->_right!=NULL)
            {
                QueuePush(&q, front->_right);
            }
        }
        printf("\n");
    }
    //BTreeLevelOrder()函数的作用由下面动图演示

![这里写图片描述][SouthEast 3]

2>:了解层序遍历之后，就可以用它来检验是否是完全二叉树
    在这之前，我们先弄清楚什么是完全二叉树？
    完全二叉树：二叉树的前n层都是满的，且第n层从左往右必须是连续的
    int IsCompleteBTree(BTNode* root)//用层序遍历的方式实现
    {
        Queue q;
        QueueInit(&q);
        if (root)//先把根结点入队，以保证第一次检验队不为空
        {
            QueuePush(&q, root);
        }
        while (QueueEmpty(&q) != 0)//队列不为空
        {
            BTNode* front = QueueFront(&q);
            QueuePop(&q);
            if (front == NULL)
            {
                break;
            }
            else
            {
                QueuePush(&q, front->_left);
                QueuePush(&q, front->_right);
            }
        }
        while (QueueEmpty(&q) != 0)
        {
            BTNode* front = QueueFront(&q);
            if (front!=NULL)
            {
                return 0;
            }
            QueuePop(&q);
        }
        return 1;
    }
    //判断是否是完全二叉树这个函数中使用了层序遍历的方法，但是有些改动，就是把NULL也入队了
    //出队时，检测到队头为NULL后停止遍历，再判断队是否为空
    //如果队为空，则是完全二叉树；反之，开始检验队内数据是否全为NULL，是则是完全二叉树，不是，则不是完全二叉树
    //因为完全二叉树的第n层从左往右是连续的，则层序遍历后数据与数据之间不可能存在NULL

![这里写图片描述][SouthEast 4]

完整源码：[https://github.com/WangYe8613/BinaryTree][https_github.com_WangYe8613_BinaryTree]

[SouthEast]: /images/20220602/c4a2263041d54f7cae1ce389b8ff7621.png
[SouthEast 1]: /images/20220602/f6dc71710e4b494e911933aaf90c1591.png
[SouthEast 2]: /images/20220602/f9e3ad60b06143aea48d2408ae6a254b.png
[SouthEast 3]: /images/20220602/75c3784197a54b1d9c19f164ca3a058e.png
[SouthEast 4]: /images/20220602/5480018351ea44d0a8bab0d65150dfee.png
[https_github.com_WangYe8613_BinaryTree]: https://github.com/WangYe8613/BinaryTree