二叉树的图形直观显示的初步实现

学习到了二叉树，认识到二叉树太有作用了。但每一次创建了二叉树，总想直观看一下二叉树的结序，以方便程序的调试。但二叉树的结构怎样才能直观显示出来呢？看了网上的一些资料和做法，要么看不懂，要么不满意。于是试着自己写代码，看能否达到目的。功夫不负有心人，经过不懈努力，终于弄出一个初步的结果。兴奋！！！本想进一步完善，添上一些符号把节点连起来再发出来，实在高兴忍不住了……哈哈！！！先上结果的图片：

下面简单说一下思路，欢迎大家指正并提出更好的办法。

基本思路：二叉树两条分支，从形状上来讲，左右是对称的。虽然不一定每个节点都有左右两个子节点，但是要直观显示时，位置分布上也要把空节点留出相应的空间来。这样，它始终是对称的。因此：我的方法就是“对称输出”，每个节点，包括空的节点，留出相应位置空间。

基本方法：思路虽然有了，但实现起来很困难。首先每个节点的信息有限，如果只有data,LChild,RChild等信息，就无法了解节点与其它同层节点以及父节点之间的信息与关系，输出时就无法控制了。

所以我的第一步：重新定义一个“节点”的结构，使它包括：父节点指针、深度（层次）、位置序号等成员数据，以上所说的难点就从定义上解决了。下面是节点的结构定义：

template<typename T>
struct BiTNode {
	BiTNode<T> *Lchild = NULL, *Rchild = NULL, *parent = NULL;
	T data;
	int depth = 0;
	int order = 0;
};

节点定义了，怎么在程序中实际生成这些数据呢？因为二叉树要直观图形输出，必须要按层的顺序了解足够的信息。所以首先要能够按层遍历二叉树的方法。这个不难，我还是用利用队列（Queue)的办法解决它。下面是我根据已存在的二叉树，按照自己定义的节点结构重新创建（即复制二叉树）的二叉树的方法代码：

//复制二叉树，按BiTNode结构类，添加深度、序号以及父节点等信息
template<typename T>
BiTNode<T> *CreateBiTTreeFrom(BiTNode<T> *p) {
	//复制p为根结点的树，并添加BiTNode相关变量信息。
	Queue<BiTNode<T> *> qbit;
	BiTNode<T> *root=NULL,*bitNode, *childNode;
	if (p) {
		//根结点复制
		root = new BiTNode<T>;
		root->data = p->data;
		root->depth = 1;
		//ordero为节点序号。节点序号编排原则：从0开始；空节点也要占据相应位置。非实际节点序号。
		root->order = 0;
		root->Lchild = p->Lchild;
		root->Rchild = p->Rchild;

		qbit.QInsert(root);
		//其它节点的复制循环，利用队列先进先出特点，按层序复制所有节点。
		while (!qbit.QEmpty()) {
			bitNode = qbit.QDelete();
			//根据父结点，创建左子节点并添加相关信息。
			if (bitNode->Lchild) {
				childNode = new BiTNode<T>;
				childNode->data = bitNode->Lchild->data;
				childNode->depth = bitNode->depth + 1;
				childNode->parent = bitNode;
				//根据父节点的序号确定上一层元素的个数，从而可以确定当前节点在当前层的序号。
				//序号计算要包括父结点中不存在的左或右子节点的数量。序号不是指实际存在的同层节点的序号。
				childNode->order = childNode->parent->order * 2;
				childNode->Lchild = bitNode->Lchild->Lchild;

				childNode->Rchild = bitNode->Lchild->Rchild;

				bitNode->Lchild = childNode;
				qbit.QInsert(bitNode->Lchild);
			}
			//根据父结点，创建右子节点并添加相关信息。
			if (bitNode->Rchild) {

				childNode = new BiTNode<T>;
				childNode->data = bitNode->Rchild->data;
				childNode->depth = bitNode->depth + 1;
				childNode->parent = bitNode;
				childNode->order = childNode->parent->order * 2 + 1;

				childNode->Lchild = bitNode->Rchild->Lchild;

				childNode->Rchild = bitNode->Rchild->Rchild;

				bitNode->Rchild = childNode;
				qbit.QInsert(bitNode->Rchild);
			}

		}

	}
	return root;
}

第二步：根据新的二叉树，直观输出二叉树。这个非常麻烦，但经过几番探索，终于找到一点二叉树节点空间分布的规律了。下面以图为例说明：

解释一下我的想法：1，二叉树的输出如果是对称输出的话，其宽度是由最深一层（最大一层）的节点数量决定的。最深一层可能存在的节点数量很容易由公式计算出来：2^(depth-1),其中depth代表层次的变量。如果最深一层的输出，节点之间（节点值输出本身有一定宽度）不留空白的话，那二叉树输出最大宽度就确定了：maxwidth=deltawidth*最深一层节点数。这里，节点数包括不存在的空节点。deltawidth是每个节点自身输出的宽度，如上图中每个矩形的宽度。有了这个衡量的标准，其它各层的输出也总是对称输出的，就有办法解决了。

2，怎么控制节点输出时的缩进以及节点之间的间隔呢？虽然最深一层节点之间间隔宽度为0，但同层节点之间的间隔在其它层里面，是存在的，也必须存在，不然无法对称，也无法显示出父节点与子节点之间的错落关系。最终我发现：节点以指定宽度输出并保持对称的话，节点之间的空白宽度是有规律的，可以计算出来：

distance=(2^(treedepth-depth)-1)/2*deltawidth。

其中，distance代表二叉树同一层的任意相连的两个节点（空节点就当它存在）之间的“单位”间隔。所谓“单位”间隔，是指两个节点之间的间隔距离是distance的2倍。1个distance又是指什么呢？它刚好是每层第一个节点的缩进宽度。而这个宽度的2倍，又刚好是后面任意两个相连节点之间的间隔。treedepth是整个二叉树的深度（最大层数），depth代表某一层的层数。deltawidth是节点值输出的指定宽度，比如：deltawidth=4。代表4个字符的宽度。从公式来看，节点之间的间隔与层数有关，不同层元素之间的间隔不一样（这很容易理解：层越接近根结点层，节点越少，间隔自然更多）。虽然不同层的间隔不一样，但可以根据层数计算出来，而且：这个间隔在每一层刚好都是distance的两倍。如上图所示。根结点只有一个元素，所以其左右空白在maxwidth内，刚好各是2个distance。找到这个规律，节点之间的间隔就能控制了。

3，怎么控制实际存在的节点之间间隔呢？因为同层中的节点，并不是完全存在的，也不可能有规律哪些节点存在，哪些不存在。这就用到了节点定义中的order成员数据了。order表示同一层中所有可能存在的节点（节点总数根据层数可以计算出来）的顺序号，第一个序号为0，最右边的节点为：节点总数-1。如二叉树第4层，它最多有8个节点，order就是0-7。根据这个节点顺序值，可以计算同层节点输出宽度了：

totalwidth += (order - _preOrder)*(deltawidth + 2 * distance) - 2 * distance;

其中，order,_preorder代表输出时前后两个节点的序号。totalwidth代表输出某个节点时，实际输出的宽度值。

怎样理解这个公式呢？想象一下：节点之间的距离为2*distance,节点本身的输出宽度为deltawidth（根据节点值的字符长短，自己定义的宽度）。所以：任意一个节点输出的宽度加上间隔的话，就是：deltawidth + 2 * distance。但是，很可能存在一些特殊情况：

（1）上一节点是上一层的最后一个实际存在的节点，下一节点不是本层第一个节点（同层第一个节点或连续几个节点不存在）。如果只输出以上宽度的话，对称无法实现的，需要把不存在的节点的宽度和它后面的空白间隔考虑进去。而间隔与节点在同层节点中的序号相关。多一个序号差，就多一个deltawidth + 2 * distance的间隔。前一节点的序号由于是上一层的，不能使用，算作0的话，计算出的结果又是错误的，实践证明：把上一节点的序号改为-1就行了。但如果是同层的，序号就不变。

//存在每层第一个存在的元素的序号不是为0的情况，统一把它第一个元素的序号设置成-1，
					//方便计算元素之间的间距（不一定是序号相连的两个元素）
				if (pre->depth != depth) {
					_preOrder = -1;
				}
				else {
					//不是第一个的元素的序号仍然为原序号。
					_preOrder = pre->order;
				}

（2） 还有一个情况：上述这样计算之后，每个节点后面，输出时都加上了间隔宽度。输出时，一般都是右对齐的，多了些宽度，输出位置就发生错位了。所以要减少这个间隔，即：-2*distance。

如此，输出宽度就解决了。二叉树直观图形式的显示就基本实现了。当然，父结点与子结点之间还没有加上连结的字符，还不是完全的图形输出。基本思考了一下，应该可以实现的，下一步就去做这个事，完成之后就发上来大家指正。

下面是我的完全代码，包括两个模板类：BitTNoe 和 Queue。其中，创建二叉树时，用的是一个递归，根据一个数组的值创建的。其中，根结点的左子节点只有一个（没有办法，为了避免手工创建二叉树的麻烦只能这样了）。

#include<iostream>
#include<iomanip>

using namespace std;

//************************************struct BiTNode****************************************************
template<typename T>
struct BiTNode {
	BiTNode<T> *Lchild = NULL, *Rchild = NULL, *parent = NULL;
	T data;
	int depth = 0;
	int order = 0;
};
//*****************************************************************************************


//************************************class Queue*****************************************************
//队列内元素最大个数：
static const int MAXSIZE=100;

/*模板队列类
*/

template<typename T>
class Queue {
private:
	//队首，指向最先出队列的元素位置。
	int front;
	//队尾，指向下一次插入的新元素位置。
	int rear;
	//已经插入队列的元素个数。
	int count;
	//队列内保存元素的数组。
	T qList[MAXSIZE];
public:
	//构造函数
	Queue();
	//插入元素的函数
	bool QInsert(T& item);
	//弹出元素的函数
	T QDelete(void);
	//清空队列
	void QClear(void);
	//返回正在排队的元素个数。
	int QGetCount(void);
	//队列状态函数：是否为空。
	bool QEmpty();
	//队列状态函数：是否已满。
	bool QFull();
	//析构函数
	~Queue();
};

template<typename T>
Queue<T>::Queue() :front(0),rear(0),count(0){
}

template<typename T>
bool Queue<T>::QInsert(T& item){
	if (QFull()) {
		cout << "队列已满！插入失败！" << endl;
		return false;
	}
	else {
		count++;
		qList[rear] = item;
		rear = (rear + 1) % MAXSIZE;
		return true;
	}
}



template<typename T>
T Queue<T>::QDelete(void){
	
	if (QEmpty()) {
		cout << "队列是空的！非正常退出！" << endl;
		exit(1);
	}
	else {
		T temp = qList[front];
		count--;
		front = (front + 1) % MAXSIZE;
		
		return temp;
	}

}
template<typename T>
void Queue<T>::QClear(void){
	front = rear =count= 0;
}


template<typename T>
int Queue<T>::QGetCount(void) {
	return count;
}


template<typename T>
bool Queue<T>::QEmpty(){
	return count == 0;
}
template<typename T>
bool Queue<T>::QFull(){
	return count == MAXSIZE;
}

template<typename T>
Queue<T>::~Queue() {

}
//*****************************************************************************************

template<typename T>
BiTNode<T> *CreateBiTTreeFrom(BiTNode<T> *p);

template<typename T>
void DisplayBiTTree(BiTNode<T> *root);

template<typename T>
int GetDepth(BiTNode<T> *root);

template<typename T>
int CountDepth(BiTNode<T> *root);

template<typename T>
void CreateTree(T *arr, int left, int right, BiTNode<T> *p);

template<typename T>
void DeleteTree(BiTNode<T> *root);

int Main() {
	BiTNode<int> *root;
	BiTNode<int> *p = new BiTNode<int>;
	const int size = 9;
	int a[size];
	for (int i = 0;i < size;i++)
		a[i] = i + 10;
	p->data = a[size - 1];

	CreateTree<int>(a, 0, size - 2, p);

	root = CreateBiTTreeFrom<int>(p);
	DisplayBiTTree<int>(root);




	DeleteTree<int>(p);
        DeleteTree<int>(root);
	return 0;
}

//复制二叉树，按BiTNode结构类，添加深度、序号以及父节点等信息
template<typename T>
BiTNode<T> *CreateBiTTreeFrom(BiTNode<T> *p) {
	//复制p为根结点的树，并添加BiTNode相关变量信息。
	Queue<BiTNode<T> *> qbit;
	BiTNode<T> *root=NULL,*bitNode, *childNode;
	if (p) {
		//根结点复制
		root = new BiTNode<T>;
		root->data = p->data;
		root->depth = 1;
		//ordero为节点序号。节点序号编排原则：从0开始；空节点也要占据相应位置。非实际节点序号。
		root->order = 0;
		root->Lchild = p->Lchild;
		root->Rchild = p->Rchild;

		qbit.QInsert(root);
		//其它节点的复制循环，利用队列先进先出特点，按层序复制所有节点。
		while (!qbit.QEmpty()) {
			bitNode = qbit.QDelete();
			//根据父结点，创建左子节点并添加相关信息。
			if (bitNode->Lchild) {
				childNode = new BiTNode<T>;
				childNode->data = bitNode->Lchild->data;
				childNode->depth = bitNode->depth + 1;
				childNode->parent = bitNode;
				//根据父节点的序号确定上一层元素的个数，从而可以确定当前节点在当前层的序号。
				//序号计算要包括父结点中不存在的左或右子节点的数量。序号不是指实际存在的同层节点的序号。
				childNode->order = childNode->parent->order * 2;
				childNode->Lchild = bitNode->Lchild->Lchild;

				childNode->Rchild = bitNode->Lchild->Rchild;

				bitNode->Lchild = childNode;
				qbit.QInsert(bitNode->Lchild);
			}
			//根据父结点，创建右子节点并添加相关信息。
			if (bitNode->Rchild) {

				childNode = new BiTNode<T>;
				childNode->data = bitNode->Rchild->data;
				childNode->depth = bitNode->depth + 1;
				childNode->parent = bitNode;
				childNode->order = childNode->parent->order * 2 + 1;

				childNode->Lchild = bitNode->Rchild->Lchild;

				childNode->Rchild = bitNode->Rchild->Rchild;

				bitNode->Rchild = childNode;
				qbit.QInsert(bitNode->Rchild);
			}

		}

	}
	return root;
}



//经过改造之后的二叉树的图形显示输出
template<typename T>
void DisplayBiTTree(BiTNode<T> *root) {

	//利用队列作为读取二叉树节点的工具
	Queue<BiTNode<T>*> qbit;
	//记录前后两个节点的指针
	BiTNode<T> *p, *pre;
	//需要显示的节点值的宽度。
	//偶数最佳，根据显示调节宽度。不宜太大。
	int deltawidth = 4;
	//整个二叉树的深度（最大层数）
	int treeDepth = GetDepth<T>(root);
	//根据二叉树最大一层可能存在的元素最多个数确定输出的最大宽度
	int maxwidth = deltawidth * pow(2, treeDepth - 1);
	//元素之间间距变量
	//二叉树每层元素以一定宽度输出后，在上述最大宽度输出范围内，剩余的元素之间的空白宽度
		//计算公式：（2^(最大层数-当前层数）-1）/2  ，其中层数从1开始。
	int distance;
	//二叉树深度（层数）
	int depth;
	//同层元素的序号：从0开始，每层元素为：2^(层数-1）个。每层最大序号为：2^(层数-1）-1 个。
	int order;
	//每层可能存在的元素的最大个数。
	int nodesNum;
	//二叉树每层最后一个元素输出后，接着输出换行符后的标志设置
	int flagEnter = 0;
	//上一个元素的序号
	int _preOrder;


	//上一个元素指针（初始为根结点）
	pre = root;
	/*以下利用队列先进先出的特点，循环读取二叉树节点，
	按层序由根结点到最大层从左到右依次读取元素，
	并根据获取的元素相关信息格式化输出二叉树每层元素。
	当遍历二叉树又不想用递归方法时，利用队列的先进先出的特点就能实现遍历了。
		*/
	if (root) {
		qbit.QInsert(root);
		while (!qbit.QEmpty()) {
			//每个节点输出时的输出宽度的变量（用于计算节点输出宽度的过程中的累计）
			int totalwidth = 0;
			p = qbit.QDelete();
			//当前节点的深度（层数）
			depth = p->depth;
			//当前节点的序号（即二叉树某层第几个节点）
			order = p->order;
			//每层元素总数（包括空节点）
			nodesNum = pow(2, depth - 1);
                        //如果上一个是上一行的最后一个节点，输出换行符
                        if (pre->depth != p->depth) {
				cout << endl;
				flagEnter = 1;
			}

			//单位间距变量（关键点！！！）
			//根据二叉树的层数（深度）和自定义设置的元素输出的单位宽度，
			//直接计算出元素之间的间距的单位量：元素之间的间距=2*distance.
			//每层的间距不一样，最大一层间距为0.即distance为0.
			distance = deltawidth * (pow(2, treeDepth - depth) - 1) / 2;
			//根结点所在层，即第一层单独设置输出宽度。
			//第一层：maxwidth=distance+节点(按一定单位的宽度输出)+distance.
			if (depth == 1) {
				cout.width(distance + deltawidth);
			}
			else {
				//以下为：非第一层节点输出的宽度的计算方法
					//如果上一节点是上一层最后一个元素输出并输出了换行符，
					//下一行开始（即当前节点）就要首先输出一个缩进宽度。即为distance的值。
				if (flagEnter == 1) {
					totalwidth += distance;
					flagEnter = 0;
				}

				//存在每层第一个存在的元素的序号不是为0的情况，统一把它第一个元素的序号设置成-1，
					//方便计算元素之间的间距（不一定是序号相连的两个元素）
				if (pre->depth != depth) {
					_preOrder = -1;
				}
				else {
					//不是第一个的元素的序号仍然为原序号。
					_preOrder = pre->order;
				}

				//每个元素的输出宽度的计算公式（元素本身的宽度+元素之间间距）--(实际存在的元素之间不一定序号相连）。
					//同层序号相连的两个元素之间的间距=2*distance.
				totalwidth += (order - _preOrder)*(deltawidth + 2 * distance) - 2 * distance;
				//元素值输出时的宽度设置。
				cout.width(totalwidth);



			}



			//输出元素（节点）的值
			cout << p->data;
			//每个元素输出后的间距输出。最深一层（最大层）的间距为0，不输出。
			if (depth != treeDepth) {
				cout.width(2 * distance);

				cout << " ";
			}
			



			//把当前节点设置成下一个节点的前一个节点。
			pre = p;
			//按层序原则循环输出其它元素。搞定！！！
			if (p->Lchild) {
				qbit.QInsert(p->Lchild);

			}
			if (p->Rchild) {
				qbit.QInsert(p->Rchild);
			}
		}


	}
}

//计算二叉树的深度
template<typename T>
int GetDepth(BiTNode<T> *root) {
	return CountDepth<T>(root);
}


//计算二叉树的深度
template<typename T>
int CountDepth(BiTNode<T> *root) {
	int leftdepth, rightdepth, maxdepth;
	if (root == NULL)
		return 0;
	leftdepth = CountDepth(root->Lchild);
	rightdepth = CountDepth(root->Rchild);
	maxdepth = leftdepth < rightdepth ? rightdepth : leftdepth;
	return maxdepth + 1;

}

//根据数组创建节点只有data,LChild,RChild数据的二叉树
template<typename T>
void CreateTree(T *arr, int left, int right, BiTNode<T> *p) {

	if (p) {

		if (left == right) {
			BiTNode<T> *newnode = new BiTNode<T>;
			newnode->data = arr[left];
			if (!p->Lchild)
				p->Lchild = newnode;
			else if (!p->Rchild)
				p->Rchild = newnode;
		}
		if (left < right) {
			int mid = (left + right) / 2;

			if (p->Lchild)
				CreateTree(arr, left, mid, p->Lchild);
			else
				CreateTree(arr, left, mid, p);

			if (p->Rchild)
				CreateTree(arr, mid + 1, right, p->Rchild);
			else
				CreateTree(arr, mid + 1, right, p);
		}




	}


}

template<typename T>
void DeleteTree(BiTNode<T> *root) {

	if (root != NULL) {

		if (root->Lchild) {
			DeleteTree(root->Lchild);
		}
		if (root->Rchild) {
			DeleteTree(root->Rchild);
		}
		delete root;

	}
}