main.cpp

将森林转化为相应二叉树的算法

#include<iostream.h>
#include"BinaryTree.h"
#include"forest.h"
template<class T>
BinaryTree<T>* Forest2Binary(Tree<T>* tree);
void main()
{
/*
一下的定义仅用来检测函数的正确性，而与函数体无关
本程序中没有做用户界面
下面的定义生成的树的结构见文件夹中的tree.jpg
转化成的二叉树结构见btree.jpg
*/
TreeNode<int> a(0);
TreeNode<int> b(1);
TreeNode<int> c(2);
TreeNode<int> d(3);
TreeNode<int> e(4);
TreeNode<int> f(5);
TreeNode<int> g(6);
//设置结点关系
a.setChild(&b);
b.setSibling(&c);
c.setSibling(&d);
b.setChild(&e);
e.setChild(&f);
c.setChild(&g);
//建树
Tree<int> tree(&a);
//转换为二叉树
BinaryTree<int>* bnTree=Forest2Binary(&tree);
}
//函数体
template<class T>
BinaryTree<T>* Forest2Binary(Tree<T>* tree)
{
	using std::queue;
	queue<BinaryTreeNode<T>*> BinaryQueue;//定义一个保存二叉树结点的队列
	queue<TreeNode<T>*> TreeQueue;//定义一个保存树结点的队列
	TreeNode<T>* tPointer=NULL;//TreeQueue的首个元素
	BinaryTreeNode<T>* bPointer=NULL;//BinaryTree的首个元素
	BinaryTreeNode<T>* broot=NULL;//生成的二叉树的根结点
	BinaryTreeNode<T>* newbp=NULL;//临时变量用来产生子结点
	tPointer=tree->getRoot();//tPointer的初值为树的根
	if (tPointer)bPointer=new BinaryTreeNode<T>(tPointer->Value());
	broot=bPointer;//broot的初值为二叉树的跟
	TreeQueue.push(tPointer);//压入根
	BinaryQueue.push(bPointer);
	while(!TreeQueue.empty())
	{
		tPointer=TreeQueue.front();
		bPointer=BinaryQueue.front();
		while(tPointer!=NULL)
		{
			if(tPointer->LeftMostChild())
			{//查找是否有左孩子,有的话建立当前二叉树结点的左子结点
				newbp=new BinaryTreeNode<T>(tPointer->LeftMostChild()->Value());
				bPointer->setLeftchild(newbp);
				TreeQueue.push(tPointer->LeftMostChild());
				BinaryQueue.push(newbp);//将左子结点压入队列待处理
			}
			if(tPointer->RightSibling())
			{//查找是否有右兄弟,有的话建立当前二叉树结点的右子结点
				newbp=new BinaryTreeNode<T>(tPointer->RightSibling()->Value());
				bPointer->setRightchild(newbp);
			}
			tPointer=tPointer->RightSibling();//指向tPointer的右兄弟
			bPointer=bPointer->rightchild();//指向bPointer的右子结点
		}
		TreeQueue.pop();
		BinaryQueue.pop();
	}
	BinaryTree<T> bnTree(broot);//建立以broot为根的二叉树
	return &bnTree;//返回引用
}