前言

今天第一次做一下cpp的树的算法，还是遇到了不少问题的，对树的学习其实在考研期间会比链表和数组少很多，其中最关键的要学会用递归。求深度也好，DSF也好，构造树也好，都用递归。

实现思路

一些疑问的解决

1. 为什么不在构造函数中创建树?

最初我考虑在构造函数初始化树的值，但是后面发现还是有问题，搜了一下，gpt的回答是这样的。

构造函数在C++中是一种特殊的成员函数，它在创建类的对象时被自动调用，用于初始化新创建的对象。> 在我们的例子中，TreeNode类的构造函数已经被用来初始化TreeNode对象的val，left和right成员。这个构造函数非常简单，只接受一个参数（节点的值），并默认将left和right指针设置为NULL。
但是，如果你想在构造函数中创建整个二叉树，那可能会有些复杂。因为构造函数在创建新对象时自动被调用，所以你不能在构造函数中直接调用它自己（这会导致无限递归）。你也不能在构造函数中改变已经创建的对象，因为构造函数的目的是初始化新对象，而不是修改已有的对象。
所以，虽然你可以在构造函数中进行一些初始化操作，但是创建整个二叉树通常需要一个单独的函数，像我们之前提供的buildTree函数。然后你可以在你的代码中调用这个函数来创建二叉树，而不是在构造函数中进行这个操作。

我的代码

#include <iostream>
#include<algorithm>
#include<cmath>
#include <queue> 
using namespace std;

struct node {
	int date;
	char info;
	node* left;
	node* right;
};

//以递归的方式构建一棵树
void createTree(node*& t) {
	char str;
	cin >> str;
	if (str == '#') {
		t = NULL;
	}
	else {
		t = new node;//为t开辟空间
		t->info = str;
		createTree(t->left);
		createTree(t->right);
	}
}

//树的深度
int depth(node* root) {
	if (root == nullptr) {
		return 0;
	}
	int left = depth(root->left);
	int right = depth(root->right);
	return max(left, right) + 1;
}

//打印一棵树满二叉树，只能打印满二叉树，节点数目最好不要超过10
void print(node*& root) {
	//存放打印的二叉树
	char str[10][100] = {};
	queue<node*> q;
	int h = depth(root);
	q.push(root);
	int index = 0;
	while (!q.empty()) {
		int size = q.size();
		//存放每一层的节点
		vector<char> list;
		for (int i = 0; i < size; i++) {
			node* temp = q.front();
			q.pop();
			list.push_back(temp->info);
			//cout << temp->info;
			if (temp->left != nullptr) {
				q.push(temp->left);
			}
			if (temp->right != nullptr) {
				q.push(temp->right);
			}
		}
		bool flag = true;
		int j = 0;
		//打印前面部分空白
		while (j <= 2 * h - 1 - index) {
			str[index][j] = ' ';
			j++;

		}
		//保持第一行居中
		if (index == 0) {
			for (int m = 0; m < h - 2; m++) {
				str[index][j++] = ' ';
			}
		}

		for (int k = 0; k < list.size(); k++) {
			//如果是一层最后一个节点
			if (k == list.size() - 1) {
				str[index][j++] = list[k];
			}
			else {
				//相邻左右子节点
				if (k % 2 == 0) {
					str[index][j++] = list[k];
					for (int l = 0; l < 3 + 2 * (h - index / 2 - 1); l++) {
						str[index][j++] = ' ';
					}
				}
				else {
					str[index][j++] = list[k];
					str[index][j++] = ' ';
				}
			}
		}

		index += 2;
		//cout << endl;
	}
	for (int i = 0; i < 10; i++) {
		if (i % 2 == 1) {
			for (int j = 0; j < 100; j++) {
				str[i][j] = ' ';
			}
		}
	}
	for (int i = 0; i < 10; i++) {
		if (i % 2 == 0) {
			for (int j = 0; j < 100; j++) {
				if (str[i][j] - '0' >= 0 && str[i][j] - '0' <= 9 && i < 2 * h - 2) {
					str[i + 1][j - 1] = '/';
					str[i + 1][j + 1] = '\\';
				}

			}
		}
	}
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 100; j++) {
			cout << str[i][j];
		}
		cout << endl;
	}
}

void DeepFirstSearch(node *root) {
	if (root == NULL) {
		return;
	}
	else {
		cout << root->info << ' ';
		DeepFirstSearch(root->left);
		DeepFirstSearch(root->right);
	}

}


int main() {
	node* T;
	createTree(T);
	cout << "树的深度：" << depth(T) << endl;
	print(T);
	DeepFirstSearch(T);
	return 0;
}