二叉树 ！
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); }
