【二叉树 OJ题】二叉树基础知识 与 OJ题完成(二叉树构建与遍历问题,子树查找问题)

2023-12-15 10:29:46

二叉树 !

1 树

1.1 树的概念

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。
在这里插入图片描述

把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。有一个特殊的结点,称为根结点,根节点没有前驱结点除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继因此,树是递归定义的

1.2 树的相关概念

1.节点的度:一个节点含有的子树的个数称为该节点的度;
2.叶节点或终端节点:度为0的节点称为叶节点;
3.非终端节点或分支节点:度不为0的节点;
4.双亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点;
5.孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点;
6.兄弟节点:具有相同父节点的节点互称为兄弟节点;
7.树的度:一棵树中,最大的节点的度称为树的度;
8.节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推;
9.树的高度或深度:树中节点的最大层次; 如上图:树的高度为5
10.堂兄弟节点:双亲在同一层的节点互为堂兄弟;
11.节点的祖先:从根到该节点所经分支上的所有节点;
12.子孙:以某节点为根的子树中任一节点都称为该节点的子孙。
13.森林:由m(m>0)棵互不相交的树的集合称为森林;

1.3 树的表示方式

一般来说最简单的想法是使用复杂链表结构

typedef int TreeData;
typedef struct TreeNode
{
   TreeData val;
   struct TreeNode* node1
   struct TreeNode* node2
   struct TreeNode* node3
  ...
  ...
  ...

}treenode;

可以发现,这样设置无法应对所有结构,并且冗杂混乱。所以有位大佬发明了一种十分巧妙的办法:孩子兄弟表示法
每个节点只有两个指向,其一指向最左边的孩子节点,另一指向右边的兄弟节点。如此往复成功构建了树的结构。

typedef int TreeData;
typedef struct TreeNode
{
 TreeData val; // 结点中的数据域
 struct Node* firstChild1; // 第一个孩子结点
 struct Node* pNextBrother; // 指向其下一个兄弟结点
}treenode;

在这里插入图片描述

2 二叉树

2.1 二叉树的概念

一棵二叉树是结点的一个有限集合,该集合:

  1. 或者为空
  2. 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
    在这里插入图片描述
    注意:
    二叉树不存在度大于2的结点
    二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
    现实中的二叉树

2.2 二叉树的构建

相比一般的树来说,二叉树的构建就十分简单了,只需要左右两个节点即可。

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

多个节点串联即可构成一棵二叉树。

2.3 特殊的二叉树

  1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是
    说,如果一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。
  2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

在这里插入图片描述

3 二叉树OJ题的解决

3.1 二叉树构建与遍历问题

二叉树构建与遍历问题链接
在这里插入图片描述
该OJ题存在两个子问题,分别是二叉树构建和二叉树遍历。

3.1.1 二叉树遍历

我们首先解决遍历问题,遍历是构建的基础。
首先,二叉树的遍历主要有三种:

  1. 前序遍历: 先打印父节点 ,然后打印左子树,最后打印右子树。
  2. 中序遍历:先打印左子树,然后打印父节点,最后打印右子树。
  3. 后序遍历:先打印左子树,在打印右子树,最后打印父节点。
    假如有这样一棵树(题目所给)
    在这里插入图片描述

我们分别用前序遍历,中序遍历,后序遍历演示一遍。是这样的,然后我以前序遍历为例剖析一下结构。
在这里插入图片描述

前序解剖为
在这里插入图片描述
一层套一层,层层递归。
代码实现也非常简单

typedef char BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
void BinaryTreePrevOrder(BTNode* root){
	if(!root) {
		printf("# ");
		return;
	}
	
    printf("%c ",root->data);//打印父节点
    BinaryTreePrevOrder(BTNode* root->left);//遍历左子树
    BinaryTreePrevOrder(BTNode* root->right);//遍历右子树
}

中序遍历和后序遍历只需要调换最后三行代码相对位置即可。

3.1.2 二叉树构建

题目给我们的输入样式为
输入:abc##de#g##f###(前序遍历)
‘#’表示空格,可以理解为二叉树里的空节点NULL。
‘字母’表示每个节点储存的数据
我们只要层层遍历,遇到‘#’记作NULL,反之记录节点数据,并依次遍历左子树,右子树。我们使用‘pi’为下标来完成数组的读取操作。

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

TreeNode* treecreate(char* str,int* pi){
       if(str[*pi] == '#'||str[*pi]=='\0') {
           (*pi)++;
           return NULL;
       }//'#'和‘\0’记作NULL
       //不为空则创建新节点
       TreeNode* node =(TreeNode*)malloc(sizeof(TreeNode));
       node->data=str[*pi];
       (*pi)++;//数组下标增加
       //遍历左子树
       node->left = treecreate(str, pi);
       //遍历右子树
       node->right = treecreate(str, pi);
       //返回当前节点
       return node;
}

int main() {  
   char str[100] = "\0";
   scanf("%s",str);
   int pi = 0;//记录下标
   //二叉树创建
   TreeNode* root = treecreate(str,&pi);
   return 0;
}

3.1.3 题目完成

根据上面两个子问题我们就解决了该OJ题
在这里插入图片描述

3.2 子树查找问题

子树查找问题链接
在这里插入图片描述
这道题我一开始的想法是检查对应每一个节点,每次只能取出一棵树中的一个节点的数据,再取出另一棵树的节点数据进行比较。但是后来发现,这种思路是非常麻烦、非常不可行的思路。

首先我完成基本的检查工作:

  1. 都为空则相同
  2. 其一为空则不同
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(!root&&!subRoot) return true;//如果都为空,则相同
    if(!root) return false;//在第一条前提下 root为空肯定是假
    if(!subRoot) return false;//在第一条前提下 subRoot为空也肯定是假
}

这三条可以完成一个基本的判定。
然后我们看看如何检查子树是否存在。这个思路也很清晰:
3. 都为空则相同
4. 其一为空 则不同
5. 数据不同 则不同
6. 递归检查左右子树,必须都为真才可以

bool issame(struct TreeNode* root, struct TreeNode* subRoot){
    if(!root&&!subRoot) return true;
    if(!root) return false;
    if(!subRoot) return false;
    if(root->val != subRoot->val) return false;
   
    return issame(root->left,subRoot->left) && issame(root->right,subRoot->right);
    
}

最后关键一步是这一行代码

return issame(root,subRoot) || isSubtree(root->left,subRoot) ||isSubtree(root->right,subRoot);
  1. 如果issame检查返回真,则存在。
  2. 如果左右子树的isSubtree返回真,则存在
    主要还是issame函数的作用,后面两个isSubroot是为了防止root为空了无法正确判断来补充。
    完整代码
bool issame(struct TreeNode* root, struct TreeNode* subRoot){
    if(!root&&!subRoot) return true;
    if(!root) return false;
    if(!subRoot) return false;
    if(root->val != subRoot->val) return false;
   
    return issame(root->left,subRoot->left) && issame(root->right,subRoot->right);
    
}

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
    if(!root&&!subRoot) return true;
    if(!root) return false;
    if(!subRoot) return false;
        
    return issame(root,subRoot) || isSubtree(root->left,subRoot) || isSubtree(root->right,subRoot);
   
    
}

Thanks?(・ω・)ノ

下一篇文章见!!!

文章来源:https://blog.csdn.net/JLX_1/article/details/134913551
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。