数据结构：二叉树链式结构拓展与遍历算法详解

前言

上篇博客我们学习了链式结构的二叉树，从递归角度实现了二叉树的前中后序遍历以及各种有关二叉树的结点个数和高度等函数，今天我们来学习一个不使用递归的二叉树的层序遍历以及一些二叉树有关的算法题。

一、二叉树的层序遍历

二叉树的层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第 2 层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。层序遍历还要借助我们的数据结构：队列。

有图才能有真相

其实就是当前一层的结点入队列，然后一个一个出队列，出队列时把该节点的左右孩子入队列，这样下一个层级的结点就跟着上一层结点之后啦，重复这个操作，层序遍历就完成啦。

这是队列的结构以及一些函数的声明（这里把之前的 int 改成 BTNode 就好啦，队列里面的元素是二叉树的结点类型）

typedef BTNode* QDataType;
struct QueueNode {
    QDataType data;
    struct QueueNode* next;
};
struct Queue {
    QueueNode* phead;
    QueueNode* ptail;
    int size;
};
void QueueInit(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
int QueueSize(Queue* pq);
void QueueDestory(Queue* pq);
void QueuePrint(Queue* pq);

借助队列实现层序遍历

// 层序遍历
void LevelOrder(BTNode* root) {
    Queue q;
    QueueInit(&q);
    QueuePush(&q, root);
    while (!QueueEmpty(&q)) {
        BTNode* top = QueueFront(&q);
        QueuePop(&q);
        cout << top->data;
        if (top->left) {
            QueuePush(&q, top->left);
        }
        if (top->right) {
            QueuePush(&q, top->right);
        }
    }
    QueueDestroy(&q);
}

学习了层序遍历之后，我们可以用它来判断二叉树是否为完全二叉树，因为完全二叉树是一层一层去填满每一个结点的，不能跳着填。

思路：正常层序遍历二叉树，当遇到空结点时，跳出循环，此时如果是完全二叉树，那它之后的结点除了空结点是没有有效结点的，如果有，那就不是完全二叉树。

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

层序遍历就到这里啦。

---

二、二叉树的有关习题

2.1 单值二叉树

习题链接：单值二叉树

题目

思路

本题给定一个二叉树，判断所有的结点的值是否相同。简单的一个题，就是递归判断每一个左右孩子是否与根结点相同就好啦。

代码

class Solution {
public:
    bool isUnivalTree(TreeNode* root) {
        if (root == NULL) return true;
        if (root->left && root->val != root->left->val) return false;
        if (root->right && root->val != root->right->val) return false;
        return isUnivalTree(root->left) && isUnivalTree(root->right);
    }
};

2.2 相同的树

习题链接：相同的树

题目

思路

本题和上一题有些类似，算是上一个题的拓展学习吧，需要判断是不是两颗相同的树。我们就同时递归两个树就好啦，一边递归一边判断结点的值是否相等，另外再处理一下不是相同的两颗树的判断就好啦。

代码

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (q == NULL && p == NULL) return true;
        if (q == NULL || p == NULL) return false;
        if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

2.3 对称的树

习题链接：对称的树

题目

思路

本题要判断一颗树是否为对称二叉树。一开始没什么头绪，但是想到对称，就从对称入手了，除了第一层的根节点，如果符合对称条件，左右子树是两颗左右孩子相反的树，这与判断两颗相同的树有些许差别，但处理一下就好啦，递归第一颗树的左节点和第二颗树的右结点匹配，右结点与左结点匹配。

代码

class Solution {
public:
    bool check(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        }
        if (p == nullptr || q == nullptr) {
            return false;
        }
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }
    bool isSymmetric(TreeNode* root) {
        return check(root->left, root->right);
    }
};

2.4 二叉树的遍历

习题链接：二叉树的遍历

题目

思路

本题根据读入的先序遍历，根据字符串创建二叉树，然后再进行中序遍历。这颗树建起来还不算麻烦，毕竟已经给了先序遍历，我们就构建链式结构，然后递归字符串的下标就好啦，走一遍先序遍历，然后把值赋给结点。

代码

#include <functional>
#include <iostream>
using namespace std;

struct BinaryTreeNode {
    char data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
};

BTNode* BuyNode(char ch) {
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    node->data = ch;
    node->left = node->right = NULL;
    return node;
}

BTNode* createTree(string arr, int* pi) {
    if (arr[*pi] == '#') {
        (*pi)++;
        return NULL;
    }
    BTNode* root = BuyNode(arr[*pi]);
    pi++;
    (*pi)++;
    root->left = createTree(arr, pi);
    root->right = createTree(arr, pi);
    return root;
}

void InOrder(BTNode* root) {
    if (root == NULL) return;
    InOrder(root->left);
    cout << root->data << ' ';
    InOrder(root->right);
}

int main() {
    string arr;
    cin >> arr;
    int i = 0;
    BTNode* root = createTree(arr, &i);
    InOrder(root);
    return 0;
}

2.5 二叉树的遍历

本题就没有习题链接啦，是实验课的习题。

题目

思路

本题和上一题不同的是，上一题是给定先序遍历，然后再建树输出中序遍历。但本题是给定后序遍历和中序遍历，再输出层序遍历。只给定先序遍历建树还好，这里是给定后序和中序遍历。

想到后序遍历（左右根）和中序遍历（左根右）的具体过程，可以根据后序遍历找根节点，然后再根据中序遍历找左右子树，如此反复这个过程就好啦。

假设我们有以下后序遍历和中序遍历的结果：

后序遍历：3 2 5 6 4 1 中序遍历：3 2 1 5 4 6

确定根节点：在后序遍历中，最后一个元素 1 是根节点。 分割中序遍历：在中序遍历中找到根节点 1 的位置，它将中序遍历分为左子树 3 2 和右子树 5 4 6。 递归构建子树：对于左子树 3 2 和右子树 5 4 6，分别在后序遍历中找到对应的部分（去掉已处理的根节点）。左子树的后序遍历是 3 2，右子树的后序遍历是 5 6 4。 对左子树和右子树重复上述过程，直到构建完整棵树。

左子树：

右子树：

就是不断找当前根节点的左右子树，把一个大问题化成很多重复相同的子问题。

代码

这里用 C++ 来实现这个题目。

#include <bits/stdc++.h>
using namespace std;

struct TNode {
    int data;
    TNode* left;
    TNode* right;
};

void LevelOrder(TNode* root) {
    queue<TNode*> q;
    q.push(root);
    while (!q.empty()) {
        TNode* top = q.front();
        q.pop();
        if (top == root) cout << top->data;
        else cout << ' ' << top->data;
        if (top->left) q.push(top->left);
        if (top->right) q.push(top->right);
    }
}

TNode* BuildTree(int* inorder, int* postorder, int n) {
    if (n == 0) return nullptr;
    TNode* node = new TNode;
    node->data = postorder[n - 1];
    node->left = node->right = nullptr;
    int pos = 0;
    for (pos; pos < n; pos++) {
        if (inorder[pos] == postorder[n - 1]) break;
    }
    node->left = BuildTree(inorder, postorder, pos);
    node->right = BuildTree(inorder + pos + 1, postorder + pos, n - pos - 1);
    return node;
}

int main() {
    int inorder[50], postorder[50];
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> postorder[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> inorder[i];
    }
    TNode* root = BuildTree(inorder, postorder, n);
    LevelOrder(root);
    return 0;
}

2.6 二叉树的有关选择题

先来了解一些新的二叉树的性质：

对任何一棵二叉树，如果度为 0 的叶结点个数为 n0，度为 2 的分支结点个数为 n2，则有 n0 = n2 + 1

假设一个二叉树有 a 个度为 2 的节点，b 个度为 1 的节点，c 个叶节点，则这个二叉树的边数是 2a+b。另一方面，由于共有 a+b+c 个节点，所以边数等于 a+b+c-1。结合上面两个公式：2a+b = a+b+c-1，即：a = c-1

话不多说，上题。

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ） A 不存在这样的二叉树 B 200 C 198 D 199

   由前面推导出来的 a = c-1，叶子结点个数有 200 个

2. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ） A n B n+1 C n-1 D n/2

   已知是完全二叉树则有 b = 1 或 0。2a+b+1 = 2n。若要符合要求 b 只能=1，所以 a = n-1、c = n;

3. 一棵完全二叉树的结点数为 531 个，那么这棵树的高度为（ ） A 11 B 10 C 8 D 12

   完全二叉树最后一层之前都是满的，所以可以根据 2 的次幂来求层数，前面在最开始讲到满二叉树时有结点个数的公式：结点个数 = 2^k-1 为层数。2 的 9 次幂是 512，所以这颗树的高度为 10

4. 一个具有 767 个结点的完全二叉树，其叶子结点个数为（） A 383 B 384 C 385 D 386

   完全二叉树，还是回到 b 只能取 1 或 0，则 2a+b+1 = 767，b 只能取 0，推出 a = 383 c=384;

来一些链式二叉树的遍历题

1. 某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH。该完全二叉树的前序序列为 A ABDHECFG B ABCDEFGH C HDBEAFCG D HDEBFGCA

   越来越觉得完全二叉树是个好东西。左子树 b d e h，右子树 c f h

2. 二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为 A E B F C G D H

   找根节点，给了先序遍历，那不就是 E 嘛

3. 设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。 A adbce B decab C debac D abcde

   和我们前面根据中序遍历和后序遍历建树的题相似，这不是手拿把掐吗

4. 某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出（同一层从左到右）的序列为 A FEDCBA B CBAFED C DEFCBA D ABCDEF

   这个题更有意思，中序遍历和后序遍历相同，那不是只有左子树

总结

简单的一些二叉树的学习就到这里啦。回顾前面两篇文章，从二叉树的基本概念到顺序结构二叉树（堆）的实现，再到链式结构二叉树的实现，然后是二叉树的遍历方式，最后到习题部分的巩固与深入，对二叉树的遍历越来越深刻，特别是根据中序遍历和后序遍历建树再层序遍历输出，对递归又有了进一步理解。