按先序遍历序列建立两个二叉树的二叉链表 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都是n阶矩阵，如存在矩阵P使P^(-1)AP=B，就称矩阵A相似与矩阵B，记成A~B。
 
与几何的相似不同，矩阵相似是比等价还要强的条件。
 
相似的性质（必要条件）：
 1.特征值相等。这个结论是由特征多项式相等推出来的。
 2.A和B的秩相等。
 3.A和B的行列式相等。
 4.A和B的迹相等。迹就是n阶矩阵主对角线上的元素之和。
 
这是大部分老师会让我们记住的4条矩阵相似的必要条件，但是在判断矩阵相似时，题目往往上面4个条件都是相等的，所以我们就不能用上面4个必要条件去否定了，然后我们也不知道矩阵相似的充分条件是什么，题目就不好做。下面给出相似的必要条件5，并把第一个必要条件做一些加强，这样就可以解决大部分考研题目了。
 
1.特征值相等，且每个特征值对应的特征向量个数相等。
 5.A-kE和B-kE也是相似的。
 
1的证明：
 若A~B，对于某个特征值λ，若B有一个线性无关的特征向量α，则Bα=λα成立，于是 (P^-1)APα=λα，即APα=λPα也成立。所以说人话就是B有一个特征向量阿尔法，则A对于同样的特征值，也有一个线性无关的向量Pα。虽然我们不知道P，但是我们可以断定A和B的每个特征值的特征向量个数是相同的。
 
2的证明：
 若A~B，则B-kE = (P^-1)AP - k(P^-1)P = (P^-1)/(A-kE)P。即A-kE~B-kE。
 
下面来做几道题。
 
例题：和矩阵 [公式] 相似的矩阵（）
 
 
我们可以看到，选项的行列式，秩，迹都是相同的，这就是考研难度的题目。
 我们可以用强化后的必要条件2，但是更好的是我们不去求矩阵的特征值。让我们用性质5来做这道题。
 
我们把这5个矩阵都减去2E，然后发现题干的矩阵秩是1，而选项里只要C-2E的秩是1，其他的都是2。
 所以得出这题选C。

按先序遍历序列建立两个二叉树的二叉链表 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;
      
}  

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;
}