二叉树链式结构实现与遍历详解

二叉树链式结构实现与遍历

概述

在了解二叉树顺序结构（堆）的基础上，本节重点学习二叉树的链式结构实现。

链式结构实现

用链表来表示一棵二叉树，即用链表来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结构如下：

typedef int BTDataType;
// 二叉链
typedef struct BinaryTreeNode {
    struct BinaryTreeNode* left;   // 指向当前结点左孩子
    struct BinaryTreeNode* right;  // 指向当前结点右孩子
    BTDataType data;               // 当前结点值域
} BTNode;

今天先不来了解怎么创建二叉树，因为这个相对而言比较麻烦，等学完了二叉树的遍历，我们再来深究二叉树的创建。所以这里我们先手动创建一颗链式二叉树。

BTNode* BuyBTNode(int val) {
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if(newnode == NULL) {
        perror("malloc fail");
        return NULL;
    }
    newnode->data = val;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

BTNode* CreateTree() {
    BTNode* n1 = BuyBTNode(1);
    BTNode* n2 = BuyBTNode(2);
    BTNode* n3 = BuyBTNode(3);
    BTNode* n4 = BuyBTNode(4);
    BTNode* n5 = BuyBTNode(5);
    BTNode* n6 = BuyBTNode(6);
    // 创建六个结点
    n1->left = n2;
    n1->right = n4;
    n2->left = n3;
    n4->left = n5;
    n4->right = n6;
    return n1;
}

二叉树图如下：

回顾二叉树的概念，二叉树分为空树和非空二叉树，非空二叉树由根结点、根结点的左子树、根结点的右子树组成的，根结点的左子树和右子树分别又是由子树结点、子树结点的左子树、子树结点的右子树组成的，因此二叉树定义是递归式的,后序链式二叉树的操作中基本都是按照该概念实现的。

遍历方法

二叉树的操作离不开树的遍历，我们先来看看二叉树的遍历有哪些方式。

遍历规则

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

• 前序遍历：访问根结点的操作发生在遍历其左右子树之前。访问顺序为：根结点、左子树、右子树 （根左右）
• 中序遍历：访问根结点的操作发生在遍历其左右子树之中。访问顺序为：左子树、根结点、右子树 （左根右）
• 后序遍历：访问根结点的操作发生在遍历其左右子树之后。访问顺序为：左子树、右子树、根结点 （左右根）

文字描述肯定是抽象的，代码加图片才是王道：以前序遍历为例子。

void PreOrder(BTNode* root) {
    if(root == NULL) // 递归出口 当 root 为空时 返回
        return;
    cout << root->data; // 前序遍历是根左右 所以先打印根结点
    PreOrder(root->left); // 再递归进入左子树
    PreOrder(root->right); // 再递归进入右子树
}

函数递归栈帧图：

前序遍历结果：1 2 3 4 5 6

理解前序遍历之后就简单了，因为中序遍历和后序遍历也是一样的道理就是按照访问顺序来就好啦。

void InOrder(BTNode* root) // 中序遍历
{
    if(root == NULL)
        return;
    InOrder(root->left);
    cout << root->data;
    InOrder(root->right);
}

void PostOrder(BTNode* root) // 后序遍历
{
    if(root == NULL)
        return;
    InOrder(root->left); // 注意此处原文可能是笔误，应为 PostOrder(root->left)
    InOrder(root->right); // 注意此处原文可能是笔误，应为 PostOrder(root->right)
    cout << root->data;
}

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

仔细观察代码，你肯定也是发现了规律，其实代码写起来很简单的，就是按照访问顺序来进行递归。但还是要自己深入理解一次整个递归的操作流程，晓之以理，才能融会贯通。

常用功能实现

接下来我们就来一一实现有关二叉树的一些功能函数。

// 二叉树结点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第 k 层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
// 二叉树查找值为 x 的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

首先来到第一个，二叉树的结点个数。

int BinaryTreeSize(BTNode* root) {
    if(root == NULL)
        return 0;
    return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

没错就这么简单，虽然看起来简单，但是其实一点都不难。递归的本义就是有很多重复类似的子问题，二叉树就是左右孩子一直往下生成。其实在前中后序遍历的时候就能发现规律，我们只需要拿出其中一个子问题来解决就好啦。其次就是要注意递归出口，也就是 if 返回那一段。

来分析结点个数，我们只看只有三个结点的二叉树，有根节点，左右孩子结点，所以结点个数就是当前遍历到的根结点加上左孩子的结点和右孩子的结点，从处理单个的子问题到所有的问题。总的来说，深刻理解递归之后，其实这些看起来都很简单。

下一个，二叉树的叶子结点个数。叶子结点必然是左右孩子为空的结点，符合要求就返回 1，从头开始递归左右孩子，相加就行。只要叶子结点，加上叶子结点的判断，然后不算根结点就行啦。

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);
}

第 k 层结点个数，看起来有没有头绪，但实际上还是不难的。这里对 k 层处理一下就好了，依然是从头开始往下递归，每递归一次 k-1，当 k==1 时，返回 1 就行。

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);
}

二叉树的深度/高度。我们只需要每一层加 1，然后再找到最深的那一层就好啦。一步一步递归，找出是左子树更深还是右子树更深。

int BinaryTreeDepth(BTNode* root) {
    if(root == NULL)
        return 0;
    int leftDep = BinaryTreeDepth(root->left);
    int rightDep = BinaryTreeDepth(root->right);
    return 1 + (leftDep > rightDep ? leftDep : rightDep); // 这里用三目操作符，就是找到左右子树的最大深度
}

下一个，这个处理起来就有点小细节了哦。用结点类型做返回值，如果遇到 x，会返回该结点，但是递归函数返回后需要接受，不然就 gg 啦。

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {
    if(root == NULL)
        return NULL;
    if(root->data == x)
        return root;
    BTNode* leftFind = BinaryTreeFind(root->left, x);
    if(leftFind) // 左子树接收，如果不为空就返回
        return leftFind;
    BTNode* rightFind = BinaryTreeFind(root->right, x);
    if(rightFind) // 右子树接收，不为空就返回
        return rightFind;
    return NULL;
}

最后一个，二叉树的销毁 传址调用，直接释放。

void BinaryTreeDestory(BTNode** root) // 这里传的是二级指针，传地址调用，直接修改
{
    if(*root == NULL)
        return;
    BinaryTreeDestory(&((*root)->left));
    BinaryTreeDestory(&((*root)->right));
    free(*root);
    *root = NULL; // 这里是采用后序遍历逐步销毁二叉树 因为根节点在最上面所有用后序遍历
}

下面就是测试啦。

观察构建的二叉树图和测试样例，实现的还是没有什么问题的。

总结

本文完成了链式二叉树的基本概念、结构及常用函数的实现，核心在于递归思想的运用。后续将涉及更多算法题练习。