C语言中的数据结构--树

前言

上节我们介绍了树的基本概念，并深入讲解了堆的结构与应用。今天我们将继续探讨树结构中的二叉树部分。现在，让我们正式开始今天的学习内容

二叉树

二叉树的链式存储结构

上一节我们所讲堆本质上是一种完全二叉树,主要用于数据选择和排序场景.然而,当应用场景不需要通过树结构来选择数据时,完全二叉树的特性就可能不再适用.在这种情况下,采用链式结构来存取数据会是更合适的选择

二叉树的链式存储是通过链表实现的,每个节点包含三部分:存储数据的部分(数据域)以及指向左孩子和右孩子的指针

基础的二叉树学习通常使用二叉链,高阶数据结构可能用到三叉链

二叉链与三叉链的区别

二叉链:每个节点有两个指针,分别指向左孩子和右孩子,适合普通二叉树结构

三叉链:多一个指向父节点的指针,用于更复杂的数据结构(如红黑树)

二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉

树中的结点进行相应的操作，并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历

是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

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

1. 前序遍历(Preorder Traversal)——访问根结点的操作发生在遍历其左右子树之前。

2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。

3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

直接给出定义可能会有点抽象,难以理解,我们直接带入用例来讲解,可能会通俗易懂一点.

首先先讲解一下前序遍历.任何一棵树都可以拆成三个部分:根、左子树、右子树,对于前序遍历而言,用通俗的话来说就是从根节点开始，先处理当前节点，再处理左子树的所有节点，最后处理右子树的所有节点

按照前序遍历的顺序：

从根节点 1 开始，先记录 1

接着遍历 1 的左子树（以 2 为根）：记录 2，再遍历 2 的左子树（记录 3）。3 没有子节点，回到 2 的右子树

2 没有右子树回到 1 的右子树 4：记录 4，再遍历 4 的左子树（记录 5），5 没有子节点，回到 4 的右子树

4 的右子树是 6 直接遍历右子树 6（记录 6）

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

 还有一种更加容易理解的方法,如图所示,先把二叉树补全成完全二叉树

随后就按照根、左子树、右子树的顺序进行访问即可

用这种方法访问的前序遍历的顺序是:

因为中序遍历的访问顺序是左子树、根、右子树.同理,用上面这种方法中序遍历访问的顺序是:

后序遍历的结果我们也可以轻易的写出来:

前序遍历、中序遍历、后序遍历其实是一种递归式的遍历,其实二叉树还有一种非递归式的遍历叫做层序遍历,这种遍历就是一层一层的往下遍历,所以它遍历的顺序就是: 1 → 2 → 4 → 3 → N → 5 → 6

 二叉树结构以及遍历的代码实现

我们先来定义一下二叉树的节点,这里和定义链表中的节点一样,所以就直接给出代码了:

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

接下来的学习会与我们之前学习的数据结构有出入,我们一开始学习数据结构的代码实现都会先实现增删查改等功能,但是由于现在我们对二叉树结构掌握还不够深入,直接实现二叉树的难度会很大,所以这里直接暴力创建一棵简单的二叉树,直接进入二叉树的遍历,等二叉树结构了解的差不多时,我们反过头再来研究二叉树真正的创建方式

BTNode* BuyNode(int x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatBinaryTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;return node1;
}

接着我们讲解一下前序遍历的代码实现,前序遍历主要是运用了递归的思想,先来分解一下递归的流程:

1.终止条件
当传入的节点指针root为NULL时，表示当前子树为空，打印N并直接返回，结束当前递归分支。

2.常规情况
若节点非空,此时有三种情况：

1.立即访问当前根节点,打印其数据值（root->data）

2.递归调用PrevOrder(root->left)处理左子树

3.递归调用PrevOrder(root->right)处理右子树

void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);
}

此时前序遍历的代码就完成了,初次接触到递归的思想可能会觉得比较抽象,先不妨试着理解,等后续深入学习递归的时候就会觉得很轻松了

下面我会逐步详细的讲解前序遍历递归展开图,方便理解

在main函数中调用PrevOrder函数会建立一个栈帧里面有root变量,在PrevOrder函数里面再次调用PrevOrder函数又会建立一个栈帧,在最开始进入PrevOrder函数的root值是1,因为它的值不是空,直接执行打印操作

此时在第一个PrevOrder函数中又调用了一个PrevOrder函数去递归左子树,往里传入了1的左子树2,现在又会建立一个栈帧:

新的栈帧里面的root值是刚刚传入的2,也不为空,所以此时也会直接将2打印出来,然后建立新的栈帧,传入左子树的3

此时的root是3,也不是空,所以直接执行打印操作,接下来建立栈帧,递归3的左子树:

此时3的左子树为空,打印完N以后就返回了(返回的时候栈帧销毁,图在画的时候忘记体现出来了),返回到root值为3的栈帧里面调用PrevOrder访问3的右子树

因为3的右子树也为空,所以此时也会执行返回操作:

返回之后,root值为3的栈帧已经执行完了,所以会销毁栈帧,然后接着执行root值为2的栈帧:

因为2的右子树也为空,所以打印完N后就直接返回了,此时root为2的栈帧的所有指令也执行完了,该栈帧也会销毁,接着递归调用1的右子树:

打印完4,接着建立栈帧,调用4的左子树:

打印完5,接着建立栈帧,调用5的左子树,此时遇到空,执行返回,然后访问5的右子树:

此时5的右子树也为空,所以直接返回,root为5的栈帧2已经执行完成了,栈帧直接销毁,接下来访问4的右子树:

此时打印完6以后会建立栈帧访问6的左子树,因为6的左子树为空,打印完N后就直接返回访问6的右子树:

6的左右子树皆为空,6的栈帧销毁,此时直接返回root值为4的栈帧,因为4的栈帧执行完了,又会返回root值为1的栈帧,1的栈帧也已经执行完了,此时递归完成,所有栈帧都被销毁:

递归整体展开图也可以参考下面的图片:

递归调用的时候栈帧销毁了的空间可以重复利用,(比如:上面访问3以后会访问3的左子树,因为3的左子树时NULL所以栈帧销毁,访问3的右子树,此时3的左子树销毁的那一块空间又会被重复使用,用于建立3的右子树的栈帧)但是当递归深度过于深或者无限递归的时候还是会出现问题,会导致栈溢出(栈的空间不够),我们来简单的演示一下栈溢出:

int fun(int n)
{if (n == 0)return 0;return fun(n - 1) + n;
}

这里我们来思考一个问题:程序编译完会编译多少份指令?

答案是:与普通函数相同,递归函数在编译的时候这个递归代码只会编译成一份指令.不同的值只会存在不同的栈帧中,而不是指令中

递归函数和普通函数的区别就在于普通函数按顺序执行完所有指令以后就直接销毁了,而递归函数会频繁的调用自己再建立一个参数不同的栈帧,直到遇到空返回了以后才会销毁掉栈帧

我们刚讲完前序遍历的思路,中序遍历和后序遍历的思路也是如此,这里就不再详细展开了,直接给出代码:

void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

int main(void)
{BTNode* root = CreatBinaryTree();PrevOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");return 0;
}

 求二叉树的节点个数、叶子节点个数、深度

二叉树节点个数

假设我们要求二叉树的节点个数该怎么办? 下面来讲解一个错误示范:

我们先让这棵树走一次遍历,走的时候创建一个size变量进行++

int TreeSize(BTNode* root)
{int size = 0;if(root == NULL) return 0;else ++size;TreeSize(root->left);TreeSize(root->right);return size;
}

但当我们写出这个代码的时候就可以发现这个办法是不可行的,因为每个栈帧里面都有一个局部的size变量,这个size变量出栈帧就销毁了,此时我们可能会想到静态修饰一下这个size变量

    static int size = 0;

此时size就不在栈帧中了,而是变成了一个全局的变量,现在这个方法就可行了,我们来测试一下:

BTNode* CreatBinaryTree(void)
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(6);node1->left = node2;node1->right = node4;node2->left = node3;node4->left = node5;node4->right = node6;node5->right = node7;return node1;
}

int main(void)
{BTNode* root = CreatBinaryTree();printf("%d\n", TreeSize(root));return 0;
}

经过测试看上去代码是不存在什么问题,但是我们仔细观察一下代码,其实代码还是存在问题的:

int main(void)
{BTNode* root = CreatBinaryTree();printf("%d\n", TreeSize(root));printf("%d\n", TreeSize(root));return 0;
}

此时静态变量的问题就出现了.因为静态变量只会初始化一次,所以在后续调用该函数的时候就会直接在原来size的基础上开始累加

要想解决这个问题,我们可以将size改为全局变量,并且在调用完TreeSize函数以后手动将size的大小调节为0

int size = 0;
int TreeSize(BTNode* root)
{if(root == NULL) return 0;else ++size;TreeSize(root->left);TreeSize(root->right);return size;
}

int main(void)
{BTNode* root = CreatBinaryTree();printf("%d\n", TreeSize(root)); size = 0;printf("%d\n", TreeSize(root)); size = 0;return 0;
}

但是这样写代码虽然可以解决问题,但是会显得代码非常冗余,其实这个函数的最佳解决方案是采取分治递归的思路,我们接下来详细讲解一下这个思路:

这次分析我们就不用递归展开图了,我们采取分治的思想:

先来分析一下节点的个数:

1:树为空,节点个数为0

2:树不为空,节点个数 = 左子树 + 右子树 + 1

将分析的逻辑转化为代码:

int TreeSize(BTNode* root)
{return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}

 这样代码就完成了:

叶子节点个数

接下来我们分析一下用分治递归的思路求叶子节点的个数:

先来进行一个错误示范:

int LeafSize(BTNode* root)
{if(root->left == NULL && root->right == NULL) return 1;else LeafSize(root->left) + LeafSize(root->right);
}

我们可能会这么写来求叶节点的个数,但是这么做其实是存在错误的,这么写的话假设传入的是一个空树,root为NULL时,代码会尝试访问root->left,会导致空指针异常

假设传入的不是一个空树也有可能存在问题,这样的情况假设节点的度是0或者2的话就不会有问题,要是节点的度是1的话就会产生问题:

我们用一个具体例子分析:假设存在一个度为 1 的节点A(只有左子树，右子树为NULL):

          A

        /

      B

当代码递归到节点A时,因为A不是叶子节点(因为左子树非空),进入else分支执行

return LeafSize(A->left) + LeafSize(A->right)

其中A->right是NULL,此时会调用LeafSize(NULL)

关键问题就在这里：

代码没有处理root为NULL的情况,当计算LeafSize(NULL)时,代码会尝试访问NULL->left,这是空指针解引用,会导致程序崩溃或产生未定义行为

那为什么度为 0 或 2 的节点看似没问题？

度为 0 的节点:直接触发return 1,不会执行递归,自然不会遇到NULL的情况

度为 2 的节点:递归调用的是LeafSize(左子树)和LeafSize(右子树)，而这两个子树都是有效节点所以暂时不会暴露问题

但这只是巧合,只要树中存在度为 1 的节点,最终一定会递归到NULL,导致代码崩溃.

所以正确的代码应该是:

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

树的高度

随后我们来分析一下树的高度:

空树:高度为0

非空树:左子树和右子树高度大的那棵树的高度 + 1

接下来进行一个错误示范:

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

这个写法在逻辑上是没有什么问题的,能够正常执行.问题就是这样写过不了OJ,因为性能太差了

这里存在最大的问题是很多节点会重复计算很多次在这个代码中：

首先计算 TreeHeight(root->left) 和 TreeHeight(root->right) 进行比较

比较后，还需要再次调用 TreeHeight(root->left) 或 TreeHeight(root->right) 来获取值并加 1

这意味着:左子树的深度会被计算 2 次(比较时 1 次，返回时 1 次),右子树的深度也会被计算 2 次(比较时 1 次，返回时 1 次)

每个地方都要计算两次,所以对于深度为 h 的二叉树时间复杂度会从 O(n) 退化为 O(2ⁿ),当树较大时,效率会显著降低

正确的写法:

int TreeHeight(BTNode* root)
{if(root == NULL) return 0;int leftheight = TreeHeight(root->left);int rightheight = TreeHeight(root->right);return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}

这两个函数虽然逻辑思路相同(计算二叉树深度:空树深度为 0,非空树深度为左右子树最大深度 + 1),但第二个避免了重复计算,提高了效率.

或者可以这么写:

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

math.h头文件中的fmax函数会选出较大的那个数,并且在底层实现的时候会进行记录,所以不会有效率问题

求第k层的节点个数

要想求第k层的节点个数有两个方法,一个方法是采用层序遍历,还有一种方法是采用递归的思想.因为本节我们主要讲解的就是递归,所以这里采取递归的思路来解决问题:

这个问题也可以拆分成左子树和右子树来解决.假设我们要求第三层有几个节点,因为根节点1的第三层的节点相当于孩子节点2、4的第二层节点

我们通过这个思路来分析一下:

k为空:不管要找第几层,空树都没有任何节点,所以直接返回 0

k不为空且k == 1:第 1 层就是当前根节点所在的层,所以只要树不为空,就一定有 1 个节点,返回 1,返回1

k不为空且k > 1:此时第 k 层的节点,实际上是当前根节点的左子树的第 k-1 层节点,加上右子树的第 k-1 层节点

这种递归方式自然地遍历了树的每一条路径,通过层层递减 k 值,最终统计出目标层的节点总数

int getKthLevelNodeCount(BTNode* root, int k)
{// 情况1：树为空，返回0if (root == NULL) return 0;// 情况2：k等于1，返回1（当前节点就是第1层的节点）if (k == 1) return 1;// 情况3：k大于1，递归计算左子树和右子树的第k-1层节点数之和return getKthLevelNodeCount(root->left, k-1) +getKthLevelNodeCount(root->right, k-1);
}

查找值为x的节点

BTNode* TreeFind(BTNode* root, BTDataType x)
{if(root == NULL) return NULL;if(root->data == x) return root;TreeFind(root->left, x);TreeFind(root->right, x);
}

这样写会导致报错,因为当两个 if 条件都不满足时,程序会执行到末尾却没有返回语句

此外,这种写法在查找到值为 x 的节点后,虽然使用了 return 语句,但实际返回的是查找结果给上一个调用栈帧,而当前函数并未接收这个返回值.而且一旦在左子树中找到了目标节点,就没必要再搜索右子树了

所以我们要按照如下的思路来书写代码:

处理空树情况:如果当前节点root为NULL(空树或已遍历到叶子节点的子节点),说明此路径上没有目标节点,返回NULL

检查当前节点:如果当前节点的值root->data等于目标值x,直接返回当前节点的指针(找到目标,结束查找)

递归查找左子树：

定义leftRet接收左子树的查找结果（递归调用TreeFind(root->left, x)）。如果leftRet不为NULL，说明左子树中找到了目标节点，立即返回leftRet

递归查找右子树：

若左子树未找到,定义RightRet接收右子树的查找结果（调用TreeFind(root->right, x))如果RightRet不为NULL,返回RightRet

未找到目标:如果当前节点、左子树、右子树都没有目标值x,返回NULL

BTNode* TreeFind(BTNode* root, BTDataType x)
{if(root == NULL) return NULL;if(root->data == x) return root;BTNode* leftRet = TreeFind(root->left, x);if(leftRet) return leftRet;BTNode* RightRet = TreeFind(root->right, x);if(RightRet) return RightRet;return NULL;
}

我们还可以对代码进行优化:

BTNode* TreeFind(BTNode* root, BTDataType x)
{if(root == NULL) return NULL;if(root->data == x) return root;BTNode* leftRet = TreeFind(root->left, x);if(leftRet) return leftRet;return TreeFind(root->right, x);
}

这段代码通过简化右子树的查找逻辑,实现了和之前版本完全相同的功能,具体分析如下:

 1. 原代码中对右子树的处理是: 

BTNode* RightRet = TreeFind(root->right, x);
if(RightRet) return RightRet;
return NULL;

这段逻辑可以简化为 :

    return TreeFind(root->right, x);

因为若右子树找到目标节点，TreeFind(root->right, x)`会直接返回该节点的指针,等价于 return RightRet.

 若右子树未找到,TreeFind(root->right, x),会返回NULL,等价于最终的return NULL

2. 保持前序遍历逻辑,代码仍遵循“根→左→右”的查找顺序: 

先检查当前节点是否匹配.不匹配则递归查找左子树,若左子树找到则立即返回.

左子树未找到时,直接递归查找右子树并返回其结果(无论是否找到)

 这样写代码更简洁,省去了中间变量RightRet和对其的判断,在不影响逻辑正确性的前提下,使代码更精炼. 这种写法本质上是对冗余代码的简化,核心功能和执行流程与原版完全一致,是更加推荐的写法 

结尾

那么到此为止,二叉树的基本知识就已经讲解结束了,因为我们初次接触递归,下一节我们将讲解一下和二叉树有关的题目来强化理解递归.希望本文能给您带来帮助,谢谢您的浏览!!!!!!!