山东大学软件学院数据结构实验五二叉树操作

1、 输入一个完全二叉树的层次遍历字符串，创建这个二叉树，输出这个二叉树的前序遍历字符串、中序遍历字符串、后序遍历字符串、结点数目、二叉树高度(上述每一个结果独立一行显示)。 2、 输入二叉树前序序列和中序序列(各元素各不相同)，创建这个二叉树，输出该二叉树的后序序列、层次遍历。

#include 
#include 
#include 
#include “binaryTree.h“
using namespace std;
constexpr auto MAX = 100;//前中序输入的最大数目本来是#define MAX定义一个宏，后来VS提示改成这个就这样了

int* binaryTree::rootElement（） const
{
	//返回NULL，如果是空树。否则，返回根节点的element域
	if （treeSize == 0）
		return NULL;  // no root
	else
		return &root->element;
}

//将leftChild，rightChild，element合并成一颗新树
void binaryTree::makeTree（const int &element binaryTree &leftChild binaryTree &rightChild）
{
	root = new binaryTreeNode（element leftChild.root rightChild.root）;
	leftChild.root = rightChild.root = 0;	//禁止通过其他途径访问leftChild和rightChild
}

void binaryTree::makeTreeBylevelOrder（const char* levelOrder const int length）
{
	queue queue;         //运用队列处理左右节点

	for （int i = 0; i < length; i++）
	{
		if （i == 0）     //根的处理，树根的初始化
		{
			switch （length）
			{
			case 1:
				root = new binaryTreeNode（levelOrder[0]）;
				break;
			case 2:
				root = new binaryTreeNode（levelOrder[0] new binaryTreeNode（levelOrder[1]） NULL）;
				break;
			case 3:
				root = new binaryTreeNode（levelOrder[0] new binaryTreeNode（levelOrder[1]） new binaryTreeNode（levelOrder[2]））;
				break;
			default:
				root = new binaryTreeNode（levelOrder[0] new binaryTreeNode（levelOrder[1]） new binaryTreeNode（levelOrder[2]））;
				queue.push（root->leftChild）;
				queue.push（root->rightChild）;
				break;
			}
		}
		else         //不为根节点时
		{
			if （2 * i + 2 <= length - 1） //如果当前节点有右孩子
			{
				queue.front（）->leftChild = new binaryTreeNode（levelOrder[2 * i + 1]）;
				queue.front（）->rightChild = new binaryTreeNode（levelOrder[2 * i + 2]）;
				queue.push（queue.front（）->leftChild）;
				queue.push（queue.front（）->rightChild）;
				queue.pop（）;
			}
			if （2 * i + 2 > length - 1 && 2 * i + 1 <= length - 1） //如果当前节点没有右孩子且有左孩子
			{
				queue.front（）->leftChild = new binaryTreeNode（levelOrder[2 * i + 1]）;
				queue.pop（）;
			}
		}
	}
}

void binaryTree::preOrder（void（*visit）（binaryTreeNode *p） binaryTreeNode *t）
{
	if （t）
	{
		visit（t）;
		preOrder（visit t->leftChild）;
		preOrder（visit t->rightChild）;
	}
}

void binaryTree::inOrder（void（*visit）（binaryTreeNode *p） binaryTreeNode *t）
{
	if （t）
	{
		inOrder（visit t->leftChild）;
		visit（t）;
		inOrder（visit t->rightChild）;
	}

}

void binaryTree::postOrder（void（*visit）（binaryTreeNode *p） binaryTreeNode *t）
{
	if （t）
	{
		postOrder（visit t->leftChild）;
		postOrder（visit t->rightChild）;
		visit（t）;
	}
}

void binaryTree::levelOrder（void（*visit）（binaryTreeNode *p） binaryTreeNode *t）
{
	//层次遍历二叉树
	queue q;

	while （t != NULL）
	{
		visit（t）; //访问根

		if （t->leftChild != NULL）	
			q.push（t->leftChild）;
		if （t->rightChild != NULL）
			q.push（t->rightChild）;
		if （!q.empty（））
		{
			t = q.front（）;
			q.pop（）;
		}
		else
		{
			break;
		}
	}
}

int binaryTree::height（）
{
	return treeHeight（root）;
}

int binaryTree::treeHeight（binaryTree

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

    ..A..H.     48640  2018-11-27 16:39  二叉树（终极版）\.vs\二叉树（终极版）\v15\.suo

     文件   12431360  2018-11-27 16:39  二叉树（终极版）\.vs\二叉树（终极版）\v15\Browse.VC.db

     文件   30539776  2018-11-13 18:00  二叉树（终极版）\.vs\二叉树（终极版）\v15\ipch\AutoPCH\2394592c86553f9c\BINARYTREENODE.ipch

     文件   38993920  2018-11-26 10:21  二叉树（终极版）\.vs\二叉树（终极版）\v15\ipch\AutoPCH\2fba762e62fd9078\TEST05_201702302055.ipch

     文件   39649280  2018-11-27 16:38  二叉树（终极版）\.vs\二叉树（终极版）\v15\ipch\AutoPCH\3b3b8f0e6b380270\源.ipch

     文件   35848192  2018-11-26 08:50  二叉树（终极版）\.vs\二叉树（终极版）\v15\ipch\AutoPCH\76f7b42f7389c2a7\linkEDBINARYTREE.ipch

     文件   38993920  2018-11-26 09:19  二叉树（终极版）\.vs\二叉树（终极版）\v15\ipch\AutoPCH\e5b55b18c077e97d\ASHDH.ipch

     文件   30539776  2018-11-13 18:04  二叉树（终极版）\.vs\二叉树（终极版）\v15\ipch\AutoPCH\f09c574e615c4b9c\BINARYTREE.ipch

     文件   39649280  2018-11-27 16:38  二叉树（终极版）\.vs\二叉树（终极版）\v15\ipch\AutoPCH\f9a142b82b662c3f\BINARYTREE.ipch

     文件     143360  2018-11-26 10:46  二叉树（终极版）\Debug\二叉树（终极版）.exe

     文件     879268  2018-11-26 10:46  二叉树（终极版）\Debug\二叉树（终极版）.ilk

     文件    1019904  2018-11-26 10:46  二叉树（终极版）\Debug\二叉树（终极版）.pdb

     文件       3477  2018-11-26 10:34  二叉树（终极版）\二叉树（终极版）\binaryTree.cpp

     文件       1978  2018-11-26 10:34  二叉树（终极版）\二叉树（终极版）\binaryTree.h

     文件        532  2018-11-26 09:32  二叉树（终极版）\二叉树（终极版）\binaryTreeNode.h

     文件     273612  2018-11-26 10:34  二叉树（终极版）\二叉树（终极版）\Debug\binaryTree.obj

     文件     368425  2018-11-26 10:03  二叉树（终极版）\二叉树（终极版）\Debug\test05_201702302055.obj

     文件     273408  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\vc141.idb

     文件     569344  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\vc141.pdb

     文件       1288  2018-11-19 16:04  二叉树（终极版）\二叉树（终极版）\Debug\二叉树（终极版）.Build.CppClean.log

     文件        129  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\二叉树（终极版）.log

     文件       1876  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\二叉树（终极版）.tlog\CL.command.1.tlog

     文件      48054  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\二叉树（终极版）.tlog\CL.read.1.tlog

     文件       2044  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\二叉树（终极版）.tlog\CL.write.1.tlog

     文件       1226  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\二叉树（终极版）.tlog\link.command.1.tlog

     文件       2756  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\二叉树（终极版）.tlog\link.read.1.tlog

     文件        478  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\二叉树（终极版）.tlog\link.write.1.tlog

     文件        216  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\二叉树（终极版）.tlog\二叉树（终极版）.lastbuildstate

     文件     305076  2018-11-26 10:46  二叉树（终极版）\二叉树（终极版）\Debug\源.obj

     文件       6173  2018-11-26 10:25  二叉树（终极版）\二叉树（终极版）\二叉树（终极版）.vcxproj

............此处省略24个文件信息