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

借助队列实现层序遍历

// 层序遍历
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

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

总结

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