二叉树层次遍历及利用层次遍历打印二叉树的结构图(C++)_二叉树树状打印 c++

目录

 

1.二叉树层次遍历

2.二叉树结构图的打印

结语

---

1.二叉树层次遍历

主要用到队列操作，先入队根结点，再不断出队，判断出队结点是否有左右孩子，有则入队，直到队列空为止。

层次遍历挺简单，但是如果要输出结点序列时分清该结点所在的深度则需要稍微变化一点，思路如下：

1. 用一个变量实时记录某层的最后一个结点，当出队元素为该节点时，则之前的所有出队元素位于同一层；
2.  记录方式为每次出队后判断是否为该层最后一个结点，如是，则入队子树时按非空子树右>左的优先级记录，比如：当出队A，且A为该层最后一个结点，如果A有右树则右树被记录，若没有右树则记录左树；
3. 当出队子树没有子树时呢？这时再添加一个变量，用于记录在遇到该层最后一个结点之前的结点，记录方式同2，只是出队的结点都需要记录而不是只记录最后一个，当遇到最后一个结点不存在子树时，则将该结点作为该层最后节点。

参考代码如下：

int TraversByLevel(BTNode<char> *T) {
	if (!T) return -1;
	BTNode<char>* p = T;
	BTNode<char>* last_one = T;
	BTNode<char>* pre_last;
	std::queue <BTNode<char>*> qu;
	qu.push(p);
	while (!qu.empty()) {
		p = qu.front();
		qu.pop();
		printf("%c  ", p->value);
		if (p->rchild) {
			pre_last = (BTNode<char> *)p->rchild;
		} else if (p->lchild) {
			pre_last = (BTNode<char> *)p->lchild;
		}
		if (p == last_one) {
			printf("\n");
			if (p->rchild) {
				last_one = (BTNode<char> *)p->rchild;
			} else if (p->lchild) {
				last_one = (BTNode<char> *)p->lchild;
			} else {
				last_one = pre_last;
			}
		}
		if (p->lchild) {
			qu.push((BTNode<char> *)p->lchild);
		}
		if (p->rchild) {
			qu.push((BTNode<char> *)p->rchild);
		}
	}
	printf("\n");
	return 0;
}

 运行效果（下面是的是二叉树的打印，具体参看后文）：

---

2.二叉树结构图的打印

这个东西搞了我两天，不过最后写出来还是挺开心的，先来展示下打印一棵满二叉树的成果吧。

先讲讲思路吧：

1. 先讲讲打印结点吧，这东西无非就是找关系：找到打印结点和打印之前需要打印多少空格的关系。
2. 为了找到到关系我把1-5层的满二叉树给画了出来，如下图，可以看到在打印从左到右第一个结点时隔了一个距离设为s0，从该结点到另外一个结点又隔了一个距离设为s1，每两个结点间又有一个距离设为s2，我找到的关系如下：

• 第一行的s0 = └总列数/2)┘，而 总列数 = └2^(h-2)*6 - 1┘，h为二叉树深度（空树为0），之后几行的s0都为上一行的s0/2，这样就找到了s0的规律了；
• 第一行的s1 = 0，而从第二行开始s1开始增加之后不断减少，但是可以看出s1的长度受上一行两个关系字符'/'和'\'的距离（设为g0）的影响，所以先需要找到这个的规律后，s1 = g0 + 2；
• 得知了s0和s1后，s2只需要算就能算出来了 s2 = (总列数- (s0-1)*2 - 上层结点数*2 - s*上层结点数)/(上层结点数 - 1);
• 再说关系行（'/'和'\'）的绘制，这里的第一行空格数与上一行的s0有关，而'/'和'\'之间的距离g0知道后，每一对'/'和'\'之间的距离就很容易计算出来了，所以关键是找出g0；
• 这里g0找的方式就有点投机取巧了，一开始我以为是等比数列，前三项是1,3,9，但是到第四项，第五项就变成了21和45？？？没办法，我只好用曲线拟合一下了。拟合结果如下右图。这样就解决了问题了。

然后就是程序编写了，一开始我是在层次遍历上改的，但是发现，只能满足打印满二叉树，因为我设置了一个变量，当结点行处理完就处理关系行，可是发现，关系行处理时出队结点固定了，无法读取之前结点的左右关系，并且当不是二叉树时，遇到空树就完全无法处理了，让后我就想了：无论什么二叉树都是一棵满二叉删删减减变的，那我就按照满二叉处理任何二叉树。然后就设计如下思路：

1. 空树也要入队，遇到空树时打印空格；
2. 出队元素为NULL时，向队列里入队两个NULL，代表空树的两个空子树；
3. 建立两个队列，一个用于打印结点，一个打印关系。

参考代码如下（upToInt为向上取整，fillWith为向字符串中填写指定个数的字符，返回值为buffer行数）：

int BTreePrintToStrArr(BTNode<char> *T, char buffer[][STR_MAX], int size) {
	if (!T || !buffer) return -1;
	BTNode<char>* p = T;
	int height;
	int tatolCol;
	int spaces[3];
	int gap[2];
	int count;
	int i, j, k;
	std::queue <BTNode<char>*> qu_travers;
	std::queue <BTNode<char>*> qu_print;
	// init
	memset(buffer, 0, size*sizeof(char));
	height = getBTreeDepth(T);
	tatolCol = upToInt(pow(2, height - 2)*6 - 1);
	gap[0] = (int)
			 (0.0417*pow(height,5) 
			 - 0.6667*pow(height,4) 
			 + 4.4583*pow(height,3) 
			 - 13.333*pow(height,2) 
			 + 18.5*height - 9);
	spaces[0] = upToInt(tatolCol/2.0);
	count = i = j = k = 0;
	qu_travers.push(p);
	while (!qu_travers.empty() && i < height*2) {
		switch (i%2) {
		case 0: // process node
			p = qu_travers.front();
			qu_travers.pop();
			qu_print.push(p);
			if (count == 0) {
				fillWith(&buffer[i][j], ' ', spaces[0] - 1);
				j += spaces[0] - 1;
			} else if ((count+1)%2 == 0) {
				fillWith(&buffer[i][j], ' ', spaces[1]);
				j += spaces[1];
			} else {
				fillWith(&buffer[i][j], ' ', spaces[2]);
				j += spaces[2];
			}
			count++;
			buffer[i][j++] = p?(p->value):' ';
			qu_travers.push(p?(BTNode<char> *)p->lchild:NULL);
			qu_travers.push(p?(BTNode<char> *)p->rchild:NULL);
			if (count == (int)pow(2,(i+1)/2)) {// new line
				buffer[i][j] = '\0';
				i++;
				j = 0;
				k = 0;
				spaces[0] /= 2;	
				gap[0] = (int)
						(0.0417*pow(height - i/2,5) 
						- 0.6667*pow(height - i/2,4) 
						+ 4.4583*pow(height - i/2,3) 
						- 13.333*pow(height - i/2,2) 
						+ 18.5*(height - i/2) - 9);
				if (count > 1) {
					gap[1] = (tatolCol - spaces[0]*2 - gap[0]*count - count*2)/(count - 1);
				} else {
					gap[1] = 0;
				}
			}
			break;
		case 1: // process link
			p = qu_print.front();
			qu_print.pop();
			// left
			if (k == 0) {
				fillWith(buffer[i] + j, ' ', spaces[0]);
				j += spaces[0];
			} else {
				fillWith(buffer[i] + j, ' ', gap[1]);
				j += gap[1];
			}
			if (p && p->lchild) {
				buffer[i][j++] = '/';
			} else {
				buffer[i][j++] = ' ';
			}
			k++;
			// right
			fillWith(buffer[i] + j, ' ', gap[0]);
			j += gap[0];
			if (p && p->rchild) {
				buffer[i][j++] = '\\';
			} else {
				buffer[i][j++] = ' ';
			}
			k++;
			if (k >= count*2 || qu_print.empty()) {
				buffer[i][j] = '\0'; j = 0;
				i++;
				spaces[1] = gap[0] + 2;
				if (count > 1) {
					spaces[2] = (tatolCol - (spaces[0]-1)*2 - count*2 - spaces[1]*count)/(count - 1);
				} else {
					spaces[2] = 0;
				}
				count = 0;
			}
			break;
		}
	}
	return i - 1;
}

满二叉图效果图如下：

其他二叉图效果图如下：

---

结语

最后还是觉得自己的方法有些冗杂，而且画出来效果不是特别好，至于深度大于6的还未试过，不知道会不会有问题。