1. 二叉树
当一个树不是满二叉树或完全二叉树时,它是不适合使用数组存储的,它应该使用链式结构来存储。
再看二叉树基本操作前,再回顾下二叉树的概念,二叉树是:
- 空树
- 非空:根节点,根节点的左子树、根节点的右子树组成的。
从概念中可以看出,二叉树定义是递归式的,因此后序基本操作中基本都是按照该概念实现的。
所以可以定义成下面这种:
typedef int TNDataType;
typedef struct TreeNode
{
TNDataType val;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
2.二叉树的遍历
所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。
按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:
- 前序遍历——访问根结点的操作发生在遍历其左右子树之前。 (根左右)
- 中序遍历——访问根结点的操作发生在遍历其左右子树之中(间)。(左根右)
- 后序遍历——访问根结点的操作发生在遍历其左右子树之后。(左右根)
2.1前序遍历
前序遍历:先访问树的根,然后访问左子树(左子树又被分为根、左子树、右子树,直到左子树不能拆分),然后再访问右子树(右子树又被分为根、左子树、右子树,直到右子树不能拆分)
先遍历根(有根一直根),然后左(有左一直左),最后右,拆分了以后就从头来
遍历结果 1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
谁的NULL: 3 3 2 5 5 6 6
void PreOrder(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->val);//先遍历根
PreOrder(root->left);//然后遍历左子树
PreOrder(root->right);//最后遍历右子树
}
2.2中序遍历
中序遍历:有左子树就一直访问左子树,直到左子树不能再拆分,然后遍历根,最后遍历右子树(右子树又拆分为根、左子树、右子树。也得先访问左子树)
有左一直左,然后根,最后右,拆分了以后就从头来
遍历结果: NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
谁的NULL: 3 3 2 5 5 6 6
void InOrder(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);//先遍历左子树
printf("%d ", root->val);//再遍历根
InOrder(root->right);//最后遍历右子树
}
2.3后序遍历
后序遍历:先遍历左子树(左子树又拆分为:根、左子树、右子树),然后遍历右子树(右子树又拆分为:根、左子树、右子树),最后遍历根。
有左一直左,然后右,最后根,拆分了以后就从头来
遍历结果: NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
谁的NULL: 3 3 2 5 5 6 6
//后序遍历
void PostOrder(TreeNode* root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);//先遍历左子树
PostOrder(root->right);//再遍历右子树
printf("%d ", root->val);//最后访问根
}
2.4层序遍历
二叉树的层序遍历需要借助队列实现。
首先需要将根入队列,然后再出队列,出队列时,需要将自己的孩子带进队列之中。由于栈先进先出的特点,只有上一层全部出完了才会出当前层,故可以实现层序遍历。
需要注意的是:链表的数值域设置为指向树节点的指针
//树的结构
typedef int TNDataType;
typedef struct TreeNode
{
TNDataType val;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
//链表的节点
typedef TreeNode* QNodeDataType;//将链表的数值域设置为指向树节点的指针
typedef struct QueueNode
{
QNodeDataType data;
struct QueueNode* next;
}QNode;
//层序遍历
void TreeLevelOrder(TreeNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
//出数据
TreeNode* front = QueueFront(&q);
QueuePop(&q);
if (front)
{
printf("%d ", front->val);
//出的数据将其孩子带进队列中(带下一层)
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
else
{
printf("N ");
}
}
printf("\n");
QueueDestroy(&q);
}
3.树的节点个数
方法:当前节点只加自己,然后再加上左子树和右子树中节点的个数
int TreeSize(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
return 1 + TreeSize(root->left) + TreeSize(root->right);
}
4.树的高度
当前层加上子树中高度大的一个
int TreeHeight(TreeNode* root)
{
if (root == NULL)
{
return 0;
}
int left = TreeHeight(root->left);
int right = TreeHeight(root->right);
return left > right ? left + 1 : right + 1;
}
5.叶子节点的个数
是叶子,返回1;不是叶子,继续遍历左右子树,空树返回0
int BinaryTreeLeafSize(TreeNode* root)
{
//空树,返回空
if (root == NULL)
{
return 0;
}
//叶子,返回1
if (root->left == NULL && root->right == NULL)
{
return 1;
}
//继续遍历左右子树
return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
6.第k层节点的个数
不是第k层就继续遍历左右子树,空树返回0;第k层就返回1。
假设K等于3
int TreeKLevel(TreeNode* root, int k)
{
//空树
if (root == NULL)
{
return 0;
}
//到第k层
if (k == 1)
{
return 1;
}
//未到第k层,继续在左右子树中寻找
//层数减少
return TreeKLevel(root->left,k-1) + TreeKLevel(root->right,k-1);
}
7.查找x所在的节点
当前节点为空数,返回NULL,当前节点是x,返回x的地址;当前节点不是x,先在左子树中找,左子树找不到,再到右子树中找。
TreeNode* TreeFind(TreeNode* root, int x)
{
if (root == NULL)
{
return NULL;
}
if (root->val == x)
{
return root;
}
//先在左子树中找
TreeNode* left = TreeFind(root->left,x);
if (left)//找到了返回
{
return left;
}
//左子树找不到。那就在右子树中找
TreeNode* right = TreeFind(root->right, x);
if (right)
{
return right;//找到了,返回
}
//左右都找不到,整棵树都找不到
return NULL;
}
8.树的销毁
//树的销毁,采用后序遍历销毁
void TreeDestroy(TreeNode* root)
{
if (root == NULL)
return;
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
9.相关题目
9.1相同的树
题目链接
先比较两树的根是否相等,若相等,在比较子树是都对应相等;若不相等,直接返回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(q->right,p->right);
}
9.2单值二叉树
题目链接
若当前节点的值不等于根的值,直接false;若当前节点为NULL,则返回true,当前节点不是空,则检查它左树与右数的值等不等于根的值。
bool UnivalTree(struct TreeNode* root ,int val)
{
if(root == NULL)
{
return true;
}
if(root->val != val)
{
return false;
}
return UnivalTree(root->left,val) && UnivalTree(root->right,val);
}
bool isUnivalTree(struct TreeNode* root) {
if(root == NULL)
{
return true;
}
int val = root->val;
return UnivalTree(root,val);
}
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对称二叉树
题目链接
bool check(struct TreeNode* left,struct TreeNode* right)
{
if(left == NULL && right == NULL)
{
return true;
}
if(left == NULL || right == NULL)
{
return false;
}
//当前节点相等,遍历左右子树
return left->val == right->val
&& check(left->left,right->right)
&& check(left->right,right->left);
}
bool isSymmetric(struct TreeNode* root) {
if(root == NULL)
{
return true;
}
return check(root->left,root->right);
}
9.4二叉树的构建
题目链接
//前序遍历,构建二叉树
TreeNode* CreatTree(char* a, int* pi)
{
if (a[*pi] == '#')
{
(*pi)++;
return NULL;
}
//先构建根
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = a[(*pi)++];
//然后构建左右子树
root->left = CreatTree(a, pi);
root->right = CreatTree(a, pi);
return root;
}
9.5翻转二叉树
题目链接
思路:将根的子树依次进行交换
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;
}
9.6另一颗树的子树
题目链接
其实这一题就是9.1的变种,本质上还是找两棵相同的树。文章来源:https://www.toymoban.com/news/detail-841403.html
- 若当前根节点与另一棵树相等,那就从当前节点开始,依次比较子树,检查是否相等。
- 若子树为空或与另一棵树不相等,则返回false.
bool isSameTree(struct TreeNode* root, struct TreeNode* subRoot)
{
if(root == NULL && subRoot == NULL)
return true;
if(root == NULL || subRoot == NULL)
return false;
if(root->val != subRoot->val)
return false;
return isSameTree(root->left,subRoot->left)
&& isSameTree(root->right,subRoot->right);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root == NULL)
return false;//此处是false
if(root->val == subRoot->val && isSameTree(root,subRoot))
return true;
return isSubtree(root->left,subRoot)
|| isSubtree(root->right,subRoot);
}
10.判断二叉树是否是完全二叉树
思路:与层序遍历类似,依然使用入队出队的方式。‘
如果当前出队元素为NULL,则队中的剩余元素必须全部为空,否则就不是一棵完全二叉树。文章来源地址https://www.toymoban.com/news/detail-841403.html
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(TreeNode* root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
TreeNode* front = QueueFront(&q);
QueuePop(&q);
//若当前出队元素不是空,则该元素出队,将它的孩子进队
if (front)
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
else
{
//当前出的元素是空,停止出
break;
}
}
//继续出,检查有无非空节点
while (!QueueEmpty(&q))
{
TreeNode* front = QueueFront(&q);
QueuePop(&q);
if (front != NULL)
{
return false;
}
}
QueueDestroy(&q);
return true;
}
到了这里,关于【数据结构】二叉树的相关操作以及OJ题目的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!