数据结构初阶|【C语言 - 数据结构】树、二叉树（下篇） c语言|算法|leetcode|数据结构

假设，我手头有 20张100元的和2000张1元的奖券，同时洒向了空中，大家比赛看谁最终捡的最多。如果是你，你会怎么做?
相信所有同学都会说，一定先捡 100 元的。道理非常简单，因为捡一张100元等1元的捡100 张，效率好得不是一点点。所以可以得到这样的结论，同样是捡奖券，在有限时间内，要达到最高效率，次序非常重要。对于二叉树的遍历来讲，次序同样显得很重要。

文章图片

超乎一切之上的一件事,就是保持青春朝气。——莎士比亚
文章目录

一、二叉树的遍历原理
二、二叉树的前序、中序、后序、层序遍历
三、二叉树的拓展：判断树的高度、每层的结点个数等
四、二叉树oj题
总结

提示：以下是本篇文章正文内容，下面案例可供参考
一、二叉树的遍历原理 1.1原理：

二叉树的遍历（traveing binary tree）是指从根结点出发，按照某种次序依次访问二叉树中所有的结点，使每个结点都被访问一次，且仅被访问一次。

这里有两个关键词：访问和次序。
1.2.1访问
访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等，它算作是一个抽象操作。在这里我们可以简单地假定就是输出结点的数据信息。
1.2.2次序
二叉树的遍历次序不同于线性结构，最多也就是从头至尾、循环、双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择就像你人生的道路上，高考填志愿要面临哪个城市、哪所大学、具体专业等选择，由选择方式的不同，遍历的次序就完全不同了。

文章图片

二、二叉树的前序、中序、后序遍历 2.1二叉树遍历的几种方式
二叉树的遍历方式可以很多，如果我们限制了从左到右的习惯方式，那么主要就分为四种：
前序遍历、中序遍历、后序遍历、层次遍历。
这四种遍历方式的基本顺序和在数组中存储的形式如下图所示：

文章图片
2.2前序遍历
规则是若叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图遍历的顺序为: ABDGHCEIF

文章图片

步骤：1、先造一颗树
造树：

#include #include typedef int BTDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; }BTNode; malloc一块空间 BTNode* BuyBTNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { printf("malloc fail\n"); exit(-1); } node->data = https://www.it610.com/article/x; node->left = node->right = NULL; return node; } 紧接着实现链接 BTNode* CreatBinaryTree() { BTNode* node1 = BuyBTNode(1); BTNode* node2 = BuyBTNode(2); BTNode* node3 = BuyBTNode(3); BTNode* node4 = BuyBTNode(4); BTNode* node5 = BuyBTNode(5); BTNode* node6 = BuyBTNode(6); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; return node1; }

2、写前序遍历和main函数

void PrevOrder(BTNode* root)//前序遍历 { if (root == NULL)//如果根是空就return { printf("NULL "); return; } printf("%d ", root->data); PrevOrder(root->left); //左子树 PrevOrder(root->right); //右子树 } int main() { BTNode* tree = CreatBinaryTree(); PrevOrder(tree); return 0; }

程序运行结果：（对照1、2、3、4、5、6）上图

文章图片

2.3中序遍历
规则是若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点) ，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树如图所示，遍历的顺序为GDHBAELCF.

文章图片

void InOrder(BTNode* root)//中序遍历 { if (root == NULL)//如果根是空就return { printf("NULL "); return; } InOrder(root->left); //先左子树 printf("%d ", root->data); InOrder(root->right); //再右子树 } int main() { BTNode* tree = CreatBinaryTree(); InOrder(tree); return 0; }

程序运行结果

文章图片

2.4后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点如图所示遍历的顺序为 GHDBIEFCA。

文章图片

void BackOrder(BTNode* root) { if (root == NULL)//如果根是空就return { printf("NULL "); return; } BackOrder(root->left); BackOrder(root->right); printf("%d ", root->data); } int main() { BTNode* tree = CreatBinaryTree(); BackOrder(tree); return 0; }

程序运行结果：

文章图片

二叉树的遍历的几种路径（小结）：网上找的图

文章图片

2.5层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

文章图片

文章图片

层序遍历与之前的三种遍历情况有所不同，层序遍历的实现依赖于队列，会比较麻烦一些。

文章图片

//层序遍历 void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); //先插入根节点 } while (QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //把队列里根节点的指针拿出来，但是指针指向的节点的值没有被销毁； printf("%d ", front->data); if (front->left) { QueuePush(&q, front->left); } if (front->right) { QueuePush(&q, front->right); } printf("\n"); } QueueDestry(&q); }

三、二叉树的拓展 3.1计算树的结点的个数
low版（代码比较挫）但是容易理解

int count = 0; void BTreeSize(BTNode* root) { if (root == NULL) return; ++count; BTreeSize(root->left); BTreeSize(root->right); //后序 }

注意：
这里为什么不用static静态变量。
因为静态变量在静态区，是整个程序结束后才销毁，而且局部静态变量不能置零
所以如果再计算下一个树的结点就会和上一个树累加。
static只初始化一次，所以要么就是全局静态变量。

具体的调用方法：//更好的计数方法，既不使用全局，也不使用静态变量-
【数据结构初阶|【C语言 - 数据结构】树、二叉树（下篇）】//思想遍历加计数（传地址调用）指针

void BTreeSize(BTNode* root, int* pCount) { if (root == NULL) return; ++(*pCount); //把一个变量的地址传过去 BTreeSize(root->left, pCount); BTreeSize(root->right, pCount); //后序 }

3.2计算树的叶子结点的个数

文章图片

思路：叶子结点的左右结点都为空，递归+分治思想
因此：代码如下

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

3.3怎么求第k层节点的个数？
核心思路：递归返回第k-1层左右结点相加的值

文章图片

int BTreekLeafSize(BTNode* root, int k) { assert(k >= 1); if (root == NULL) return 0; if (k == 1) return 1; return BTreekLeafSize(root->left, k - 1) + BTreekLeafSize(root->right, k - 1); //返回左结点和右结点的上一层 }

3.4求一棵树的高度
思想：比较左右子树的高度，并且返回高度大的加一（原因：加根结点）

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

3.5二叉树查找值为x的结点

文章图片

思路：用前序遍历去递归搜索，先搜左子树，如果左子树没有，就返回一个NULL到根结点，然后根结点再递归搜索右树，如果右树有就返回那个点的值。

BTNode* BTreeFind(BTNode* root, BTDataType x) { if (root == NULL) return NULL; if (root->data =https://www.it610.com/article/= x) return root; //用前序遍历的思想 BTNode* ret1 = BTreeFind(root->left, x); //先去递归左树 if (ret1)//如果左边返回的不是NULL { return ret1; } BTNode* ret2 = BTreeFind(root->right, x); if (ret2) { return ret2; } return NULL; }

3.6判断一棵树是不是完全二叉树
思路：就是把空也当作二叉树的节点放进去，然后运用层序遍历，
如果在遍历的中间过程中遇到空就说明不是完全二叉树。
队列不能直接像数组一样遍历

文章图片

//判断一棵树是不是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q); if (root) { QueuePush(&q, root); //先插入根节点 } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); //会等于队头第一个数据的值 QueuePop(&q); if (front == NULL) { break; } QueuePush(&q, front->left); QueuePush(&q, front->right); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); //会等于队头第一个数据的值 QueuePop(&q); if (front)//如果出到非空，那么就不是完全二叉树 { return false; }} return true; }

四、二叉树oj题 1、965. 单值二叉树 - 力扣（LeetCode）

文章图片

bool isUnivalTree(struct TreeNode* root) { if(root == NULL) return true; if(root->left && root->left->val != root->val)//如果左结点不为空，且左树结点的值不等于根的值，返回false return false; if(root->right && root->right->val != root->val)//如果右结点不为空，且右树结点的值不等于根的值，返回false return false; return isUnivalTree(root->left) && isUnivalTree(root->right); //递归判断 }

2、100. 相同的树 - 力扣（LeetCode）

文章图片

思路：先判断两棵树是不是都是空树，再判断如果一个为空一个不为空，最后递归

bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //判断两个树的根是不是都为空 if(p == NULL && q == NULL) return true; //判断两个树的其中一颗树的结点为空时，另一个不为空 if(p == NULL || q == NULL) return false; //判断两个树的根节点是否是同值 if(p->val != q->val) return false; //递归判断 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } 注意：这里的判断不能写成p->left->val != q->left->val 会报错

3、101. 对称二叉树 - 力扣（LeetCode）

文章图片

思路：写一个辅助函数，舍弃根结点，判断左边这个树是否与右边这个树对称

bool isSymmetricTree(struct TreeNode* p, struct TreeNode* q) { //如果root的左和右节点都为空 if(p == NULL && q == NULL) return true; //如果一个为空一个不为空 if(p == NULL || q == NULL) return false; return p->val == q->val && isSymmetricTree(p->left, q->right) && isSymmetricTree(p->right, q->left); } bool isSymmetric(struct TreeNode* root) { if(root == NULL) return true; return isSymmetricTree(root->left, root->right); }

4、144. 二叉树的前序遍历 - 力扣（LeetCode）

文章图片

题目意思解释：Note: The returned array must be malloced, assume caller calls free().
这句话的意思是数组要malloc，然后caller系统会帮你free掉
int* returnSize的意思是返回结点的个数
代码如下所示：

int TreeSize(struct TreeNode* root)//计算树的结点个数，方便malloc空间 { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; } //定义一个子函数去完成前序遍历 void _preorder(struct TreeNode* root, int* a,int *pi) { if(root == NULL) return; a[(*pi) ++] = root->val; //控一下优先级*的优先级低于++，所以要加（） _preorder(root->left, a, pi); _preorder(root->right, a, pi); } int* preorderTraversal(struct TreeNode* root, int* returnSize)//int*returnSize是输出型参数 { int size = TreeSize(root); //不考虑动态扩容 int* a = malloc(sizeof(int)*size); int i = 0; *returnSize = size; _preorder(root, a, &i); return a; }

因为之后的二叉树中序以及后序遍历思路差不多，所以如果读者有兴趣可以根据这个思路去做。
5、572. 另一棵树的子树 - 力扣（LeetCode）

文章图片

思路：左边树中每一个子树都比较isSameTree
遍历左边的每个节点，做子树的根，跟右边的子树都比较一下isSameTree

bool isSameTree(struct TreeNode* p, struct TreeNode* q) { //两棵树的根都为空 if (p == NULL && q == NULL) return true; //只有一颗树为空此时已经有同位置的节点不相等 if(p == NULL || q == NULL) return false; if(p->val != q->val) return false; return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); }bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) { if(root == NULL) return; if(isSameTree(root, subRoot)) { return true; } return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); }

6.二叉树遍历_牛客题霸_牛客网 (nowcoder.com)
先序遍历字符串构造的二叉树（前序）
递归、分治的思想

文章图片

#include #include //构造结构体 typedef struct BinaryTreeNode { char data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; //造树 BTNode* CreatTree(char* a, int* pi) { if(a[*pi] == '#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); root->data = https://www.it610.com/article/a[(*pi)++]; root->left = CreatTree(a, pi); root->right = CreatTree(a, pi); return root; } void InOrder(BTNode* root) { if(root == NULL)//这里root直接等于NULL判断便可，不需要‘# { return; } InOrder(root->left); printf("%c ", root->data); InOrder(root->right); } //main函数部分 int main () { char a[101]; scanf("%s", a); int i = 0; BTNode* tree = CreatTree(a, &i); InOrder(tree); return 0; }

总结