comparison of BiTree

递归对比二叉链结构的二叉树

数据结构如下:

template<class T>
struct Node {
    T data;
    Node* lchild, * rchild;
};

实际方法如下:

#include <stdio.h>
using namespace std;

bool isEqual(Node<int>* bt1, Node<int>* bt2) {
	if (bt1 == NULL && bt2 == NULL)//正确的出口
		return true;
	else if (bt1 == NULL || bt2 == NULL)
		return false;
	else {
		cout << bt1->data << "," << bt2->data << endl;
		if (bt1->data != bt2->data)
			return false;
		return isEqual(bt1->lchild, bt2->lchild) && isEqual(bt1->rchild, bt2->rchild);
	}
}

生成测试二叉树函数如下:

//创建二叉树
//根据平衡二叉树规则生成
Node<int>* CreateBTtree(int a[], int n)
{
	Node<int>* root, * c, * pa = NULL, * p;
	int i;
	root = new Node<int>;
	root->data = a[0];
	root->lchild = root->rchild = NULL;
	for (i = 1; i < n; i++)
	{
		p = new Node<int>;
		p->lchild = p->rchild = NULL;
		p->data = a[i];
		c = root;
		while (c)
		{
			pa = c;
			if (c->data < p->data) //根节点小于待插入节点
				c = c->rchild;      //往右遍历
			else                  //根节点大于待插入节点 
				c = c->lchild;      //往左遍历
		}
		if (pa->data < p->data)
			pa->rchild = p;        //右放
		else
			pa->lchild = p;         //左放
	}
	return root;    //返回根节点
}

测试函数:

void test() {
	int a[8] = { 5, 3, 7, 2, 4, 6, 8, 9 };
	int b[8] = { 5, 3, 7, 2, 4, 6, 8, 15 };
	int c[7] = { 5, 3, 7, 2, 4, 6, 8 };
	int d[8] = { 5, 3, 7, 2, 4, 6, 8, 1 };
	Node<int>* bt1 = CreateBTtree(a, 8);
	Node<int>* bt2 = CreateBTtree(a, 8);
	Node<int>* bt3 = CreateBTtree(b, 8);
	Node<int>* bt4 = CreateBTtree(c, 7);
	Node<int>* bt5 = CreateBTtree(d, 8);
	cout << "A and B Equal or Not : " << (isEqual(bt1, bt2) ? "Equal" : "Not Equal") << endl;
	cout << "A and C Equal or Not : " << (isEqual(bt1, bt3) ? "Equal" : "Not Equal") << endl;
	cout << "A and D Equal or Not : " << (isEqual(bt1, bt4) ? "Equal" : "Not Equal") << endl;
	cout << "A and E Equal or Not : " << (isEqual(bt1, bt5) ? "Equal" : "Not Equal") << endl;
}

输出测试:

//output
5,5
3,3
2,2
4,4
7,7
6,6
8,8
9,15
A and C Equal or Not : Not Equal
5,5
3,3
2,2
4,4
7,7
6,6
8,8
9,empty
the nodes count not equal
A and D Equal or Not : Not Equal
5,5
3,3
2,2
empty,1
the nodes count not equal
A and E Equal or Not : Not Equal

G:\GithubProjects\C++\TrashCodes\Debug\TrashCodes.exe (进程 17836)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .