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 二叉树是否相似。
注：其中“#”表示的是空格，空格字符代表空树。

测试用例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相似↵

测试输入
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;
      
}  

	

今天给大家带来的知识点：矩阵是否相似于对角阵的判别！
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分钟，搞定一道考研题型！喜欢的朋友可以转发加关注哦