【数据结构实验】简单打印二叉树超详细讲解（含二叉树每一个元素所在层数的算法和求二叉树深度的代码）

问题描述 打印二叉树结构（设计性实验） 问题描述 按凹入表形式横向打印二叉树结构，即二叉树的根在屏幕的最左边，二叉树的左子树在屏幕的下 边，二叉树的右子树在屏幕的上边。例如：   测试数据 由读者依据软件工程的测试技术自己确定。注意测试边界数据，如空二叉树。 实验分析

首先观察例子中打印的二叉树的排版格式，如果把图片顺时针旋转90度，就能看到非常直观的二叉树的排版，现在需要从中找到规律，从而用代码将其实现。

经过观察发现：
打印出的二叉树中，每一行可以看成只有一个元素，最重要的发现是从下往上的元素的顺序恰好就是二叉树中序遍历的序列，这是行的规律。

列的规律实际上更加直观，因为元素位于第几列，就是对应于二叉树的第几层！

所以现在想要去构造这么一个二维矩阵，需要知道1.中序遍历序列2.每一个元素对应的层数

先来看中序遍历序列怎么找，实际上只需要对中序遍历的函数InOrderTraverse(BiTreePtr T)做一下小小的改变，原来是直接在屏幕上打印相关的数据，现在可以设置一个全局变量的一维数组，把打印的 *** 作换成加入数组的 *** 作，把这个序列保存起来即可。

元素在第j列，就对应着在原来的二叉树的第j层，也就意味着在矩阵中，前面有j-1个空格！

最后一个关键的问题是，如何知道每一个元素所在的层数，我是在原来的结构中添加了一个成员layer，然后受到“求二叉树深度”的算法的启发，同样利用递归写出了这个过程。下面先放一下求二叉树深度的伪代码吧:

int Depth(BiTree T)
{
if(T=NULL) return 0;
else{
m=Depth(T->lChild);
n=Depth(T->rChild);
if(m>n) return (m+1);
else return (n+1);
}

所有工作做完之后只需两个for循环，在主函数里面就可以得到我们想要的啦

完整代码实现：

#include
#include
#include
int cnt=0;
typedef struct BiTree
{
	char data;
	int layer;
	struct BiTree *lchild;
	struct BiTree *rchild;
}BiTree,*BiTreePtr;
BiTree InOrder[50];
bool CreatBiTree(BiTreePtr *T,int t)
{
	char ch;
	scanf("%c",&ch);
	if(ch==' ') (*T)=NULL;
	else
	{
		if(!((*T)=(BiTreePtr)malloc(sizeof(BiTree)))) exit(1);
		(*T)->data=ch;
		(*T)->layer=t;
		int sub=t;
		CreatBiTree(&((*T)->lchild),++t);
		CreatBiTree(&((*T)->rchild),++sub);
	}
	return true;
}
bool InOrderTraverse(BiTreePtr T)
{
	if(T)
	{
		InOrderTraverse(T->lchild);
		InOrder[cnt++]=*T;
     	InOrderTraverse(T->rchild);
	}
	else
	return true;
	return true;
}
int main()
{
	BiTreePtr T;
	CreatBiTree(&T,1);
	InOrderTraverse(T);
	int i,j;
	for(i=cnt-1;i>=0;i--)
	{
		for(j=1;j

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/1294669.html