精华内容
下载资源
问答
  • 算法设计:判断两棵二叉树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;
    }
    
    展开全文
  • 按先序遍历序列建立两个二叉树的二叉链表 A 和链表 B ,设计算法判断 A 、 B 二叉树是否相似。...A与B相似↵ #include <iostream> #include <list> #include <string> usi...

    按先序遍历序列建立两个二叉树的二叉链表 A 和链表 B ,设计算法判断 A 、 B 二叉树是否相似。

    注:其中“#”表示的是空格,空格字符代表空树。
    测试用例1

    ab#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;
    	}
    }
    
    展开全文
  • 按先序遍历序列建立两个二叉树的二叉链表 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;
          
    }  
    
    
    展开全文
  • 性质如果A与B相似,则有:(1)A与B的秩相同(2) A与B的行列式相同(3) A与B的特征多项式相同,特征值相同,特征向量不一定相同!(4) A与B的迹相同【注】矩阵A的迹等于A的主对角线元素的和3.矩阵的相似对角化4.矩阵A相似...

    今天给大家带来的知识点矩阵是否相似于对角阵的判别!

    01

    矩阵的相似

    1.定义

    d53f8c94e8feebf3a59f33cd7eb5e962.png

    2.性质

    如果A与B相似,则有:

    (1)A与B的秩相同

    (2)  A与B的行列式相同

    (3)  A与B的特征多项式相同,特征值相同,特征向量不一定相同!

    (4)  A与B的迹相同

    【注】矩阵A的迹等于A的主对角线元素的和

    3.矩阵的相似对角化

    1e8793811102ca9e36a24ca82d1c2930.png

    4.矩阵A相似对角化的条件这部分内容在考研中非常重要!!!判断方法如下:(1)判断A是否实对称实对称矩阵一定相似于对角阵(2)求A的所有特征值      (i)如果A的所有特征值都是单根,则A一定可以相似对角化        (ii)  如果A的特征值中有重根,假设是r重根若此时该重根对应的特征向量个数也是r,则A一定可以对角化。若少于r,则A不能对角化。

    02

    经典例题

    下列矩阵中,不能相似于对角阵的是()

    9c2ee5556601a50b3e28b20f493106d5.png

    答案:C

    解析:

    (A)是实对称矩阵,一定相似于对角阵!(B)有3个不同的特征值,一定相似于对角阵!(C)-1是矩阵C的三重特征根,求出对应的特征向量个数为             1,所以不能对角化,具体求解请同学们自行尝试。(D)0是矩阵D的二重特征根,求出对应的特征向量个数为2,         矩阵D的另一特征根为-1,所以可以对角化。

    20191012(每日一题)

    26e933e7ce25f565b24625908329bea2.png

    答案:x=3, y=-2,  A,B都可以相似对角化!

    感兴趣的童鞋可以尝试做做2019年考研数学一第21题第二问

    每天10分钟,搞定一道考研题型!喜欢的朋友可以转发加关注哦

                    8cb570125d204afc89f0d479fcda4b11.png

    展开全文
  • 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 ab,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。 注意:答案中不可以包含重复的三元组。 示例: 给定数组 nums = [-1, 0,...
  • 判断俩字符串是否相似,相似的条件如下: a1+a2=A,a1和a2都是A的一半 b1+b2=B,同理 如果A,B相等,那么相似 如果A的长度为偶数{  如果a1b1,a2b2相似或者a1b2,b1a2相似  那么A,B相似 } ...
  • 判断两个由大小写字母和空格组成的字符串在忽略大小写,且忽略空格后是否相等。 输入 两行,每行包含一个字符串。 输出 若两个字符串相等,输出YES,否则输出NO。 样例输入 a A bb BB ccc CCC Aa BBbb CCCccc...
  • 将这两个代码分别转换为token串后,基于算法RKR-GST( running-karp-rabin greedy-string-tiling)算法思想,循环求取两个标记串中未被匹配部分的最大公共子串,将其用空格代替,并根据公式求出两个token串AB的...
  • 接下来我们可以先根据 ab 的类型来判断,如果类型不一样,那么就没必要继续判断了。如何获取变量类型?没错,就是神奇的 <code>Object.prototype.toString.call</code>! 如果...
  • ,|)和(and,or)是两组比较相似的运算符,用在“”/ “或”上,在用法上有些许区别。 (&,|)和(and,or)是用来比较两组变量的,格式基本上是: a & b a | b a and b a or b 如果ab是数值变量, ...
  • 向量点乘向量叉乘的几何意义

    千次阅读 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的右子树也一样的方法判断...
  • 1. 映射c:对于数据集A与B,通过映射函数f,找到映射c{c:a=b,a属于A,b属于B}。 2. 假设条件:对于任何一个映射c,被一系列映射函数f1.。。fi找到,这些映射函数越不同,映射c越有可能是正确的。 根据假设...
  • 表达式判断b是否包含在a中,返回布尔类型 a.find(b) 在a中从左到右查找b字符串 a.rfind(b) 在a中从右往左查找b字符串 返回第一次找到的位置,如没有返回-1 a.rfind(b, 2, 9)可以限定查找范围 a.index(b)和a.rindex(b...
  • 2. 对于树A与树B,如果A与B的节点数相同,且无论i为何值,f[A, i]与f[B, i]都相等,则A与B为两棵相似的树。 3. 对于一棵树A,在以节点1为根节点的情况下,如果不存在与其它树与A相似,则A是一棵...
  • (&,|)和(and,or)是两组比较相似的运算符,用在“”/ “或”上,在用法上有些许区别。 (&,|)和(and,or)是用来比较两组变量的,格式基本上是: a & b a | b a and b a or b 如果ab是数值变量, 则&...
  • 力扣第 221 场周赛

    2020-12-27 18:51:51
    判断字符串的两半是否相似5638. 吃苹果的最大数目5210. 球会落何处5640. 数组中元素的最大异或值经历 5637. 判断字符串的两半是否相似 class Solution: def halvesAreAlike(self, s: str) -> bool: score = ...
  • a == 1 表示判断a是否等于1 a is 1 表示a 1是否为相同的对象。 对于b同理。 我们会发现一些比较意外的结果。对于一个整数,我们可以很容易通过多种方式来确定相等。然而对于列表对象,我们发现is的表现其他...
  • CCF通信网络

    2020-04-11 18:38:50
    此题目有环因此设置一个maze[1005][1005]判断之前ab是否已经基数,也可不设判断tt[a]+tt[b] >= n - 1; 此题poj3660相似poj3360(vj上的) #include<iostream> #include <map> #include <...
  • 结点的插入和删除和单链表非常相似,就不再示范了。 <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 #...
  • 假如a与b进行运算分下面情况: 如果a b是数值变量: # &amp;, | 表示二进制的位运算 1 &amp; 2 # 结果为0 1 | 2 # 结果为3   # 判断变量是否为0, 是0则为False,非0判断为True,   # and...
  • 三角形

    2017-12-12 20:33:00
    TanYz的三角形 发布时间: 2017年12月11日 14:05 最后更新: 2017年12月11日 14:46 时间限制: 1000ms 内存限制...秒掉A题之后,发现B题虽然与A相似,但是TanYz看得一脸懵逼,完全不会。 想到CF(伪)又要掉分,TanYz...
  • 给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 ab,c 和 d ,使得 a + b + c + d 的值 target 相等?找出所有满足条件且不重复的四元组。 注意:答案中不可以包含重复的...
  • LeetCode 四数之和

    2020-12-22 12:20:44
    给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 ab,c 和 d ,使得 a + b + c + d 的值 target 相等?找出所有满足条件且不重复的四元组。 注意: 答案中不可以包

空空如也

空空如也

1 2 3 4
收藏数 65
精华内容 26
关键字:

判断a与b是否相似