目录
1.链式结构的创建
2.遍历的方式
3.结点数的计算
4.高度的计算
5.第k层的节点个数
6.查找值
7.判断完全二叉树
8,销毁
9.OJ题
1.链式结构
在学习二叉树基本操作前，需要先创建一颗二叉树。为了快速上手，这里手动擦窗机简单的二叉树。等后面再自动创建
typedef int TDataType;
typedef struct BinaryTreeNode
{
TDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}TNode;
TNode* BuyNode(TDataType data)
{
TNode* newnode = (TNode*)malloc(sizeof(TNode));
if (newnode == NULL)
{
perror("mallco");
return NULL;
}
//初始化数据
newnode->_data = data;
newnode->_left = NULL;
newnode->_right = NULL;
return newnode;
}
TNode* CreatBinaryTree()
{
TNode* node1 = BuyNode(1);
TNode* node2 = BuyNode(2);
TNode* node3 = BuyNode(3);
TNode* node4 = BuyNode(4);
TNode* node5 = BuyNode(5);
TNode* node6 = BuyNode(6);
node1->_left = node2;
node1->_right = node4;
node2->_left = node3;
node4->_left = node5;
node4->_right = node6;
return node1;
}
上面的二叉树的图形
2. 二叉树的遍历
2.1 前序、中序、后续遍历
二叉树遍历是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，每个节点只操作一次。遍历是二叉树最重要的运算之一，也是二叉树上进行其他的运算的基础
前序遍历(Preorder Traversal 先序遍历/先根遍历)
访问根节点的操作发生在遍历其左右子树之前
根节点 左子树 右子树
1 2 3 N N N 4 5 N N 6 N N
N代表空
void PrePrint(TNode* root)
{
if (root == NULL)
{
printf("N ");
return;
}
printf("%d ", root->_data);
PrePrint(root->_left);
PrePrint(root->_right);
}
中序遍历(Inorder Traversal)
访问根节点的操作发生在遍历其左右子树之中
N 3 N 2 N 1 N 5 N 4 N 6 N
前序遍历(Postorder Traversal)
访问根节点的操作发生在遍历其左右子树之后
N N 3 N 2 N N 5 N N 6 4 1
递归的条件:
1.子问题
2.返回条件，不然会栈溢出
上面的时间复杂度是O(N),有N个结点要打印N次
空间复杂度是高度O(h),空间可以重复利用,兄弟层用的一个栈帧空间
三种遍历的联系
在没有重复值的前提下
先序遍历可以得到二叉树的根结点，如果有左右子树，可以得到左右子树对应的根节点
中序遍历的根结点分成左右子树
后序遍历的最后一个是二叉树的根节点，再往前可能是右子树的根节点
中序和前序后序任一个联合可以得到整个树的结构，前序和后序确定根，中序分割左右子树
二叉树的先序和后序遍历结果相反，树中每个结点只有一个孩子，只有一个叶子结点，结果就是相反的
2.2 层序遍历
层序遍历就是从根结点为第1层开始，一层一层向下遍历
思路
可以利用队列先进先出的规则，先将根节点压进去，根节点出来的时候再将左右节点压进去，重复这个过程。这样打印的时候就不会破坏顺序，先进队列的先打印
之前队列的数据类型是int，需要改成结点的指针类型，单纯压入值并不能得到左右结点，所以要压入结点的地址
结构文件
typedef int TDataType;
typedef struct BinaryTreeNode
{
TDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}TNode;
typedef TNode* DATATYPE;
//节点
typedef struct _Node
{
DATATYPE data;
struct _Node* next;
}Node;
//队列
typedef struct _Queue
{
struct _Node* head;
struct _Node* tail;
int size;
}Queue;
函数
void LevelPrint(TNode* root)
{
Queue que;
Init(&que);
if (root != NULL)
{
Push(&que, root);
}
while (!Empty(&que))
{
TNode* top = Front(&que);
printf("%d ", top->_data);
Pop(&que);
if (top->_left != NULL)
{
Push(&que, top->_left);
}
if (top->_right != NULL)
{
Push(&que, top->_right);
}
}
}
首先是队列的结构，队列有一个头节点和尾节点，，为了方便理解，上面的头尾节点没存数据，实际上头尾结点也存数据。头结点的下一个链接到下一个结点的地址，结点里保存了二叉树的根节点地址。先压入头结点入队，出队时释放的是队列结点的指针，并不是二叉树根结点的地址，然后按顺序压入根结点的左右子树地址，直到队列为空结束
3. 结点个数的计算
可以根据上面的遍历所有结点，每次访问一个结点数量加1
int count = 0;
int TreeSize(TNode* root)
{
if (root == NULL)
{
return;
}
count++;
TreeSize(root->_left);
TreeSize(root->_right);
return count;
}
这种方法需要定义一个全局变量，怎么可以不用全局变量
递归的原理就是分治法
比如校长想知道全校有多少学生，会叫来院长AB，院长AB又会让辅导员去统计，辅导员让班长去统计，然后班长统计完返回给辅导员，辅导员统计几个班长的总数返回给院长，院长统计完两个辅导员的总数返回给校长。整个过程就是将大问题化为越来越小的问题，直到可以得出答案，然后返回小问题的结果
int TreeSize(TNode* root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->_left)
+ TreeSize(root->_right)
+ 1;
}
这个画图之后和后序遍历的过程相似，空就返回0，后序左右子树遍历完再加上自身的1然后返回给上一层
4. 高度的计算
高度就是求二叉树中路径最长的一条有多少结点。类似上面那个图，校长想知道哪个哪个院人数最多，不断向下分解为求哪个班人数最多。辅导员比较左右两个班哪个人数最多，返回最多的。然后院长比较哪个辅导员最多，返回最多的。在二叉树分解到叶子结点，就是要比较左右节点，如果有就返回1，不断累加
int TreeHigh(TNode* root)
{
if (root == NULL)
{
return 0;
}
/*return TreeHigh(root->_left) > TreeHigh(root->_right)
? TreeHigh(root->_left) + 1
: TreeHigh(root->_right)+ 1;*/
int left = TreeHigh(root->_left);
int right = TreeHigh(root->_right);
return left > right ? left + 1 : right + 1;
}
虽然上面两个方法都可以求得高度，但效率有很大的区别。屏蔽了的代码销毁慢很多，这种返回不会记录数量，每一次比较谁大都需要重新递归，越往节点上层对大的一方加1并不知道具体数量，所以需要将大的一方所有过程重新递归一遍，越往根节点走消耗等比增长。相当于校长想知道哪个班人数最多，班长返回给辅导员，辅导员往院长汇报没记录数量，又得重新走一遍最多的班询问数量，返回给院长，院长统计汇报时又得问辅导员数量，辅导员又得比较两个班长，将刚才的过程重复一遍，越往上，会将下一层整个过程重复，消耗越来越大
5. 第k层结点个数
求第k层的结点个数，求第3层的话，对于根节点来说就是求3层，对于根节点下一层来说就是求他的第2层，当k变为1的时候，意味着就是要求的这一层。放到学校体系里，想知道有多少个辅导员，就需要院长这一层来统计，所以想知道第3层有多少结点，就需要第2层来统计，往上汇总，所以有两个返回条件
1.结点为NULL，返回0
2.结点不为空，k是1
int TreeK(TNode* root, int k)
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeK(root->_left, k - 1) + TreeK(root->_right, k - 1);
}
当判断k是不是1的时候，节点为空在上面已经判断了。k代为3，画一下这个递归过程
6. 查找值
二叉树查找值返回的是节点的地址，需要注意递归中返回的不是最外层，而是返回给上一层调用自己的一层，需要保存返回值再往上一层层传递，上一层不断保存下一层传递上来的返回值
TNode* FindNode(TNode* root, TDataType x)
{
if (root == NULL)
return NULL;
if (root->_data == x)
{
return root;
}
//保存返回的结果
TNode* le = FindNode(root->_left, x);
if (le)
{
return le;
}
TNode* rig = FindNode(root->_right, x);
if (rig)
{
return rig;
}
//都没找到返回空
//return FindNode(root->_right, x);
return NULL;
}
7. 判断完全二叉树
完全二叉树的判断和层序遍历有关系。同样用一个队列，这时将空节点也压入，当层序遍历到空结点的时候，证明到了完全二叉树的结尾处，这时，如果出队列时有非空值就不是完全二叉树
bool isCompeteTree(TNode* root)
{
Queue que;
Init(&que);
if (root != NULL)
{
Push(&que, root);
}
while (!Empty(&que))
{
TNode* top = Front(&que);
//遇到空开始判断,如果有非空不是完全二叉树
Pop(&que);
if (top == NULL)
{
break;
}
//不是空就压入左右子树,需要压入空
Push(&que, top->_left);
Push(&que, top->_right);
}
//检查有没有非空
while (!Empty(&que))
{
TNode* top = Front(&que);
Pop(&que);
if (top != NULL)
{
Destory(&que);
return false;
}
}
return true;
}
8. 销毁
二叉树的销毁需要遵循后续遍历的原则,左右子树都销毁了才能销毁根节点
void Destory(TNode* root)
{
if (root == NULL)
{
return;
}
Destory(root->_left);
Destory(root->_right);
free(root);
}
9. OJ题
9.1 比较
相同的树: https://leetcode.cn/problems/same-tree/description/
思路
和遍历二叉树一样，在遍历的过程中比较，这里使用先序遍历，如果根不相等，就没必要往下继续比较了，最后返回这两个数与的结果，如果两个数都是空，就返回true，有一个不是空，就返回false，接着判断值
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);
}
9.2 单值二叉树
单值二叉树: https://leetcode.cn/problems/univalued-binary-tree/
思路
可以利用传递性，a=b=c，那么a=c。先比较根和左右节点是否相等，然后把子树当做根，比较它自己的左右子树，一直这样下去。注意判断反条件，因为相等得不出任何返回，还需要继续向下比较。最后递归返回两个子树向上传递的返回结果
bool isUnivalTree(struct TreeNode* root) {
if (root == NULL)
{
return true;
}
//比较子树的值和根节点的值,确保不是空
if (root->left && root->left->val != root->val)
{
return false;
}
if (root->right && root->right->val != root->val)
{
return false;
}
return isUnivalTree(root->left) && isUnivalTree(root->right);
}
9.3 镜像二叉树
镜像二叉树: https://leetcode.cn/problems/symmetric-tree/
思路
根结点不用比，因为没有对称节点。对称就是要根节点的左右节点互相相比。所以封装一个函数，分别传入根节点的左右结点，左子树的左节点和右子树的右结点，右结点和左节点相比
bool isSymmetriclr(struct TreeNode* left, struct TreeNode* right)
{
//都为空
if(left == NULL && right == NULL)
{
return true;
}
//有一个为空
if(left == NULL || right == NULL)
{
return false;
}
//值不相等
if(left->val != right->val)
{
return false;
}
//返回传递结果
return isSymmetriclr(left->left, right->right)
&& isSymmetriclr(left->right,right->left);
}
bool isSymmetric(struct TreeNode* root) {
return isSymmetriclr(root->left, root->right);
}
9.4 二叉树遍历
二叉树遍历：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/
思路
这个题目函数中给出了一个指针用来返回数组的大小，意思是将遍历结果放入数组之中。所以需要申请一个数组，而数组的大小可以先求一下二叉树的数量来确定，当前序遍历的时候，给定函数中不能递归，每次都会重新开辟空间。所以封装一个函数，传入这个数组指针，再记录一个下标，每放一下增加下标位置。要想让递归过程下标每放一次数据加一下，就得使用全局变量，但全局变量容易产生问题。所以传入一个指针，用下标访问每次改变下标值
int treesize(struct TreeNode* root) {
if (root == NULL) {
return 0;
}
return treesize(root->left) + treesize(root->right) + 1;
}
void preprint(struct TreeNode* root, int* ary, int* pi)
{
if(root == NULL)
{
return;
}
ary[(*pi)++] = root->val;
preprint(root->left,ary,pi);
preprint(root->right,ary,pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
//计算空间大小
*returnSize = treesize(root);
int* ary = (int*)malloc(sizeof(int) * (*returnSize));
int i = 0;
//传入数组和下标地址
preprint(root, ary, &i);
return ary;
}
9.5 子树
另一棵树的子树：https://leetcode.cn/problems/subtree-of-another-tree/description/
思路
可以利用前面的判断两个数相同的代码，在这里如果遇到空就返回false。先比较根结点，然后比较左右子树，递归这个过程。注意：只要有一次比较相同那么整个结果就是相同的
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 false;
}
if(isSameTree(root, subRoot))
{
return true;
}
return isSubtree(root->left, subRoot)
|| isSubtree(root->right,subRoot);
}
9.6 二叉树遍历
二叉树遍历: https://www.nowcoder.com/practice/4b91205483694f449f94c179883c1fef?tpId=60&&tqId=29483&rp=1&ru=/activity/oj&qru=/ta/tsing-kaoyan/question-ranking
先手动构建一下这个过程，给定字符串是先序的结果，所以第1个是根节点，第二个是左子树，根据这个顺序画出二叉树
思路
题目没给出，所以要自己写一个二叉树的结构体。根绝输入的字符串判断，如果是#，说明是空节点，就直接返回。如果不是，就创建该节点，然后链接递归自己的左右结点
#include <stdio.h>
typedef int TDataType;
typedef struct BinaryTreeNode {
TDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
} TNode;
TNode* BuyNode(TDataType data) {
TNode* newnode = (TNode*)malloc(sizeof(TNode));
if (newnode == NULL) {
perror("mallco");
return NULL;
}
//初始化数据
newnode->_data = data;
newnode->_left = NULL;
newnode->_right = NULL;
return newnode;
}
TNode* CreaTree(char* ary, int* p) {
if (ary[*p] == '#') {
(*p)++;
return NULL;
}
TNode* root = BuyNode(ary[*p]);
(*p)++;
root->_left = CreaTree(ary, p);
root->_right = CreaTree(ary, p);
return root;
}
void PrePrint(TNode* root) {
if (root == NULL) {
return;
}
PrePrint(root->_left);
printf("%c ", root->_data);
PrePrint(root->_right);
}
int main() {
char ary[100];
scanf("%s", ary);
int i = 0;
TNode* root = CreaTree(ary, &i);
PrePrint(root);
return 0;
}
![[网络安全 渗透实验 01]基于MSF框架渗透攻击Win7主机系统的设计与实现](https://img-blog.csdnimg.cn/direct/1c6fb7c29ac04197ac892037e942c4f5.png)
