数据结构与算法3--树常见操作

 

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树。以下是笔者根据树的特性和平时使用情况完成的一些基本功能，后续将根据使用情况再增加相关功能。

 

1、功能

00-打印数组
01-新建树方法1
02-广度输出树
03-先序遍历树
04-中序遍历树
05-后续遍历树
06-树高度计算方法

 

2、代码

/*
该文件夹包含tree的增删查改，以及常见tree算法的实现
*/
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

/*	
example 1
     10
  6     14
4   8  12 16
pre = {10,6,4,8,14,12,16}
mid = {4,8,6,12,16,14,10}

example 2
	 1
  2     3
4      5   6 
 7        8
pre = {1,2,4,7,3,5,6,8}
mid = {4,7,2,1,5,3,8,6} 
*/

typedef struct Node
{
	int val;
	Node *left;
	Node *right;
}TreeNode;

/*Menu
00-打印数组
01-新建树方法1
02-广度输出树
03-先序遍历树
04-中序遍历树
05-后续遍历树
06-树高度计算方法
*/
void PrintArray(const vector<int> &arr);//00
TreeNode* CreateTree1(vector<int> pre, vector<int> mid);//01-1由前序遍历和中序遍历构建二叉树
void PrintTreeBFS(TreeNode *pRoot);//02
void PrintPreOrder(TreeNode *pRoot);//03
void PrintInOrder(TreeNode *pRoot);//04
void PrintLastOrder(TreeNode *pRoot);//05
int GetHight(TreeNode *pRoot);//06-树高度计算方法

//00-打印数组
void PrintArray(const vector<int> &arr)
{
	cout<<'[';
	for(int i=0;i<arr.size();i++)
		(i==(arr.size()-1))?(cout<<arr[i]<<']'<<endl):(cout<<arr[i]<<',');
}
//01-新建树方法1
TreeNode* CreateTree1(vector<int> pre, vector<int> mid)
{
	if(pre.size()==0 || mid.size()==0)
		return NULL;
	vector<int> lpre,lmid,rpre,rmid;//save leftsubtre pre、leftsubtree mid、rightsubstree pre、rightsubtree mid
	int i=0;
	for(i=0;i<mid.size();i++)
	{
		if(pre[0]!=mid[i])
		{
			lpre.push_back(pre[i+1]);
			lmid.push_back(mid[i]);
		}else
		{
			break;
		}
	}
	for(i=i+1;i<mid.size();i++)
	{
		rpre.push_back(pre[i]);
		rmid.push_back(mid[i]);
	}
	TreeNode *root = new TreeNode();
	root->val = pre[0];
	root->left = CreateTree1(lpre,lmid);
	root->right = CreateTree1(rpre,rmid);
	return root;
}
void TestCreateTree1()
{
	int pre[] = {1,2,4,7,3,5,6,8};
	int mid[] = {4,7,2,1,5,3,8,6};
	vector<int> vpre(pre,pre+sizeof(pre)/sizeof(int));
	vector<int> vmid(mid,mid+sizeof(mid)/sizeof(int));
	cout<<"pre:";
	PrintArray(vpre);
	cout<<"mid:";
	PrintArray(vmid);
	TreeNode *root = CreateTree1(vpre,vmid);
	PrintTreeBFS(root);
}
//02-广度输出树
void PrintTreeBFS(TreeNode *pRoot)
{
	if(pRoot==NULL)
	{
		cout<<"NULL"<<endl;
		return ;
	}
	queue<TreeNode *> que;
	que.push(pRoot);
	while(que.size()!=0)
	{
		int len = que.size();
		for(int i=0;i<len;i++)
		{
			TreeNode *p = que.front();
			cout<<p->val<<'\t';
			if(p->left!=NULL)
				que.push(p->left);
			if(p->right!=NULL)
				que.push(p->right);
			que.pop();
		}
		cout<<endl;
	}
}
void TestPrintTreeBFS()
{
	int pre[] = {1,2,4,7,3,5,6,8};
	int mid[] = {4,7,2,1,5,3,8,6};
	vector<int> vpre(pre,pre+sizeof(pre)/sizeof(int));
	vector<int> vmid(mid,mid+sizeof(mid)/sizeof(int));
	TreeNode *root = CreateTree1(vpre,vmid);
	PrintTreeBFS(root);
}
//03-先序遍历树
void PrintPreOrder(TreeNode *pRoot)
{
	if(pRoot==NULL)
		return ;
	cout<<pRoot->val<<'\t';
	PrintPreOrder(pRoot->left);
	PrintPreOrder(pRoot->right);
}
void TestPrintPreOrder()
{
	int pre[] = {1,2,4,7,3,5,6,8};
	int mid[] = {4,7,2,1,5,3,8,6};
	vector<int> vpre(pre,pre+sizeof(pre)/sizeof(int));
	vector<int> vmid(mid,mid+sizeof(mid)/sizeof(int));
	PrintArray(vpre);
	PrintArray(vmid);
	TreeNode *root = CreateTree1(vpre,vmid);
	PrintPreOrder(root);
	cout<<endl;
}
//04-中序遍历
void PrintInOrder(TreeNode *pRoot)
{
	if(pRoot==NULL)
		return ;
	PrintInOrder(pRoot->left);
	cout<<pRoot->val<<'\t';
	PrintInOrder(pRoot->right);	
}
void TestPrintInOrder()
{
	int pre[] = {1,2,4,7,3,5,6,8};
	int mid[] = {4,7,2,1,5,3,8,6};
	vector<int> vpre(pre,pre+sizeof(pre)/sizeof(int));
	vector<int> vmid(mid,mid+sizeof(mid)/sizeof(int));
	PrintArray(vpre);
	PrintArray(vmid);
	TreeNode *root = CreateTree1(vpre,vmid);
	PrintInOrder(root);
	cout<<endl;
}
//05-后续遍历
void PrintLastOrder(TreeNode *pRoot)
{
	if(pRoot==NULL)
		return ;
	PrintLastOrder(pRoot->left);
	PrintLastOrder(pRoot->right);	
	cout<<pRoot->val<<'\t';
}
void TestPrintLastOrder()
{
	int pre[] = {1,2,4,7,3,5,6,8};
	int mid[] = {4,7,2,1,5,3,8,6};
	vector<int> vpre(pre,pre+sizeof(pre)/sizeof(int));
	vector<int> vmid(mid,mid+sizeof(mid)/sizeof(int));
	PrintArray(vpre);
	PrintArray(vmid);
	TreeNode *root = CreateTree1(vpre,vmid);
	PrintLastOrder(root);
	cout<<endl;
}
//06-树高度计算方法
int GetHight(TreeNode *pRoot)
{
	if(pRoot == NULL)
		return 0;
	return GetHight(pRoot->left)>GetHight(pRoot->right)?(1+GetHight(pRoot->left)):(1+GetHight(pRoot->right));
}
void TestGetHight()
{
	int pre[] = {1,2,4,7,3,5,6,8};
	int mid[] = {4,7,2,1,5,3,8,6};
	vector<int> vpre(pre,pre+sizeof(pre)/sizeof(int));
	vector<int> vmid(mid,mid+sizeof(mid)/sizeof(int));
	TreeNode *root = CreateTree1(vpre,vmid);
	cout<<GetHight(root)<<endl;
}

int main(int argc, char const *argv[])
{
	/* code */
//01-新建树方法1
	//TestCreateTree1();
//02-广度输出树
	//TestPrintTreeBFS();
//03-先序遍历树
	//TestPrintPreOrder();
//04-中序遍历树
	//TestPrintInOrder();
//05-后续遍历树
	//TestPrintLastOrder();
//06-树高度计算方法
	TestGetHight();
	return 0;
}

 

3、说明

当前已在mingw32(gcc 4.9.2)上测试通过。