【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)

⭐️本篇博客我要给大家分享一下二叉树基本知识。希望对大家有所帮助。
⭐️ 博主码云gitee链接:码云主页

  系列文章

【初阶数据结构与算法】第一篇:算法中的时间复杂度和空间复杂度

【初阶数据结构与算法】第二篇:顺序表

【初阶数据结构与算法】第三篇:单链表

 【初阶数据结构与算法】第四篇:链表面试题详解

【初阶数据结构与算法】第五篇:双链表

【初阶数据结构与算法】第六篇:栈和队列(各个功能实现+练习题包含多种方法)

【初阶数据结构与算法】第七篇:二叉树和堆的基本概念+以及堆的实现

【初阶数据结构与算法】第八篇——二叉树的顺序结构的应用(堆排序+TOPK问题)


目录

  系列文章

前言

一、二叉树链式结构

        1.选择原因

二、二叉树简单创建

        链式结构

        创建二叉树,直接暴力创建 

三、二叉树遍历

        1.前序遍历

        2.中序遍历

        3.后序遍历

        4.层序遍历

四、二叉树基本操作

        二叉树的节点个数

                        方式一:全局遍历

                        方式二:局部遍历

                        方式三:递归分治

        二叉树的叶子节点个数

        二叉树第k层节点个数

        二叉树查找值为x的节点

        求二叉树的深度/高度

        二叉树的销毁

        完全二叉树判断

五,二叉树基本练习题

        单值二叉树(传送门)

        相同的树(传送门)

        对称二叉树(传送门)

        二叉树的前序遍历(传送门)

        二叉树的中序遍历(传送门)

        二叉树的后续遍历(传送门)

        另一颗树的子树(传送门)

        二叉树遍历(传送门)

         翻转二叉树(传送门)

        已知前中后序遍历其中两种,求剩下一种

总结


前言


一、二叉树链式结构

        1.选择原因

⭐️普通二插树没有增删查改的价值,单纯的为了存储数据不如线性表

⭐️链式二叉树可以更好控制结构

、二叉树简单创建

        链式结构

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

        创建二叉树,直接暴力创建 

BTNode* CreatBinaryTree()
{
    BTNode* treeNode1 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* treeNode2 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* treeNode3 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* treeNode4 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* treeNode5 = (BTNode*)malloc(sizeof(BTNode));
	BTNode* treeNode6 = (BTNode*)malloc(sizeof(BTNode));

	treeNode1->data = 'A';
	treeNode2->data = 'B';
	treeNode3->data = 'C';
	treeNode4->data = 'D';
	treeNode5->data = 'E';
	treeNode6->data = 'F';

	treeNode1->left = treeNode2;
	treeNode1->right = treeNode3;
	treeNode2->left = treeNode4;
	treeNode2->right = treeNode5;
	treeNode3->left = treeNode6;
	treeNode3->right = NULL;
	treeNode4->left = treeNode4->right = NULL;
	treeNode5->left = treeNode5->right = NULL;
	treeNode6->left = treeNode6->right = NULL;

    return treeNode1;
}

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第1张图片

、二叉树遍历

⭐️二叉树的遍历分为两类,一类是深度优先遍历,一类是广度优先遍历​​​​​​​

深度优先遍历:前序、中序和后序遍历,但是因为前序遍历是最先访问根在往深处走,所以是最符合深度优先的

广度优先遍历:层序遍历

        1.前序遍历

⭐️前序遍历指的是先遍历根,再遍历左子树,再遍历右子树
⭐️思想: 二叉树本身就是一种递归结构,所以通过递归来遍历这棵树,如何递归遍历呢?
是这样的,先遍历根,再遍历左子树,左子树又可以分解为,根、左子树和右子树,直到把所以左子树的部分遍历完,然后就遍历右子树,右子树又可以分解为,根、左子树和右子树。

void PreOrder(BTNode* root) {
    // 遍历到NULL就返回
	if (root == NULL) {
		printf("NULL ");
		return;
	}
    // 先遍历根
	printf("%c ", root->data);
    //再遍历左子树
	PreOrder(root->left);
    //再遍历右子树
	PreOrder(root->right);
}

        2.中序遍历

⭐️中序遍历指的是先遍历左子树,再遍历根,再遍历右子树
⭐️思想: 二叉树本身就是一种递归结构,所以通过递归来遍历这棵树,如何递归遍历呢?
是这样的,先遍历左子树,左子树又可以分解为,左子树、根和右子树,直到把所以左子树的部分遍历完,然后就遍历根,再遍历右子树,右子树又可以分解为,左子树、根和右子树。

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第2张图片

void PreOrder(BTNode* root) {
    // 遍历到NULL就返回
	if (root == NULL) {
		printf("NULL ");
		return;
	}
    //遍历左子树
	PreOrder(root->left);
    // 遍历根
	printf("%c ", root->data);
    //遍历右子树
	PreOrder(root->right);
}

        3.后序遍历

⭐️后序遍历指的是先遍历左子树再遍历右子树,再遍历根树
⭐️思想: 二叉树本身就是一种递归结构,所以通过递归来遍历这棵树,如何递归遍历呢?
是这样的,先遍历左子树,左子树又可以分解为,左子树、右子树和根,直到把所以左子树的部分遍历完,然后遍历右子树,右子树又可以分解为,左子树、右子树和根,最后遍历根。

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第3张图片

void PreOrder(BTNode* root) {
    // 遍历到NULL就返回
	if (root == NULL) {
		printf("NULL ");
		return;
	}
    //遍历左子树
	PreOrder(root->left);
    //遍历右子树
	PreOrder(root->right);
    // 遍历根
	printf("%c ", root->data);
}

        4.层序遍历

⭐️层序遍历是设置root为第一层,然后从第一层开始,从左往右一层一层向下遍历

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第4张图片

层序遍历通常用队列解决,首先将不为空的root放入到队列中,然后依次将队头取出,同时将root的左右不为空的子树存放到队头中,直到队列为空停止 

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第5张图片

//前置声明,
typedef struct BinaryTreeNode* QDataType;
//队列
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* head;
	QNode* tail;

	//size_t size;
}Queue;
//树
typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	int data;
}BTNode;
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = pq->tail = NULL;
}

void QueueDestory(Queue* pq)
{
	assert(pq);
	QNode* cur = pq->head;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	assert(newnode);

	newnode->data = x;
	newnode->next = NULL;

	if (pq->tail == NULL)
	{
		assert(pq->head == NULL);
		pq->head = pq->tail = newnode;
	}
	else
	{
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
}

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->head && pq->tail);

	if (pq->head->next == NULL)
	{
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else
	{
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
}

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);

	return pq->head->data;
}

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	//return pq->head == NULL && pq->tail == NULL;
	return pq->head == NULL;
}

// 层序遍历
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//如果root不是空,就把root放到队列中
	if (root)
	{
		QueuePush(&q, root);
	}
	//队列不为空,把队头数据出来
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		//将队列存的指针拿掉了,指针存的节点给了front
		QueuePop(&q);
		printf("%d ", front->data);
		//将root的左子树和右子树都放到队列中
		if (front->left)
		{
			QueuePush(&q, front->left);
		}

		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}

	printf("\n");
	QueueDestory(&q);
}

、二叉树基本操作

        二叉树的节点个数

                        方式一:全局遍历

int size = 0;//这里不妨思考下能不能直接放入BinaryTreeSize函数内部进行定义
int BinaryTreeSize(BTNode* root)
{
	if (root == NULL){
		return;
	}else{
		++size;
	}

	BinaryTreeSize(root->left);
	BinaryTreeSize(root->right);
}

                        方式二:局部遍历

void BinaryTreeSize(BTNode* root, int* psize)
{
	if (root == NULL)
		return;
	else
		++(*psize);

	BinaryTreeSize(root->left, psize);
	BinaryTreeSize(root->right, psize);
}

                        方式三:递归分治

⭐️空树,最小规模子问题,节点数返回0

⭐️非空,左子树节点数+右子树节点数+1(自己)

//3、分治,不再遍历
int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 1
		+ BinaryTreeSize(root->left)
		+ BinaryTreeSize(root->right);
}

        二叉树的叶子节点个数

⭐️分解为求左子树叶子节点个数+右子树叶子节点个数

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
    //第K层
	if (root->left == NULL && root->right == NULL)
		return 1;
    //既不是空也不是第K层
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

        二叉树第k层节点个数

⭐️求解左子树的第k-1层节点个数+右子树的第k-1层节点个数,当k==1时,就可以直接返回1,节点为空就返回0。

下面如果K==3,那么就是求A的第三层,B的第二层,D的第一层(直到为K为1时候,则找到所求层数,计数即可)

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第6张图片

int BinaryTreeLevelKSize(BTNode* root, int K)
{
    //检查K合法性
    assert(k >= 1);
	if (root == NULL)
	{
		return 0;
	}
	if (K == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, K- 1) + BinaryTreeLevelKSize(root->right, K - 1);

}

        二叉树查找值为x的节点

⭐️前序遍历一遍二叉树,先判断当前结点是否是目标,然后查找左子树,再查找右子树.

如果左右子树都没有找到,就返回NULL,直到找到x就返回。

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

        求二叉树的深度/高度

⭐️二叉树的高度等于1 + 左右子树高度的最大值.

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	int leftDepth = BinaryTreeDepth(root->left);
	int rightDepth = BinaryTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

        二叉树的销毁

⭐️直接依次分治递归销毁即可,这里置空root没有用,是临时变量,真正的root指针没有没有置空

void BinaryTreeDestory(BTNode* root) {
	if (root == NULL) {
		return ;
	}
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

        完全二叉树判断

⭐️首先创建一个队列,利用层序遍历,将每一层都遍历一遍,如果,遇到空了,则结束循环,之后再遍历判断如果不是空,则不是完全二叉树。

如果说上一层都从队列中出来了,那么下一层会全部进入队列,哪怕下一层都是空或者只有一个在最左边的节点或者最右边的节点

记得销毁队列,防止内存泄漏

// 完全二叉树判断	
bool Completely_binary_tree(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	//如果root不是空,就把root放到队列中
	if (root)
	{
		QueuePush(&q, root);
	}
	//队列不为空,把队头数据出来
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		//将队列存的指针拿掉了,指针存的节点给了front
		QueuePop(&q);
		//遇到空则结束循环
		if (front == NULL) {
			break;
		}
		//将root的左子树和右子树都放到队列中
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		//将队列存的指针拿掉了,指针存的节点给了front
		QueuePop(&q);
		//后面遇到空则说明不是完全二叉树
		if (front) {
			QueueDestory(&q);
			return false;
		}
	}
	QueueDestory(&q);
	return true;
}

五,二叉树基本练习题

        单值二叉树(传送门)

⭐️如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时,才返回 true;否则返回 false

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第7张图片

输入:[1,1,1,1,1,null,1]
输出:true

思路:

         当root为空时,说明此条分支遍历完了,直接返回true,如果root和left和right值不相等,返回false,同时判断left和right是不是为空,之后分治遍历左子树和右边子树

bool isUnivalTree(struct TreeNode* root){
    //为空不违反规则
    if(root == NULL){
        return true;
        //比较左边
    }else if(root->left && root->left->val != root->val){
        return false;
        //比较右边
    }else if(root->right && root->right->val != root->val){
        return false;
    }else{
        return isUnivalTree(root->left) && isUnivalTree(root->right);
    }
}

        相同的树(传送门)

⭐️给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第8张图片

输入:p = [1,2,3], q = [1,2,3]
输出:true
思路:

         当两个树都为空时,返回true,当两个树一个为空一个不为空时,返回false,当两个树都不为空时,如果两个树值不相等返回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);
}

        对称二叉树(传送门)

⭐️给你一个二叉树的根节点 root , 检查它是否轴对称。

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第9张图片

输入:root = [1,2,2,3,4,4,3]
输出:true

 思路:

        首先判断根是不是为空,然后将左子树和右子树一分为二比较,判断是否镜像相同,判断相同可参照上一题

bool _isSymmetric(struct TreeNode* q, struct TreeNode* p){
    //两个都是空
    if(q == NULL && p == NULL){
        return true;
    }
    //一个为空
    if(p == NULL || q == NULL){
        return false;
    }
    //两个都不为空,判断值是否相等
    if(q->val != p->val){
        return false;
    }
    return _isSymmetric(q->left, p->right) && _isSymmetric(q->right, p->left);
}

bool isSymmetric(struct TreeNode* root){
    //判断头是不是为空
    if(root == NULL){
        return true;
    }
    //之后一分为二,两边分开比较
    return _isSymmetric(root->left, root->right);
}

        二叉树的前序遍历(传送门)

⭐️给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第10张图片

输入:root = [1,null,2,3]
输出:[1,2,3]

  思路:

        首先计算树的节点个数,然后开辟相应的内存,之后将root和内存数组和数组下标地址单独传过去用函数分治判断,之后就是前置分治了

int TreeSize(struct TreeNode* root){
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//要传送i的地址,不然栈帧销毁的的时候i也就丢失了
void _preorderTraversal(struct TreeNode* root, int* arr, int* i){
    //这里判空了,主函数就不用判空了
    if(root == NULL){
        return ;
    }
    arr[(*i)++] = root->val;
    _preorderTraversal(root->left, arr, i);
    _preorderTraversal(root->right, arr, i);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){
    //为空直接返回即可
    // if(root == NULL){
    //     return NULL;
    // }
    //计算出数的长度
    int len = TreeSize(root);
    *returnSize = len;
    int* arr = (int*)malloc(sizeof(int)*len);
    int i = 0;
    //数组计算每一个节点
    _preorderTraversal(root, arr, &i);
    return arr;
}

        二叉树的中序遍历(传送门)

⭐️给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第11张图片

输入:root = [1,null,2,3]
输出:[1,3,2]

  思路:

        和前序思路基本一样

int TreeSize(struct TreeNode* root){
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//要传送i的地址,不然栈帧销毁的的时候i也就丢失了
void _inorderTraversal(struct TreeNode* root, int* arr, int* i){
    //这里判空了,主函数就不用判空了
    if(root == NULL){
        return ;
    }
    _inorderTraversal(root->left, arr, i);
    arr[(*i)++] = root->val;
    _inorderTraversal(root->right, arr, i);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize){
    //为空直接返回即可
    // if(root == NULL){
    //     return NULL;
    // }
    //计算出数的长度
    int len = TreeSize(root);
    *returnSize = len;
    int* arr = (int*)malloc(sizeof(int)*len);
    int i = 0;
    //数组计算每一个节点
    _inorderTraversal(root, arr, &i);
    return arr;
}

        二叉树的后续遍历(传送门)

⭐️给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第12张图片

输入:root = [1,null,2,3]
输出:[3,2,1]

  思路:

         和前序思路基本一样

int TreeSize(struct TreeNode* root){
    return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
//要传送i的地址,不然栈帧销毁的的时候i也就丢失了
void _postorderTraversal(struct TreeNode* root, int* arr, int* i){
    //这里判空了,主函数就不用判空了
    if(root == NULL){
        return ;
    }
    _postorderTraversal(root->left, arr, i);
    _postorderTraversal(root->right, arr, i);
    arr[(*i)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize){
    //为空直接返回即可
    // if(root == NULL){
    //     return NULL;
    // }
    //计算出数的长度
    int len = TreeSize(root);
    *returnSize = len;
    int* arr = (int*)malloc(sizeof(int)*len);
    int i = 0;
    //数组计算每一个节点
    _postorderTraversal(root, arr, &i);
    return arr;
}

        另一颗树的子树(传送门)

⭐️给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第13张图片

输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true

  思路:

        首先判断头是不是为空,然后将主树和子树传入比较相同的树中,然后依次分治递归主树左子树和右子树 

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;
    }
    //相等直接返回true,否则左右子树开始递归
    return isSameTree(root, subRoot)
         || isSubtree(root->left, subRoot)
         || isSubtree(root->right, subRoot);
}

        二叉树遍历(传送门)

⭐️编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

输入:

abc##de#g##f###

输出:

c b e g d f a 

 思路:

        首先创建一个数组a然后将数组a中所有元素按照前序遍历的思想创建一个树,之后按照中序遍历的思想打印出来

#include
#include
//创建一个节点
struct TreeNode
{
    char val;
    struct TreeNode* left;
    struct TreeNode* right;
};
//用前序遍历创建一个树
struct TreeNode* CreatTree(char* str,int* pi)
{
    //遇到#就返回空
    if(str[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    //创建节点
    struct TreeNode*root=(struct TreeNode*)
        malloc(sizeof(struct TreeNode));
    //将数组中的值给节点
    root->val=str[(*pi)++];
    //前序遍历
    root->left=CreatTree(str, pi);
    root->right=CreatTree(str, pi);
    
    return root;
}
//中序遍历
void InOrder(struct TreeNode* root)
{
    if(root==NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
}
    
    
int main()
{
    char str[100];
    scanf("%s",str);
    int i=0;
    struct TreeNode* root=CreatTree(str,&i);
    InOrder(root);
}

         翻转二叉树(传送门)

 ⭐️

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第14张图片

 思路:

        翻转每一个根的左右子树

struct TreeNode* _invertTree(struct TreeNode* root){
    //判断为空则直接返回空
    if(root == NULL){
        return NULL;
    }
    //交换左右子树
    struct TreeNode* tmp = root->left;
    root->left = root->right;
    root->right = tmp;
    //分治
    _invertTree(root->left);
    _invertTree(root->right);
    return root;
}

struct TreeNode* invertTree(struct TreeNode* root){
    //将根传送到子函数中交换
    return _invertTree(root);
}

         已知前中后序遍历其中两种,求剩下一种

⭐️已知某二叉树的前序遍历序列为5 7 4 9 6 2 1,中序遍历序列为4 7 5 6 9 1 2,则其后序遍历序列为

4 7 6 1 2 9 5

 思路:

        首先根据前序遍历,得到root是5,然后根据中序遍历7在5的左边,说明是5的左子树,然后根据中序遍历4在5的左边同时在7的左边,所以是7的左子树,然后根据中序遍历9在5的左边,是右子树,然后6在五的左边但是在9的右边所以是9的左子树,然后根据中序遍历2在9的右边所以是9的右子树,然后根据中序遍历1在2的左边9的右边所以是2的左子树

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第15张图片

 ⭐️已知某二叉树的中序遍历序列为JGDHKBAELIMCF,后序遍历序列为JGKHDBLMIEFCA,则其前序遍历序列为

 ABDGJHKCEILMF

  思路:

        首先根据后序遍历得到A是root,然后根据中序遍历C在A的右边所以是A右子树,根据中序遍历F在C的右边所以是C的右子树,根据中序遍历E在A的右边在C的前面,所以是C的左子树,根据中序遍历I在E的右边所以是E的右子树,M在I的右边,所以是I的右子树,L在I的左边E的右边,所以是I的左子树,B在A的左边所以是A的左子树,D在A的左边B的左边,所以是B的左子树,H在B的左边B的右边,所以是D的右子树,K在B的左边H的右边,所以是H的右子树,G在D的左边,所以是D的左子树,J在G的左边所以是G的左子树

【初阶数据结构与算法】第九篇——二叉树(链式结构实现+四种遍历方式+基本操作实现+基本练习详解)_第16张图片


总结

        二叉树初阶总算是学完了,中间递归思想和其他分治之类的都值得反复咀嚼。

你可能感兴趣的