【二叉树 OJ题】二叉树基础知识 与 OJ题完成（二叉树构建与遍历问题，子树查找问题）
【二叉树 OJ题】二叉树基础知识 与 OJ题完成（二叉树构建与遍历问题，子树查找问题）
二叉树 ！
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 二叉树的概念
一棵二叉树是结点的一个有限集合，该集合:
- 或者为空
- 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
注意： 二叉树不存在度大于2的结点 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
2.2 二叉树的构建
相比一般的树来说，二叉树的构建就十分简单了，只需要左右两个节点即可。
typedef char BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
}BTNode;多个节点串联即可构成一棵二叉树。
2.3 特殊的二叉树
- 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。
- 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
3 二叉树OJ题的解决
3.1 二叉树构建与遍历问题
该OJ题存在两个子问题，分别是二叉树构建和二叉树遍历。
3.1.1 二叉树遍历
我们首先解决遍历问题，遍历是构建的基础。 首先，二叉树的遍历主要有三种：
- 前序遍历: 先打印父节点 ，然后打印左子树，最后打印右子树。
- 中序遍历：先打印左子树，然后打印父节点，最后打印右子树。
- 后序遍历：先打印左子树，在打印右子树，最后打印父节点。 假如有这样一棵树（题目所给）
我们分别用前序遍历，中序遍历，后序遍历演示一遍。是这样的，然后我以前序遍历为例剖析一下结构。
前序解剖为
一层套一层，层层递归。 代码实现也非常简单
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 子树查找问题
这道题我一开始的想法是检查对应每一个节点，每次只能取出一棵树中的一个节点的数据，再取出另一棵树的节点数据进行比较。但是后来发现，这种思路是非常麻烦、非常不可行的思路。
首先我完成基本的检查工作：
- 都为空则相同
- 其一为空则不同
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);- 如果issame检查返回真，则存在。
- 如果左右子树的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♪(･ω･)ﾉ
腾讯云开发者
