利用二叉链表进行数据的存储与遍历
先用 l , r 数组将输入的数据存储,用 a 数组存储树的数值,并升序排序,这样有利于后期的深度优先搜索进行数据插入(因为二叉搜索树进行中序遍历是升序排序的),创建二叉树的时候就先判断是否为空树,不是空树就要先创建左子树,后创建右子树的顺序进行创建,建树的主要方式与深度优先搜索相差不大。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct TreeNode{
int val; //树节点的值
int id; //此题id没有作用
TreeNode* left, *right; //左子树和右子树
};
const int N = 110;
int l[N], r[N]; //记录读入的数据,并用他们建立二叉树
int n, k;
int a[N]; //数的值序列
TreeNode* createTree(int t)
{
if (t==-1) return NULL; //如果传入的数据为-1,就视为空树,返回NULL
TreeNode* T = (TreeNode*)malloc(sizeof(TreeNode));
T->left = createTree(l[t+1]); //建立左子树
T->right = createTree(r[t+1]); //建立右子树
return T;
}
void dfs(TreeNode* T) //利用深度优先搜索进行数值的填充
{
if (T->left) dfs(T->left);
T->val = a[k++];
if (T->right) dfs(T->right);
}
void levelTraversal(TreeNode* T) //简单的层序遍历
{
queue<TreeNode*> q;
q.push(T);
while(q.size()){
auto t = q.front();
q.pop();
cout<<t->val<<' ';
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
}
}
int main()
{
cin>>n;
for (int i=1;i<=n;i++) cin>>l[i]>>r[i];
for (int i=1;i<=n;i++) cin>>a[i];
sort(a+1, a+1+n);
TreeNode* T = createTree(l[0]); //l[0]未赋初值且l为全局变量,因此l[0]=0
k = 1; //k是记录a数组的下标,在dfs函数中有用到
dfs(T);
levelTraversal(T);
return 0;
}
第一次写题解,希望对屏幕前的你有所启发,如果有不懂的欢迎评论。