【整理自用】二叉树的子树、子结构

大家好，欢迎来到IT知识分享网。

二叉树的子树和子结构

简单而言，与子树不同的是，子结构可以是A树的任意一部分。
这里以一颗7节点，高度为3的满二叉树为例，说明子树和子结构的差别：

图1

1.图1的子树示意图

对于图1而言，子树意味着图2，图3等情况。根据定义非常好理解。

图2 图1子树的某一种情况

图3 图1子树的某一种情况

2.图1的子结构示意图

3.求二叉树A子树的代码

 //函数声明，这里是为了先看首先要调用的函数，才放到后面去的。 bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2); //正式开始第一个函数 bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { //因为定义空树不是任何一个树的子树，因此如果有个根节点是空树，那么直接返回false if(pRoot1 == NULL || pRoot2 == NULL) return false; bool result = false; //如果当前两个树节点值相同，就调用其他函数判断能否以当前节点为根节点下找到相同的子树。 if(pRoot1->val == pRoot2->val) { result = isSubtree(pRoot1, pRoot2); } //如果不同或者是以当前节点为根节点下找不到相同的子树，那么就看看A树的左节点或者右节点中有没有。 if(!result) result = HasSubtree(pRoot1->left, pRoot2); if(!result) result = HasSubtree(pRoot1->right, pRoot2); return result; } bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { //因为是子树：只要包含了一个结点，就得包含这个结点下的所有节点。 //因此，A树与其子树一定最后同时访问到空指针。 if(pRoot2 == NULL && pRoot1 == NULL) return true; else if(pRoot2 != NULL && pRoot1 != NULL) { if(pRoot1->val != pRoot2->val) { return false; } return isSubtree(pRoot1->left, pRoot2->left) && isSubtree(pRoot1->right, pRoot2->right); } else return false; }

4. 求二叉树A子结构的代码

因此，对于子结构而言，只要在子结构访问到空指针之前，所有的节点均和A树的某部分相同就可以了。

 //函数声明，这里是为了先看首先要调用的函数，才放到后面去的。 bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2); //正式开始第一个函数 bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { //因为定义空树不是任何一个树的子树，因此如果有个根节点是空树，那么直接返回false if(pRoot1 == NULL || pRoot2 == NULL) return false; bool result = false; //如果当前两个树节点值相同，就调用其他函数判断能否以当前节点为根节点下找到相同的子树。 if(pRoot1->val == pRoot2->val) { result = isSubtree(pRoot1, pRoot2); } //如果不同或者是以当前节点为根节点下找不到相同的子树，那么就看看A树的左节点或者右节点中有没有。 if(!result) result = HasSubtree(pRoot1->left, pRoot2); if(!result) result = HasSubtree(pRoot1->right, pRoot2); return result; } bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { //这里不一样！！！！ //这里不一样！！！！ //这里不一样！！！！ //子结构访问到空指针时，和A树的比较都一直是true就是true. //而这个函数能一直循环下去，就意味着之前的比较都是true,因此，这里程序改为 if(pRoot2 == NULL) return true; else if(pRoot1 == NULL) return false; else if(pRoot2 != NULL && pRoot1 != NULL) { if(pRoot1->val != pRoot2->val) { return false; } return isSubtree(pRoot1->left, pRoot2->left) && isSubtree(pRoot1->right, pRoot2->right); } else return false; }