博客

1. 构建树的基本数据结构

typedef struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode():val(0),left(nullptr),right(nullptr){}; 
	TreeNode(int x):val(x),left(nullptr),right(nullptr){}; //通过结构体内的方法初始化树的节点
}T;

2. 按照前序（遍历）顺序递归构建二叉树

void InorderCreateTree(T*& t){ //这里非常重要!在构建二叉树时传入的参数必须是树的引用，也就是要加'&'，否则传递的只是形参，无法通过该函数进行赋值;
	string x;		
	cin >> x;		//通过字符串读入数字，使用String类型，可以读入任何符合要求的数字 
	if(x[0] == '#'){
		t = nullptr; //当输入的第一个字符为'#'时该节点为空指针，这里的判断字符可以自定义
	}else{
		t = new T; //定义一个新的树节点
		t->val = stoi(x); //对该节点赋值
		InorderCreateTree(t->left); 
		InorderCreateTree(t->right); //递归构建树 
	}
	return;
}

3.按照层次（遍历）顺序构建二叉树

//基本构建树的思路和上面的前序构建差不多，只不过用了层次遍历的方法去构建，不再赘述
void layerCreateTree(T* &t){
	string x;
	cin >> x; //读入一个数字，用于构建根节点
	queue<T*> q;
	while(!q.empty())q.pop();
	if(x[0] == '#'){
		t = NULL;
		return; 
	}else{
		t = new T;
		t->val = stoi(x);
		q.push(t);
	}
	T* temp;
	while(!q.empty()){
		temp = q.front();
		if(temp == nullptr) continue; //如果为空节点，则不再加入到队列当中，因为空节点不会再有后续的子树;
		q.pop();
		cin >> x; //读入一个数字，用于构建左孩子 
		if(x[0] == '#'){
			temp->left = nullptr;
		}else{
			temp->left = new T;
			temp->left->val = stoi(x);
			q.push(temp->left);
		}
        
		cin >> x; //读入一个数字，用于构建右子树
		if(x[0] == '#'){
			temp->right = nullptr;
		}else{
			temp->right = new T;
			temp->right->val = stoi(x);
			q.push(temp->right);
		}
	}
	return;
}

4.完整代码（通过前序，层次顺序构建树，并进行前序遍历和层次遍历）

#include <iostream>
#include <queue>
#include <stack>
#include <string>
using namespace std;

typedef struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode():val(0),left(nullptr),right(nullptr){}; 
	TreeNode(int x):val(x),left(nullptr),right(nullptr){};
}T;

void InorderCreateTree(T*& t){
	string x;
	cin >> x;
//	if(t==nullptr) return; 
	if(x[0] == '#'){
		t = nullptr;
	}else{
		t = new T;
		t->val = stoi(x);
		InorderCreateTree(t->left);
		InorderCreateTree(t->right); 
	}
	return;
}

void layerCreateTree(T* &t){
	string x;
	cin >> x;
//	if(t==nullptr) return; 
	queue<T*> q;
	while(!q.empty())q.pop();
	if(x[0] == '#'){
		t = NULL;
		return; 
	}else{
		t = new T;
		t->val = stoi(x);
		q.push(t);
	}
	T* temp;
	while(!q.empty()){
		temp = q.front();
		if(temp == nullptr) continue;
		q.pop();
		cin >> x; 
		if(x[0] == '#'){
			temp->left = nullptr;
		}else{
			temp->left = new T;
			temp->left->val = stoi(x);
			q.push(temp->left);
		}
		cin >> x;
		if(x[0] == '#'){
			temp->right = nullptr;
		}else{
			temp->right = new T;
			temp->right->val = stoi(x);
			q.push(temp->right);
		}
	}
	return;
}

void preRecursive(const T* t){
	if(t == nullptr) return;
	cout << t->val << " ";
	preRecursive(t->left);
	preRecursive(t->right);
}

void layerTraserval(T* t){
	if(t == nullptr) return;
	queue<T*> q;
	while(!q.empty())q.pop();
	q.push(t);
	T* temp;
	while(!q.empty()){
		temp = q.front();
		q.pop();
		cout << temp->val << " ";
		if(temp->left!=nullptr){
			q.push(temp->left);
		}
		if(temp->right!=nullptr){
			q.push(temp->right);
		}
	}
	cout <<endl;
	return;
}


int main(){
	T* root;
	InorderCreateTree(root);
	//InorderCreateTree(root);
	cout << "树已经创建完毕！" << endl;
	cout<< "递归先序遍历二叉树" << endl;
	preRecursive(root);
	cout << endl;
	cout << "层次遍历二叉树" <<endl;
	layerTraserval(root);
	
	T* root2;
	layerCreateTree(root2);
	cout << "树已经创建完毕！" << endl;
	cout << "层次遍历二叉树" <<endl;
	layerTraserval(root2);
	cout<< "递归先序遍历二叉树" << endl;
	preRecursive(root2);
	cout << endl;
	return 0;
}

前序遍历顺序： 12 -> 23 -> 45 -> 67 -> 34 -> 56 -> 78

层次遍历顺序： 12 -> 23 -> 34 -> 45 -> 67 -> 56 -> 78