【C语言】打印二叉树树形（制表符实现，清晰+高拓展）（2022-10-22 更新—偏移量说明）

2022-10-22 补充

好久没来 CSDN 了，今晚一看发现一些小伙伴反应说看文中的 ==偏移量== 看的很晕（当时自己写比较主观哈哈），秉着要对文章负责的态度，我在这里统一给大家详细解释一下
如果是第一次来的话，可以先去看正文
~没想到这么久了还有人看我的文章，挺感动的，先谢谢大家的支持了~~

废话不多说，先看画的这张图（相信大家看到图心里应该就有底了）
这张图里边已经基本上把算法的核心全部画出来了，确认根结点的位置是重点（画树枝是次要的）
说明：为了画线比较好看，我把对 x 坐标的减 1 操作放到了第一个偏移量的位置，这样能使得线段对的上每个结点
​

首先要解释的就是 偏移参数 以及 三个偏移量 的作用：

1. tap：这个是父节点传递给子结点的相对偏移量
   如算法中所示，它是直接针对 tap1 的，用于计算父树的偏移量
2. tap1：也就是图中红色的划线，该偏移我叫做 父树偏移量
   是为了计算当前结点的父节点再整个空间的偏移量，加上这个偏移量，父节点的位置就相当于初始化状态的父节点，它的子结点（当前结点）可以直接基于父节点来计算自己的偏移量
3. tap2：也就是图中绿色的划线，该偏移我叫做 子树偏移量
   这是在子树为右子树的情况下需要的，前边的 tap1 我们已经确定了以父节点为根的树在空间中的位置，而子结点如果是右子树的话，那么还需要将左子树的位置空出来，tap2 就是干这件事的
4. tap3：也就是图中橙色的画线，该偏移我叫做 半偏移量
   这是左右子树都需要的，左子节点用 tap1 就可以确定相对位置，而右子节点用 tap1 和 tap2 的和，也就确定了和左子树一样的相对位置（分别使用者两个偏移量，左右子树的状态就相同了，tap3 的规则对他们来说是一样的）
   准确地说，tap3 是树枝的长度，也就是为了下面的树能有空间继续放的下去而需要的偏移量

到这里，大家对几个偏移量的作用应该基本上都清楚了，至于每个偏移量的计算方法，这里我简单说明一下（手动在纸上模拟一遍更好理解哦），这里我顺序倒着解释可能会更好

1. tap3：首先是 tap3，它的作用就是为下边的树空出位置，计算方法是 2^treeDepth-depth-1^
   什么意思呢？以上图为例，该树深度为 4，则宽度为 2^4^=16，所以一个子树的宽度应该是 8，也就是2^4-1^
   所以上式的 -1 操作表明了，子树的宽度是父树的一般。再而，每往下一层，子树的宽度都会减半，所以得减去当前深度 depth，所以最终的指数部分就是 treeDepth-depth-1
2. tap2：然后是 tap2，它的作用是把右子树向右挪出一个左子树的位置
   所以我们需要的，自然就是左子树的宽度啦，由于是在同一层，所以不需要减半也就不用 -1，所以指数部分是 treeDepth-depth，而前边的 right 就好理解了，因为右子树才需要否则置为 0 表示不需要
3. tap1：再而是 tap1，它的作用是确定父树在整个空间的偏移量
   而该父树的父树可能是左子树也可能是右子树，爷爷也可能是左子树和右子树，这么多情况要怎么确定呢？
   答案就是 tap 偏移量了，由它来记录前边的爸爸爷爷们究竟有多少是右子树，得到一个累计值，然后 tap1 就可以根据这个累计值算出整体在空间的偏移量了！由于是在同一层，所以也不需要 -1
4. tap：这个在 tap1 已经介绍过了，就是相对偏移量，用来保存该节点的爸爸爷爷到底做了多少次右子树，是一个累计值

至于你们要问，为什么我会知道需要这些偏移量。我只能说，这是一点点调试出来的（无奈）
一开始就是只有 tap3，确定需要为子树空出多少就好了嘛
然后就发现，怎么区分左右子树？！所以就出现了 tap2
最后才发现最致命的一点，一层层的递归下，每棵小树（父节点+子结点）他们分别在空间的哪个位置？所以出现了辅助性的 tap 和用于确定相对位置的 tap1

好了，整一个完整的说明就到这里了
从看到评论和私信，到拿起一年前的代码重新理解（哭），再到捋好思路将说明补充好，已经过去一个半小时了
虽然这对我来说有点花时间（一年过去了，心态也不太一样了）
但我自己清楚在看别人博文看不懂，自己苦苦理解几个小时没出来个结果是多么痛苦（我看别人博文时，对于说的含含糊糊的也有要骂街的冲动2333），所以我也决心一定要把思路讲清楚，让自己成为自己讨厌的人，是很不应该的啊

就到这里啦，今年起来就没写过博客，今天也顺带把手感提上来了，后边看情况再更新吧
看到以前的文章还能对大家有帮助，挺开心的，能帮到你们就好。溜了溜了~（有什么问题可以再评论或者私信我哦）

---

0. 前言

上 CSDN 找了很多份树形代码，一个共通的感觉就是拓展性不够强
比如说树大了节点之间被撑开无法兼容性不好
没有使用树枝连接的画显示稍显混乱，使用斜线当树枝又不好拓展
还有一部分就是代码太冗长看不懂

基于此，我打算用回制表符，力求清晰显示出树形
肝了几个小时的代码，过程中一点一点调出来树形
代码部分也在不断优化，思路在不断的调试中也不断改变
最后总结出一种以绝对偏移量画树形的方法，下边将一一对代码进行解释

1. 效果展示

首先树画出来的效果如下，可以很好兼容各种树形，显示也很清晰
​
​
拓展性扛扛的完全不用担心
​

2. 核心代码及解读

① 核心代码

代码也是简洁 + 清晰

/*
* 递归打印打印出树形
* T		正在打印的树
* depth	目前在打印树的第几层
* right	该子树是否为右子树
* tap	目前子树需要的相对偏移数量
*/
Status Traverse_R(BiTree T, int depth, int right, int tap) {
	if (T == NULL) return OK;

	// 获取一次树的初始高度，用于计算相对偏移数量
	static int treeDepth = BiTreeDepth(T);
	// 记录当前光标位置，用于在递归中记录当前递归时树的位置
	int x, y;
	// 拆分树，将树的左右子树拆分开来
	BiTree L, R;
	BreakBiTree(T, L, R);

	// 计算父树的偏移量
	int tap1 = tap * pow(2, treeDepth - depth);
	// 计算子树的偏移量
	int tap2 = right * (pow(2, treeDepth - depth));
	// 计算半偏移量
	int tap3 = pow(2, treeDepth - depth - 1);

	// 获取根的坐标
	// x 计算方法为：父偏移量 + 子偏移量 + 半偏移量 - 1
	// y 计算方法为：目前打印的层数 * 2
	x = tap1 + tap2 + tap3 - 1;
	y = depth * 2;

	// 打印根的位置
	gotoxy(x * 2, y);
	printf("%d", T->data);

	// 在打印子树时，当前层数+1
	depth++;
	// 计算子树的父偏移量
	tap = tap * 2 + (right == 1 ? 2 : 0);
	if (L == NULL && R == NULL) return OK;
	else if (R == NULL) {
		// 打印左子树的位置
		gotoxy(x * 2 - tap3, y + 1);
		printf("┏");
		for (int i = 0; i < tap3-1; i++) printf("━");
		printf("┛");
		Traverse_R(L, depth, 0, tap);
	}
	else if (L == NULL) {
		// 打印右子树的位置
		gotoxy(x * 2, y + 1);
		printf("┗");
		for (int i = 0; i < tap3-1; i++) printf("━");
		printf("┓");
		Traverse_R(R, depth, 1, tap);
	}
	else {
		// 打印左右子树的位置
		gotoxy(x * 2 - tap3, y + 1);
		printf("┏");
		for (int i = 0; i < tap3 - 1; i++) printf("━");
		printf("┻");
		for (int i = 0; i < tap3 - 1; i++) printf("━");
		printf("┓");
		Traverse_R(L, depth, 0, tap);
		Traverse_R(R, depth, 1, tap);
	}
}

// 打印树形接口
Status Traverse(BiTree T) {
	Traverse_R(T, 0, 0, 0);
	return OK;
}

② 完整解读：

在不断的调试后，最终得出的方案是：确定每一个根节点在屏幕上的绝对坐标

其实打印树形，无非就是打印两个东西：根节点的值 + 树枝
这一共产生了 3 问题：
① 根节点应该打印在哪里？
② 树枝应该打印在哪里？
③ 树枝应该打印多长？

而再继续往下整理思路
其实当根节点的位置确定后，树枝的所有需要的参数也集齐了（在这个解决方案中）

接下来说明一下根节点位置的确定方案：
首先作为二叉树，就会有左子树和右子树之分，这也是整个偏移量设计的重点

左右子树最大的不同就是，右子树的偏移量比左子树多出来一半
所以首先就需要确定当子树作为右子树时的偏移量（变量 tap），作宏观调整
但只有这个偏移量还不够，想象这种情况：子树为右子树，但父节点又是作为左子树
这时单单依靠宏观调整已经不够了，需要引入一个 right 作两子树间的调整
最后，子树根的位置确定了，还需要确定该子树还衍生出的树枝的长度
这个就是更小的一个偏移量，也就是上边的半偏移量，时参考了本层树计算出来的

最后，就是偏移量需要不断继承下去，供下一层的子树使用

---

3. 辅助代码

① 头文件

//常用头文件
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

//常用常量
#define OK 1
#define ERROR 0
#define OVERFLOW -1
#define SUCCESS 1
#define UNSUCCESS -1

//常用类型定义
typedef int Status;

// 树数据类型
typedef int TElemType;

// 二叉树结构体
typedef struct BiTNode {
	TElemType data;
	struct BiTNode* lchild, * rchild;
} BiTBode, *BiTree;

// 部分需要的接口
// 将二叉树分为根，左子树，右子树三个部分
Status BreakBiTree(BiTree& T, BiTree& L, BiTree& R);
// 获取树的深度
int BiTreeDepth(BiTree T);

② 工具代码与实现代码

#include <Windows.h>

//改变光标位置
void gotoxy(int x, int y)
{
	// 更新光标位置
	COORD pos;
	HANDLE hOutput = GetStdHandle(STD_OUTPUT_HANDLE);
	pos.X = x;
	pos.Y = y;
	SetConsoleCursorPosition(hOutput, pos);
}

// 获取树的深度
int BiTreeDepth(BiTree T) {
	if (T == NULL) return 0;

	int depthLeft, depthRight;
	depthLeft = BiTreeDepth(T->lchild);
	depthRight = BiTreeDepth(T->rchild);

	return 1 + (depthLeft > depthRight ? depthLeft : depthRight);
}

// 将二叉树分为根，左子树，右子树三个部分
Status BreakBiTree(BiTree& T, BiTree& L, BiTree& R) {
	if (T == NULL) return ERROR;
	L = T->lchild;
	R = T->rchild;

	return OK;
}

---

两点一线，纵曲也终抵达（IceClean）