-
25.二叉树的应用实例 算法设计:判断两棵二叉树A与B是否相似,即要么它们都为空或都只有一个根结点,要么...
2020-10-28 08:21:10算法设计:判断两棵二叉树A与B是否相似,即要么它们都为空或都只有一个根结点,要么它们的左右子树均相似。 算法思路: 1、保留之前所写二叉树头文件内容。 2、再设计判断相似算法Like(BiTreeNode *A, BiTreeNode *...25.二叉树的应用实例
算法设计:判断两棵二叉树A与B是否相似,即要么它们都为空或都只有一个根结点,要么它们的左右子树均相似。
算法思路:
1、保留之前所写二叉树头文件内容。
2、再设计判断相似算法Like(BiTreeNode *A, BiTreeNode *B),该算法功能是:若A与B相似,则函数返回1,否则返回0,具体如下:
(1)若A== B==NULL,则A与B相似,即Like(A,B)=1;
(2)若A与B有一个为NULL,另一个不为NULL,则A与B不相似,即Like(A,B)=0;
(3)采用递归方法,进一步判断A的左子树和B的左子树、A的右子树和B的右子树是否相似。
3、在主函数中实现,验证两棵树是否相似。(需要先建立两棵树,然后再判定)头文件1:BiTree.h
#include<stdio.h> #include<stdlib.h> typedef char DataType; typedef struct Node { DataType data; struct Node* leftChild; struct Node* rightChild; }BiTreeNode; void Initiate(BiTreeNode** root) { *root = (BiTreeNode*)malloc(sizeof(BiTreeNode)); (*root)->leftChild = NULL; (*root)->rightChild = NULL; } BiTreeNode* InsertLeftNode(BiTreeNode* curr, DataType x) { BiTreeNode* s, * t; if (curr == NULL) return NULL; t = curr->leftChild; s = (BiTreeNode*)malloc(sizeof(BiTreeNode)); s->data = x; s->leftChild = t; s->rightChild = NULL; curr->leftChild = s; return curr->leftChild; } BiTreeNode* InsertRightNode(BiTreeNode* curr, DataType x) { BiTreeNode* s, * t; if (curr == NULL) return NULL; t = curr->rightChild; s = (BiTreeNode*)malloc(sizeof(BiTreeNode)); s->data = x; s->rightChild = t; s->leftChild = NULL; curr->rightChild = s; return curr->rightChild; } void Destroy(BiTreeNode** root) { if ((*root) != NULL && (*root)->leftChild != NULL) Destroy(&(*root)->leftChild); if ((*root) != NULL && (*root)->rightChild != NULL) Destroy(&(*root)->rightChild); free(*root); }
头文件2:BiTreeTraverse.h
#include"BiTree.h" void Visit(DataType item) { printf("%c ", item); } void PrintBiTree(BiTreeNode* root, int n) { int i; if (root == NULL) return; PrintBiTree(root->rightChild, n + 1); for (i = 0; i < n - 1; i++) printf(" "); if (n > 0) { printf("---"); printf("%c\n", root->data); } PrintBiTree(root->leftChild, n + 1); } BiTreeNode* Search(BiTreeNode* root, DataType x) { BiTreeNode* find = NULL; if (root != NULL) { if (root->data == x) find = root; else { find = Search(root->leftChild, x); if (find == NULL) find = Search(root->rightChild, x); } } return find; } void PreOrder(BiTreeNode* t, void Visit(DataType item)) { if (t != NULL) { Visit(t->data); PreOrder(t->leftChild, Visit); PreOrder(t->rightChild, Visit); } } void InOrder(BiTreeNode* t, void Visit(DataType item)) { if (t != NULL) { InOrder(t->leftChild, Visit); Visit(t->data); InOrder(t->rightChild, Visit); } } void PostOrder(BiTreeNode* t, void Visit(DataType item)) { if (t != NULL) { PostOrder(t->leftChild, Visit); PostOrder(t->rightChild, Visit); Visit(t->data); } }
源文件:main.c
#include"BiTreeTraverse.h" int Like(BiTreeNode* a, BiTreeNode* b) { if ((a == NULL && b != NULL) || (a != NULL && b == NULL)) return 0; if (a == NULL && b == NULL) return 1; return Like(a->leftChild, b->leftChild) && Like(a->rightChild, b->rightChild); } int main() { BiTreeNode* root1, * root2, * p, * pp; Initiate(&root1); Initiate(&root2); p = InsertLeftNode(root1, '2'); p = InsertLeftNode(p, '6'); p = InsertRightNode(root1->leftChild, '4'); pp = p; p = InsertLeftNode(p, '5'); p = InsertLeftNode(p, '3'); InsertRightNode(pp, '1'); p = InsertLeftNode(root2, '1'); p = InsertLeftNode(p, '2'); p = InsertRightNode(root2->leftChild, '3'); pp = p; p = InsertLeftNode(p, '4'); p = InsertLeftNode(p, '5'); InsertRightNode(pp, '7'); PrintBiTree(root1, 0); printf("\n"); PrintBiTree(root2, 0); if (Like(root1, root2)) printf("两棵树相似!\n"); else printf("两棵树不相似!\n"); Destroy(&root1); Destroy(&root2); return 0; }
-
判断两棵二叉树是否相似。
2020-05-08 12:33:12按先序遍历序列建立两个二叉树的二叉链表 A 和链表 B ,设计算法判断 A 、 B 二叉树是否相似。...A与B相似↵ #include <iostream> #include <list> #include <string> usi...按先序遍历序列建立两个二叉树的二叉链表 A 和链表 B ,设计算法判断 A 、 B 二叉树是否相似。
注:其中“#”表示的是空格,空格字符代表空树。
测试用例1ab#c##d##↵ xc#v##b##↵
期待输出1
A与B相似↵
#include <iostream> #include <list> #include <string> using namespace std; string treeA; string treeB; int lenA; int lenB; int curIndex = 0; int layer; struct tree { public: char data; tree *left; tree *right; }; void CreateTreeA(int curLayer, tree *node); void CreateTreeB(int curLayer, tree *node); bool Equal(tree* nodeA, tree* nodeB); int main() { cin >> treeA; cin >> treeB; lenA = treeA.size(); lenB = treeB.size(); int power = 0; while (((2 << power) - 1) < lenA) { power++; } layer = power + 1; tree *TreeA = new tree; CreateTreeA(1, TreeA); power = 0; while (((2 << power) - 1) < lenB) { power++; } layer = power + 1; curIndex = 0; tree *TreeB = new tree; CreateTreeB(1, TreeB); if (Equal(TreeA, TreeB)) { cout << "A与B相似" << endl; } else { cout << "A与B不相似" << endl; } return 0; } void CreateTreeA(int curLayer, tree *node) { if (treeA[curIndex] != '#') { node->data = treeA[curIndex++]; } else { curIndex++; } if (node->left == NULL && curIndex < lenA && curLayer + 1 <= layer) { tree *tmp = new tree; node->left = tmp; tmp->data = ' '; tmp->left = NULL; tmp->right = NULL; CreateTreeA(curLayer + 1, node->left); } if (node->right == NULL && curIndex < lenA && curLayer + 1 <= layer) { tree *tmp = new tree; node->right = tmp; tmp->data = ' '; tmp->left = NULL; tmp->right = NULL; CreateTreeA(curLayer + 1, node->right); } } void CreateTreeB(int curLayer, tree *node) { if (treeB[curIndex] != '#') { node->data = treeB[curIndex++]; } else { curIndex++; } if (node->left == NULL && curIndex < lenB && curLayer + 1 <= layer) { tree *tmp = new tree; node->left = tmp; tmp->data = ' '; tmp->left = NULL; tmp->right = NULL; CreateTreeB(curLayer + 1, node->left); } if (node->right == NULL && curIndex < lenB && curLayer + 1 <= layer) { tree *tmp = new tree; node->right = tmp; tmp->data = ' '; tmp->left = NULL; tmp->right = NULL; CreateTreeB(curLayer + 1, node->right); } } bool Equal(tree* nodeA, tree* nodeB) { if (nodeA == NULL && nodeB == NULL) { return true; } if ((nodeA == NULL && nodeB != NULL) || (nodeA != NULL && nodeB == NULL)) { return false; } if ((nodeA->data == ' '&&nodeB->data == ' ') || nodeA->data != ' '&&nodeB->data != ' ') { return Equal(nodeA->left, nodeB->left) && Equal(nodeA->right, nodeB->right); } else { return false; } }
-
C++数据结构 判断两棵二叉树是否相似
2020-06-03 22:17:37按先序遍历序列建立两个二叉树的二叉链表 A 和链表 B ,设计算法判断 A 、 B 二叉树是否相似。 注:其中“#”表示的是空格,空格字符代表空树。 测试输入 ab#c##d##↵ xc#v##b##↵ 期待的输出 A与B相似↵ 测试输入 ...按先序遍历序列建立两个二叉树的二叉链表 A 和链表 B ,设计算法判断 A 、 B 二叉树是否相似。
注:其中“#”表示的是空格,空格字符代表空树。
测试输入 ab#c##d##↵ xc#v##b##↵ 期待的输出 A与B相似↵ 测试输入 ab#c##d##↵ gv##d##↵` 期待的输出 A与B不相似↵ #include<iostream> #include<string> #include<cstdio> using namespace std; class binarytreenode { public: char data; binarytreenode * Lchild, * Rchild; binarytreenode() { Lchild = NULL; Rchild = NULL; } }; class binarytree { public: binarytreenode * root; binarytree() { root =NULL; } void createtree( binarytreenode * &p) { char ch; cin >> ch; if (ch == '\n') return; if (ch == '#') p = NULL; else { p = new binarytreenode(); if (!p) exit(-1); p->data = ch; createtree(p->Lchild); createtree(p->Rchild); return; } } }; bool similar(binarytreenode *t1, binarytreenode *t2) { bool leftS = false, rightS = false; if (t1 == NULL && t2 == NULL) // 两树皆空 return true; else if (t1 == NULL || t2 == NULL) // 只有一个树为空 return false; else // 递归地进行判断 { leftS = similar(t1->Lchild, t2->Lchild); rightS = similar(t1->Rchild, t2->Rchild); return leftS && rightS; } } int main() { binarytree x, t; x.createtree(x.root); t.createtree(t.root); bool flag; flag=similar(x.root, t.root); if (flag) cout << "A与B相似\n"; else cout << "A与B不相似\n"; return 0; }
-
实对称矩阵的性质_矩阵是否相似于对角阵的判别
2020-12-03 14:20:52性质如果A与B相似,则有:(1)A与B的秩相同(2) A与B的行列式相同(3) A与B的特征多项式相同,特征值相同,特征向量不一定相同!(4) A与B的迹相同【注】矩阵A的迹等于A的主对角线元素的和3.矩阵的相似对角化4.矩阵A相似...今天给大家带来的知识点:矩阵是否相似于对角阵的判别!
01
—
矩阵的相似
1.定义
2.性质
如果A与B相似,则有:
(1)A与B的秩相同
(2) A与B的行列式相同
(3) A与B的特征多项式相同,特征值相同,特征向量不一定相同!
(4) A与B的迹相同
【注】矩阵A的迹等于A的主对角线元素的和
3.矩阵的相似对角化
4.矩阵A相似对角化的条件这部分内容在考研中非常重要!!!判断方法如下:(1)判断A是否实对称,实对称矩阵一定相似于对角阵(2)求A的所有特征值 (i)如果A的所有特征值都是单根,则A一定可以相似对角化 (ii) 如果A的特征值中有重根,假设是r重根,若此时该重根对应的特征向量个数也是r,则A一定可以对角化。若少于r,则A不能对角化。02
—
经典例题
下列矩阵中,不能相似于对角阵的是()
答案:C
解析:
(A)是实对称矩阵,一定相似于对角阵!(B)有3个不同的特征值,一定相似于对角阵!(C)-1是矩阵C的三重特征根,求出对应的特征向量个数为 1,所以不能对角化,具体求解请同学们自行尝试。(D)0是矩阵D的二重特征根,求出对应的特征向量个数为2, 矩阵D的另一特征根为-1,所以可以对角化。20191012(每日一题)
答案:x=3, y=-2, A,B都可以相似对角化!
【感兴趣的童鞋可以尝试做做2019年考研数学一第21题第二问】
每天10分钟,搞定一道考研题型!喜欢的朋友可以转发加关注哦
-
15. 三数之和 ----- 排序+双指针(与两数之和相似)
2020-06-12 09:49:52给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。 示例: 给定数组 nums = [-1, 0,... -
Codeforces Round #313 (Div. 1) B. Equivalent Strings DFS暴力
2017-02-27 12:11:00判断俩字符串是否相似,相似的条件如下: a1+a2=A,a1和a2都是A的一半 b1+b2=B,同理 如果A,B相等,那么相似 如果A的长度为偶数{ 如果a1与b1,a2与b2相似或者a1与b2,b1与a2相似 那么A,B相似 } ... -
NOI上字符串判等问题,测试结果无误,可是最后判...希望大神帮改正错误或给出一个与原答案相似且可通过的答案
2019-11-13 21:00:01判断两个由大小写字母和空格组成的字符串在忽略大小写,且忽略空格后是否相等。 输入 两行,每行包含一个字符串。 输出 若两个字符串相等,输出YES,否则输出NO。 样例输入 a A bb BB ccc CCC Aa BBbb CCCccc... -
c语言数据结构问题 代码相似性度量
2013-11-07 11:20:34将这两个代码分别转换为token串后,基于算法RKR-GST( running-karp-rabin greedy-string-tiling)算法思想,循环求取两个标记串中未被匹配部分的最大公共子串,将其用空格代替,并根据公式求出两个token串A,B的... -
JavaScript 中是如何比较两个元素是否 "相同" 的
2021-01-10 01:54:22接下来我们可以先根据 a 和 b 的类型来判断,如果类型不一样,那么就没必要继续判断了。如何获取变量类型?没错,就是神奇的 <code>Object.prototype.toString.call</code>! 如果... -
Python中&与and有什么区别?
2020-09-25 20:40:21,|)和(and,or)是两组比较相似的运算符,用在“与”/ “或”上,在用法上有些许区别。 (&,|)和(and,or)是用来比较两组变量的,格式基本上是: a & b a | b a and b a or b 如果a,b是数值变量, ... -
向量点乘与向量叉乘的几何意义
2019-02-01 17:50:04点乘的结果是是标量,点乘也被称为内积,是a向量在b向量上投影的长度与b向量的长度的乘积,反映了两个向量之间的相似度,两向量越相似,它们的点积就越大。 内积(点乘)的几何意义: 表征或计算两个向量之间的... -
剑指Offer-树的子结构
2015-08-29 00:11:44先判断A的根结点是否与B的树根相同,若相同,则遍历B的同时遍历A,判断是否相似。 否则判断A的左子树是否与B的树根相同,若相同,则遍历B的同时遍历A的左子树,判断是否相似。 同理A的右子树也一样的方法判断... -
请教一个与f-measure值有关的问题,谢谢!
2020-03-22 21:41:221. 映射c:对于数据集A与B,通过映射函数f,找到映射c{c:a=b,a属于A,b属于B}。 2. 假设条件:对于任何一个映射c,被一系列映射函数f1.。。fi找到,这些映射函数越不同,映射c越有可能是正确的。 根据假设... -
python两字符串比较常用函数
2020-09-25 10:44:50表达式判断b是否包含在a中,返回布尔类型 a.find(b) 在a中从左到右查找b字符串 a.rfind(b) 在a中从右往左查找b字符串 返回第一次找到的位置,如没有返回-1 a.rfind(b, 2, 9)可以限定查找范围 a.index(b)和a.rindex(b... -
hdu 5423 Rikka with Tree(dfs)bestcoder #53 div2 1002
2015-08-31 19:48:002. 对于树A与树B,如果A与B的节点数相同,且无论i为何值,f[A, i]与f[B, i]都相等,则A与B为两棵相似的树。 3. 对于一棵树A,在以节点1为根节点的情况下,如果不存在与其它树与A相似,则A是一棵... -
浅谈Python中(&,|)和(and,or)之间的区别
2021-01-20 05:49:30(&,|)和(and,or)是两组比较相似的运算符,用在“与”/ “或”上,在用法上有些许区别。 (&,|)和(and,or)是用来比较两组变量的,格式基本上是: a & b a | b a and b a or b 如果a,b是数值变量, 则&... -
力扣第 221 场周赛
2020-12-27 18:51:51判断字符串的两半是否相似5638. 吃苹果的最大数目5210. 球会落何处5640. 与数组中元素的最大异或值经历 5637. 判断字符串的两半是否相似 class Solution: def halvesAreAlike(self, s: str) -> bool: score = ... -
python 中的一些细节知识- is = == 的区别,深浅拷贝的理解
2018-12-27 18:01:22a == 1 表示判断a是否等于1 a is 1 表示a 与1是否为相同的对象。 对于b同理。 我们会发现一些比较意外的结果。对于一个整数,我们可以很容易通过多种方式来确定相等。然而对于列表对象,我们发现is的表现与其他... -
CCF通信网络
2020-04-11 18:38:50此题目有环因此设置一个maze[1005][1005]判断之前a到b是否已经基数,也可不设判断tt[a]+tt[b] >= n - 1; 此题与poj3660相似poj3360(vj上的) #include<iostream> #include <map> #include <... -
图片有的不显示.br标签和a标签直接显示出来.版本0.1.0. 文本如下
2020-12-04 13:58:15结点的插入和删除和单链表非常相似,就不再示范了。 <p><strong>双链表 <img alt="" src="http://my.csdn.net/uploads/201204/26/1335454807_2626.png" /><br /> 双链表拥有一前一后两个指针域,... -
计算歌曲相似度:Jaccard系数
2014-02-15 16:02:38可以看出,其含义是集合A、B中相同的个数,除以A与B交集个数。可以看出,Jaccard系统主要关注的是元素是的个体是否相同,而不能用数值具体表示其差异。从这个意义上讲,我认为适合我的音乐,音乐推荐中计算相似度的... -
POJ-1931 Biometrics
2016-08-22 16:23:35题目链接:http://poj.org/problem?id=1931判断两个多边形是否相似 多边形相似充要条件:多边形A的任何两点之间长度,与多边形B对应的两个点 长度比值都相等注意一下顺时针和逆时针,还有数值的范围*/#include #... -
python中的 &,| 和 and or
2018-09-04 14:28:36假如a与b进行运算分下面情况: 如果a b是数值变量: # &, | 表示二进制的位运算 1 & 2 # 结果为0 1 | 2 # 结果为3 # 判断变量是否为0, 是0则为False,非0判断为True, # and... -
三角形
2017-12-12 20:33:00TanYz的三角形 发布时间: 2017年12月11日 14:05 最后更新: 2017年12月11日 14:46 时间限制: 1000ms 内存限制...秒掉A题之后,发现B题虽然与A题相似,但是TanYz看得一脸懵逼,完全不会。 想到CF(伪)又要掉分,TanYz... -
LeetCode 四数之和 Java 双指针
2020-08-21 16:19:43给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。 注意:答案中不可以包含重复的... -
LeetCode 四数之和
2020-12-22 12:20:44给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。 注意: 答案中不可以包