towtrees.cpp

几乎包括二叉树的所有编程算法

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <cassert>
using namespace std;


// struct define
struct Node
{
	char c;
	Node* left;
	Node* right;
	bool leftVisite;
	bool rightVisite;
	Node()
	{
		c = 0;
		left = 0;
		right = 0;
		leftVisite = false;
		rightVisite = false;
	}
};


// 按先序扩展序列建立二叉树
Node* createTree(const string& allNodes);
void displayTree(Node* tree);
// 先序、中序、后序遍历的递归算法
void firstTravel(Node* tree);
void midTravel(Node* tree);
void lastTravel(Node* tree);
// 先序遍历的非递归算法, 基于堆栈
void _firstTravel(Node* tree);
// 中序遍历的非递归算法, 基于堆栈
void _midTravel(Node* tree);
// 后序遍历的非递归算法, 基于堆栈
void _lastTravel(Node* tree);
// 释放资源
void releaseTravel(Node* tree);
// 层次的非递归算法, 基于队列
void levelTravel(Node* tree);
// 统计二叉树中叶子结点的个数
int countLeaf(Node* tree);
// 	统计二叉树中结点的总数
int countNode(Node* tree);
// 求二叉树的深度(后序遍历)
int treeDepth(Node* tree);
// 求二叉树的宽度（具有结点数最多的层上的结点数）
unsigned int treeWidth(Node* tree);
// 已知二叉树中序遍历和后序遍历序列，求二叉树的二叉链表结构
Node* midLastToTree(const string& midIn, const string& lastIn);
// 已知二叉树中序遍历和先序遍历序列，求二叉树的二叉链表结构
Node* firstMidToTree(const string& midIn, const string firstIn);

void main()
{
	cout<<"输入先序扩展序列\n";
	string inData;
	getline(cin, inData);
	Node* tree = createTree(inData);

	cout<<"树的2叉表示:\n";
	displayTree(tree);

	cout<<"先序遍历:";
	firstTravel(tree);
	cout<<'\n';

	cout<<"中序遍历:";
	midTravel(tree);
	cout<<'\n';

	cout<<"后序遍历:";
	lastTravel(tree);
	cout<<'\n';

	cout<<"非递归先序遍历:";
	_firstTravel(tree);
	cout<<'\n';

	cout<<"非递归中序遍历:";
	_midTravel(tree);
	cout<<'\n';

	cout<<"非递归后序遍历:";
	_lastTravel(tree);
	cout<<'\n';

	cout<<"层次遍历:";
	levelTravel(tree);
	cout<<'\n';

	cout<<"叶子节点数目:"<<countLeaf(tree)<<'\n';

	cout<<"总节点数目:"<<countNode(tree)<<'\n';

	cout<<"树深度:"<<treeDepth(tree)<<'\n';

	cout<<"树宽度:"<<treeWidth(tree)<<'\n';

	// 中序遍历和后序遍历序列求二叉树
	{
	releaseTravel(tree);
	cout<<"输入中序和后序遍历序列\n";
	string midIn, lastIn;
	getline(cin, midIn);
	getline(cin, lastIn);
	tree = midLastToTree(midIn, lastIn);
	displayTree(tree);
	}

	// 中序遍历和先序遍历序列求二叉树
	{
	releaseTravel(tree);
	cout<<"输入先序遍历和中序遍历序列\n";
	string midIn, firstIn;
	getline(cin, firstIn);
	getline(cin, midIn);
	tree = firstMidToTree(midIn, firstIn);
	displayTree(tree);
	}

	cout<<"press any key to continue\n";
	cin>>inData;
	releaseTravel(tree);
} 

void createChild(Node* &node, string::const_iterator& iter, string::const_iterator& endIter)
{
	if (iter != endIter)
	{
		char c = *iter++;//建立字符串
		if (' ' == c)
		{
			node = 0;
		} else
		{
			node = new Node;
			node->c = c;//构造根结点
			createChild(node->left, iter, endIter);//构造左子树
			createChild(node->right, iter, endIter);//构造右子树
		}
	} else
	{
		node = 0;
	}
}
Node* createTree(const string& allNodes)// 按先序扩展序列建立二叉树
{
	string::const_iterator curIter = allNodes.begin();
	string::const_iterator endIter = allNodes.end();
	Node* tree = 0;
	createChild(tree, curIter, endIter);
	return tree;
}
void firstTravel(Node* tree)//先序遍历的递归算法
{
	if (tree)
	{
		cout<<tree->c;//根
		firstTravel(tree->left);//左
		firstTravel(tree->right);//右
	}
}
void releaseTravel(Node* tree)// 释放资源
{
	if (tree)
	{
		releaseTravel(tree->left);
		releaseTravel(tree->right);
		delete tree;
		tree  = 0;
	}
}
void midTravel(Node* tree)//中序遍历的递归算法
{
	if (tree)
	{
		midTravel(tree->left);
		cout<<tree->c;
		midTravel(tree->right);
	}
}
void lastTravel(Node* tree)//后序遍历的递归算法
{
	if (tree)
	{
		lastTravel(tree->left);
		lastTravel(tree->right);
		cout<<tree->c;
	}
}
void resetTree(Node* tree)//重置二叉树
{
	if (tree)
	{
		tree->leftVisite = false;
		tree->rightVisite = false;
		resetTree(tree->left);
		resetTree(tree->right);
	}
}
void _firstTravel(Node* tree)//先序遍历非递归算法
{
	//assert(tree);
	resetTree(tree);

	typedef vector<Node*> NodeStack;
	NodeStack stack;
	stack.push_back(tree); // 初始化栈

	while (stack.size())
	{
		Node* topNode = stack.back();
		if (!topNode->leftVisite && !topNode->rightVisite)
		{
			cout<<topNode->c;
		}
		if (topNode->left && !topNode->leftVisite)
		{
			stack.push_back(topNode->left);
			topNode->leftVisite = true;
		}else if (topNode->right && !topNode->rightVisite)
		{
			stack.push_back(topNode->right);
			topNode->rightVisite = true;
		} else
		{
			stack.pop_back();
		}
	}
}
void _midTravel(Node* tree)//中序遍历的非递归算法
{
	//assert(tree);
	resetTree(tree);

	typedef vector<Node*> NodeStack;
	NodeStack stack;
	stack.push_back(tree); //  初始化

	while (stack.size())
	{
		Node* topNode = stack.back();
		if (topNode->leftVisite && !topNode->rightVisite)
		{
			cout<<topNode->c;
		}
		   if (topNode->left && !topNode->leftVisite)
		   {
			  stack.push_back(topNode->left);
			  topNode->leftVisite = true;
		   }else 
			   if (topNode->right && !topNode->rightVisite)
		{
			if (!topNode->left && topNode->right)
			{cout<<topNode->c; }// 单边只有右子节点
			stack.push_back(topNode->right);
			topNode->rightVisite = true;
		} else
		{
			if (!topNode->left && !topNode->right)
			{
				cout<<topNode->c;
			}
			stack.pop_back();
		}
	}
}
void _lastTravel(Node* tree)//后序遍历的非递归算法
{
	//assert(tree);
	resetTree(tree);

	typedef vector<Node*> NodeStack;
	NodeStack stack;
	stack.push_back(tree); // 初始化

	while (stack.size())
	{
		Node* topNode = stack.back();
		if (topNode->leftVisite && topNode->rightVisite)
		{
			cout<<topNode->c;
		}
		if (topNode->left && !topNode->leftVisite)
		{
			stack.push_back(topNode->left);
			topNode->leftVisite = true;
		}else if (topNode->right && !topNode->rightVisite)
		{
			stack.push_back(topNode->right);
			topNode->rightVisite = true;
		} else
		{
			// 针对叶子节点或者单边子节点的情况
			if (!topNode->left || !topNode->right)
			{
				cout<<topNode->c;
			}
			stack.pop_back();
		}
	}
}
void levelTravel(Node* tree)// 层次的非递归算法, 基于队列
{
	//assert(tree);
	typedef list<Node*> Queue;
	Queue nodeQueue;
	nodeQueue.push_back(tree);

	while (nodeQueue.size())//由上至下，由左至右
	{
		Node* node = nodeQueue.front();
		cout<<node->c;
		if (node->left)
		{
			nodeQueue.push_back(node->left);
		}
		if (node->right)
		{
			nodeQueue.push_back(node->right);
		}
		nodeQueue.pop_front();
	}
}
int countLeaf(Node* tree)// 统计二叉树中叶子结点的个数
{
	if (!tree)
	{
		return 0;
	}

	if (!tree->left && !tree->right)//孤立点
	{
		return 1;
	}
    //递归计算
	int sum = 0;
	sum += countLeaf(tree->left);
	sum += countLeaf(tree->right);
	return sum;
}
int countNode(Node* tree)// 统计二叉树中结点的总数
{
	int sum = 0;
	if (tree)
	{
		sum = 1;
		sum += countNode(tree->left);
		sum += countNode(tree->right);
	}

	return sum;
}
int treeDepth(Node* tree)// 求二叉树的深度(后序遍历)
{
	int leftDepth = 0;
	int rightDepth = 0;
	if (tree)
	{
		leftDepth = 1;
		leftDepth += treeDepth(tree->left);
		rightDepth = 1;
		rightDepth += treeDepth(tree->right);
	}

	return max(leftDepth, rightDepth);
}
unsigned int treeWidth(Node* tree)// 求二叉树的宽度（具有结点数最多的层上的结点数）
{
	if (!tree)
	{
		return 0;
	}
	typedef list<Node*> Queue;
	Queue nodeQueue;
	unsigned int width = 0;
	nodeQueue.push_back(tree);

	while (nodeQueue.size())
	{
		unsigned int size = nodeQueue.size();
		// 上一层的节点全部出列,并压入下一层节点
		for (unsigned int i=0; i<size; ++i)
		{
			Node* node = nodeQueue.front();
			if (node->left)
			{
				nodeQueue.push_back(node->left);
			}
			if (node->right)
			{
				nodeQueue.push_back(node->right);
			}
			nodeQueue.pop_front();		
		}
		width = max(width, size);//与每一个size比较，取最大者
	}

	return width;
}
void displayTree(Node* tree)//显示二叉树
{
	if (tree)
	{
		cout<<"[Node:"<<tree->c<<']';
		if (tree->left)
		{
			cout<<"[left child:"<<tree->left->c<<']';
		}
		if (tree->right)
		{
			cout<<"[right child:"<<tree->right->c<<']';
		}
		cout<<'\n';

		displayTree(tree->left);
		displayTree(tree->right);
	}
}
Node* midLastToTree(const string& midIn, const string& lastIn)// 已知二叉树中序遍历和 
{                                             //后序遍历序列，求二叉树的二叉链表结构
	if (midIn.empty() || lastIn.empty())
	{
		return 0;
	}

	char rootC = *(lastIn.end() - 1); // 找出根结点
	// 把字符串midIn分成两部分 
	string::size_type rootIndex = midIn.find_first_of(rootC);
	string leftMidIn = midIn.substr(0, rootIndex);
	string rightMidIn = midIn.substr(rootIndex+1);
	// 把字符串lastIn也分成两部分 
	string leftLastIn;
	string rightLastIn;
	string::const_iterator curIter = lastIn.begin();
	string::const_iterator endIter = lastIn.end();
	for (; curIter!=endIter; ++curIter)
	{
		char c = *curIter;
		if (leftMidIn.find_first_of(c)!=string::npos)
		{
			leftLastIn.push_back(c);
		} else if (rightMidIn.find_first_of(c)!=string::npos)
		{
			rightLastIn.push_back(c);
		}
	}

	Node* tree = new Node;
	tree->c = rootC;
	// 递归
	tree->left = midLastToTree(leftMidIn, leftLastIn);
	tree->right = midLastToTree(rightMidIn, rightLastIn);
	return tree;
}
Node* firstMidToTree(const string& midIn, const string firstIn)// 已知二叉树中序遍历和
{                                               //先序遍历序列，求二叉树的二叉链表结构
	if (midIn.empty() || firstIn.empty())
	{
		return 0;
	}

	char rootC = *firstIn.begin();
	// 把字符串midIn分成两部分
	string::size_type rootIndex = midIn.find_first_of(rootC);
	string leftMidIn = midIn.substr(0, rootIndex);
	string rightMidIn = midIn.substr(rootIndex+1);
	// 把字符串firstIn分成两部分
	string leftFirstIn, rightFirstIn;
	string::const_iterator curIter = firstIn.begin();
	string::const_iterator endIter = firstIn.end();
	while (curIter != endIter)
	{
		char c = *curIter++;
		if (leftMidIn.find_first_of(c)!=string::npos)
		{
			leftFirstIn.push_back(c);
		} else if (rightMidIn.find_first_of(c)!=string::npos)
		{
			rightFirstIn.push_back(c);
		}
	}

	Node* tree = new Node;
	tree->c = rootC;
	// 递归
	tree->left = firstMidToTree(leftMidIn, leftFirstIn);
	tree->right = firstMidToTree(rightMidIn, rightFirstIn);
	return tree;
}