数据结构——小小二叉树第三幕（链式结构的小拓展，二叉树的创建，深入理解二叉树的遍历）超详细！！！

文章目录

• 前言
• 一、二叉树的层序遍历
• 二、二叉树的有关习题
  • 2.1 单值二叉树
    • 题目
    • 思路
    • 代码
  • 2.2 相同的树
    • 题目
    • 思路
    • 代码
  • 2.3 对称的树
    • 题目
    • 思路
    • 代码
  • 2.4 二叉树的遍历
    • 题目
    • 思路
    • 代码
  • 2.5 二叉树的遍历
    • 题目
    • 思路
    • 代码
  • 2.6 二叉树的有关选择题
• 总结

前言

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

一、二叉树的层序遍历

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

对队列不熟悉的可以看看我的这篇博客嗷
链接：栈和队列

有图才能有真相

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

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

typedef BTNode* QDataType;// int 改成 BTNode*typedefstructQueueNode// 队列内每个元素用链式结构 一个一个结点连接{ QDataType data;structQueueNode* next;}QueueNode;typedefstructQueue// 队列 { QueueNode* phead;// 队头 QueueNode* ptail;// 队尾int size;}Queue;voidQueueInit(Queue* pq);// 队列初始化 voidQueuePush(Queue* pq, QDataType x);// 入队 voidQueuePop(Queue* pq);// 出队 boolQueueEmpty(Queue* pq);// 判空函数  QDataType QueueFront(Queue* pq);// 获取对头元素  QDataType QueueBack(Queue* pq);// 获取队尾元素intQueueSize(Queue* pq);// 队内有效元素voidQueueDestory(Queue* pq);// 销毁队列 voidQueuePrint(Queue* pq);// 打印 方便测试代码 

借助队列实现层序遍历

// 层序遍历voidLevelOrder(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);}

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

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

// 判断⼆叉树是否是完全⼆叉树boolBinaryTreeComplete(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);returnfalse;}}QueueDestroy(&q);returntrue;}

层序遍历就到这里啦

二、二叉树的有关习题

2.1 单值二叉树

习题链接：单值二叉树

题目

思路

思路：本题给定一个二叉树，判断所有的结点的值是否相同
简简单单的一个题，就是递归判断每一个左右孩子是否与根结点相同就好啦
对于认真了解二叉树的遍历的我们，洒洒水啦

代码

classSolution{public:boolisUnivalTree(TreeNode* root){if(root ==NULL)returntrue;if(root->left && root->val != root->left->val)returnfalse;if(root->right && root->val != root->right->val)returnfalse;returnisUnivalTree(root->left)&&isUnivalTree(root->right);}};

轻松拿下

2.2 相同的树

习题链接：相同的树

题目

思路

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

代码

classSolution{public:boolisSameTree(TreeNode* p, TreeNode* q){if(q ==NULL&& p ==NULL)// 如果两颗树的当前结点都为空 返回truereturntrue;if(q ==NULL|| p ==NULL)// 如果其中有一个不为空 证明两颗树的结点个数不同returnfalse;if(p->val != q->val)// 值不相同returnfalse;returnisSameTree(p->left,q->left)&&isSameTree(p->right,q->right);// 递归到每个根节点的左右子树 }};

拿下拿下

2.3 对称的树

习题链接：对称的树

题目

思路

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

代码

classSolution{public:boolcheck(TreeNode* p, TreeNode* q){if(p ==nullptr&& q ==nullptr){returntrue;}if(p ==nullptr|| q ==nullptr){returnfalse;}// 当前结点是否相等 以及 左右孩子反过来匹配判断 return p->val == q->val &&check(p->left,q->right)&&check(p->right,q->left);}boolisSymmetric(TreeNode* root){// 递归第一个根结点的左右子树 分成两棵树来看 returncheck(root->left, root->right);}};

也是稳稳的过啦

2.4 二叉树的遍历

习题链接：二叉树的遍历

题目

思路

思路：本题看起来就有难度了，就像上篇博客留下来的一个小问题，构建二叉树
本题根据读入的先序遍历，根据字符串创建二叉树，然后再进行中序遍历
这颗树建起来还不算麻烦，毕竟已经给了先序遍历，我们就构建链式结构，然后递归字符串的下标就好啦，走一遍先序遍历，然后把值赋给结点

代码

#include<functional>#include<iostream>usingnamespace std;typedefstructBinaryTreeNode// 正常创建二叉树链式结构 {char data;structBinaryTreeNode* left;structBinaryTreeNode*right;}BTNode; 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 表示字符串的下标 {(*pi)++;// 如果当前字符是 # pi++ 返回 returnNULL;} BTNode* root =BuyNode(arr[*pi]);// 根据先序遍历 获取值为arr[pi]的结点 pi++(*pi)++; root->left =createTree(arr, pi); root->right =createTree(arr, pi);return root;// 类似于先序遍历的过程建树 }voidInOrder(BTNode* root)// 再更具中序遍历输出就好了{if(root ==NULL)return;InOrder(root->left); cout<<root->data<<' ';InOrder(root->right);}intmain(){ string arr; cin>>arr;int i =0; BTNode* root =createTree(arr,&i);InOrder(root);return0;}

拿下

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>usingnamespace std;structTNode// 二叉树的结点结构 数据域 左右指针域 {int data; TNode* left; TNode* right;};voidLevelOrder(TNode* root)// 层序遍历 { queue<TNode*> q;// 这里小编就直接使用 stl库的 queue 函数啦 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)returnnullptr; 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;// pos左边的就是左子树 pos 右边的就是右子树 } node->left =BuildTree(inorder, postorder, pos);// 当前根节点的左子树  node->right =BuildTree(inorder + pos +1, postorder + pos, n - pos -1);// 右子树 return node;// 这里中序遍历要在pos结点之后 因为pos是根结点 }// 后序遍历在pos开始 因为根节点在结尾 intmain()// 然后就是反复循环左右子树递归就好啦 就像前面举例一样 {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);// 层序遍历 return0;}

也是稳稳拿下了

2.6 二叉树的有关选择题

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

对任何一棵二叉树, 如果度为 0 的叶结点个数为 n0 , 度为2 的分支结点个数为 n2 ,则有 n0 = n 2 + 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

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

总结

简单的一些二叉树的学习就到这里啦，目前小编的石粒还没有涉及到更深层次的二叉树
回顾前面两篇文章，从二叉树的基本概念到顺序结构二叉树（堆）的实现，再到链式结构二叉树的实现，然后是二叉树的遍历方式，最后到习题部分的巩固与深入，对二叉树的遍历越来越深刻，特别是根据中序遍历和后序遍历建树再层序遍历输出，对递归又有了进一步理解，小编持续进步中~~~~
下一篇我们将开启新的数据结构——排序，小编持续更新中，不要走开~~~~