中诺建设集团有限公司网站,山东网站制作定制,水务局政务网站建设工作总结,企业网站建设 论文文章目录一、单值二叉树二、检查两颗树是否相同三、判断一棵树是否为另一颗树的子树四、对称二叉树五、二叉树的前序遍历六、二叉树中序遍历七、二叉树的后序遍历八、二叉树的构建及遍历一、单值二叉树
单值二叉树
题目描述
如果二叉树每个节点都具有相同的值#xff0c;那…
文章目录一、单值二叉树二、检查两颗树是否相同三、判断一棵树是否为另一颗树的子树四、对称二叉树五、二叉树的前序遍历六、二叉树中序遍历七、二叉树的后序遍历八、二叉树的构建及遍历一、单值二叉树
单值二叉树
题目描述
如果二叉树每个节点都具有相同的值那么该二叉树就是单值二叉树只有给定的树是单值二叉树时才返回 true否则返回 false。
示例 思路分析
一棵树的所有节点都有相同的值当且仅当对于树上的每一条边的两个端点它们都有相同的值这样根据传递性所有节点都有相同的值
因此我们可以对树进行一次深度优先搜索当搜索到节点root时我们检查root的左孩子和右孩子是否相同不相同则返回false,直到检查了所有的节点所有我们就可以进行递归遍历每次比较根节点和左右孩子的val值是否相等不相等就返回false然后递归比较左子树和右子树。
【注意】我们比较的条件应该是不相等因为不相等就可以直接返回而相等还要继续比较
代码实现
bool isUnivalTree(struct TreeNode* root)
{// 根节点为空返回trueif (root NULL)return true;// 左子树存在但是不相等则返回falseif (root-left root-val ! root-left-val)return false;// 右子树存在但是不相等则返回falseif (root-right root-val ! root-right-val)return false;// 继续递归 左右子树return isUnivalTree(root-left) isUnivalTree(root-right);
}二、检查两颗树是否相同
题目链接
检查两颗树是否相同
题目描述
给你两棵二叉树的根节点 p 和 q 编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。
示例 思路分析
如果两个二叉树都为空则两个二叉树相同。如果两个二叉树中有且只有一个为空则两个二叉树一定不相同如果两个二叉树都不为空那么首先判断它们的根节点的值是否相同若不相同则两个二叉树一定不同若相同再分别判断两个二叉树的左子树是否相同以及右子树是否相同。这是一个递归的过程因此可以使用深度优先搜索递归地判断两个二叉树是否相同。
代码实现
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{// 如果根节点都为NULL则返回tureif (p NULL q NULL)return true;// 运行到这里都不为空则下面判断的情况为只有一个为空另一个不为空所以返回falseif (p NULL || q NULL)return false;// 都不为空但是值不相等返回falseif (p-val ! q-val)return false;// 继续比较左右子树return isSameTree(p-left, q-left) isSameTree(p-right, q-right);
} 三、判断一棵树是否为另一颗树的子树
题目链接
判断一棵树是否为另一颗树的子树
题目描述
给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在返回 true 否则返回 false 。
二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树
示例 思路分析
由于root和subRoot中可能含有一个和多个值相同的节点所以判断不相等的时候又要返回原来的根节点所以我们可以这道题利用上一题的代码我们的思路为不断的比较root这棵树以每一个节点作为根节点判断是否和subRoot相等相等就返回true,所以节点都变量之后都没有相等的树就返回false.
代码实现
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{// 如果根节点都为NULL则返回tureif (p NULL q NULL)return true;// 运行到这里都不为空则下面判断的情况为只有一个为空另一个不为空所以返回falseif (p NULL || q NULL)return false;// 都不为空但是值不相等返回falseif (p-val ! q-val)return false;// 继续比较左右子树return isSameTree(p-left, q-left) isSameTree(p-right, q-right);
}bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {if (root NULL){return false;}if (isSameTree(root, subRoot)){return true;}return isSubtree(root-left, subRoot) || isSubtree(root-right, subRoot);}四、对称二叉树
题目链接
对称二叉树
题目描述
给你一个二叉树的根节点 root 检查它是否轴对称
示例 思路分析
这道题和判断两棵树是否相等的思路一致只是有一些细节有所不同。对称二叉树是最左边和最右边的节点相同所以我们就可以拿第一棵树的左子树和第二棵树的右子树进行比较拿第一棵树的右子树和第二棵树的左子树进行比较不相等就返回false,相等就继续比较直到所有节点都相等所以我们就可以对检查两颗是否相同的代码进行修改即可即对其递归代码中的参数进行调整
return isSameTree(p-left,q-right)isSameTree(p-right,q-left);代码实现
//判断两颗子树是否对称
bool isSameTree(struct TreeNode* p,struct TreeNode* q)
{if(pNULLqNULL){return true;}// 当两棵树中只有一棵树的节点为NULL时节点数量不相等直接返回falseif(pNULL||qNULL){return false;}// 检查节点的值是否相等if(p-val!q-val){return false;}// 检查左右子树是否对称return isSameTree(p-left,q-right)isSameTree(p-right,q-left);
}
bool isSymmetric(struct TreeNode* root){return isSameTree(root-left,root-right);
}五、二叉树的前序遍历
题目链接
二叉树的前序遍历
题目描述
给你二叉树的根节点 root 返回它节点值的 前序 遍历。
示例 思路分析
二叉树的前序遍历我们已经非常熟悉这里我提出两点需要注意的地方
1.由于二叉树的节点数是未知的为了不浪费空间我们可以先求出二叉树的节点数然后开辟对应大小的空间
2.由于数据存储在一个数组中所以我们需要一个变量i来控制数组的下标由于在递归调用的过程中对形参的改变不会改变影响实参所以这里我们需要传递i的地址通过指针来控制i的增长
代码实现
// 计算节点个数
int TreeSize(struct TreeNode* root)
{if (root NULL)return 0;// 左子树的节点个数右节点的个数1return TreeSize(root-left) TreeSize(root-right) 1;
}
// 前序遍历并存入数组中
void preorder(struct TreeNode* root, int* a, int* pi)
{if (root NULL)return;// 先遍历根再访问左子树左后访问右子树a[*pi] root-val;(*pi);preorder(root-left, a, pi);preorder(root-right, a, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{// 求二叉树的节点个数int size TreeSize(root);// 开辟同等大小的空间int* a (int*)malloc(sizeof(int) * size);int i 0;//前序遍历preorder(root, a, i);*returnSize size;return a;
}六、二叉树中序遍历
题目链接
二叉树中序遍历
题目描述
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。
示例 二叉树的中序遍历和前序遍历一样只是访问节点的顺序不同
代码实现
// 计算节点个数
int TreeSize(struct TreeNode* root)
{if (root NULL)return 0;// 左子树的节点个数右节点的个数1return TreeSize(root-left) TreeSize(root-right) 1;
}
// 前序遍历并存入数组中
void inorder(struct TreeNode* root, int* a, int* pi)
{if (root NULL)return;// 先遍历左子树再访问根节点左后访问右子树inorder(root-left, a, pi);a[*pi] root-val;(*pi);inorder(root-right, a, pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{// 求二叉树的节点个数int size TreeSize(root);// 开辟同等大小的空间int* a (int*)malloc(sizeof(int) * size);int i 0;//中序遍历inorder(root, a, i);*returnSize size;return a;
}七、二叉树的后序遍历
题目链接
二叉树的后序遍历
题目描述
给你一棵二叉树的根节点 root 返回其节点值的 后序遍历 。
示例 思路分析
二叉树的后序遍历和前序遍历中序遍历一样只是访问节点的顺序不同
代码实现
代码实现
// 计算节点个数
int TreeSize(struct TreeNode* root)
{if (root NULL)return 0;// 左子树的节点个数右节点的个数1return TreeSize(root-left) TreeSize(root-right) 1;
}
// 后序遍历并存入数组中
void postorder(struct TreeNode* root, int* a, int* pi)
{if (root NULL)return;// 先遍历左子树再访问右子树左后访问根节点postorder(root-left, a, pi);postorder(root-right, a, pi);a[*pi] root-val;(*pi);
}
int* postorderTraversal(struct TreeNode* root, int* returnSize)
{// 求二叉树的节点个数int size TreeSize(root);int* a (int*)malloc(sizeof(int) * size);int i 0;// 后续遍历postorder(root, a, i);*returnSize size;return a;
}八、二叉树的构建及遍历
题目链接
二叉树的构建及遍历
题目描述
编一个程序读入用户输入的一串先序遍历字符串根据此字符串建立一个二叉树以指针方式存储。 例如如下的先序遍历字符串 ABC##DE#G##F### 其中“#”表示的是空格空格字符代表空树。建立起此二叉树以后再对二叉树进行中序遍历输出遍历结果。
输入描述
输入包括1行字符串长度不超过100。
输出描述
可能有多组测试数据对于每组数据 输出将输入字符串建立二叉树后中序遍历的序列每个字符后面都有一个空格。 每个输出结果占一行。
示例 思路分析
这道题目是前序建立二叉树和中序遍历我们写成两个子函数即可对于二叉树的创建字符为‘#’说明节点为空我们直接返回即可然后依次递归创建节点即可
代码实现
#include stdio.h
#include stdlib.h// 符号和结构的定义
typedef char BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
} BTNode;// 构建二叉树
BTNode* BTreeCreate(char* a, int* pi)
{if (a[*pi] #){(*pi);return NULL;}// 创建根节点BTNode* root (BTNode*)malloc(sizeof(BTNode));if (root NULL) {perror(malloc fail);exit(-1);}root-data a[*pi];(*pi);// 创建左子树和右子树root-left BTreeCreate(a, pi);root-right BTreeCreate(a, pi);return root;
}
// 二叉树中序遍历
void InOrder(BTNode* root)
{if (root NULL){return;}// 先访问左子树再访问根节点最后访问右子树InOrder(root-left);printf(%c , root-data);InOrder(root-right);
}int main()
{char str[100];scanf(%s, str);// 创建二叉树int i 0;BTNode* root BTreeCreate(str, i);// 二叉树的中序遍历InOrder(root);return 0;
}
