[数据结构与算法]PAT A 1099 AC代码

woc我忘了二叉搜索树中序遍历就是递增序列，我简直思路绕地球一圈，有空重新写

可用于理解二叉搜索树的题目

写了一个countnode函数来计算从某结点出发有几个空结点，若==0，则该结点为根的树满

插入数据的关键是判断左子树满不满

再写了一个insert函数来根据该结点左子树满不满以及该结点空不空来插入数据

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> nums,Level[101];
int tag[101]={0};
struct node{
	int num=-1;
	int left;
	int right;
}Node[101];
int countnode(int index){
	if(index==-1){
		return 0;
	}else if(Node[index].num!=-1){
		return countnode(Node[index].left)+countnode(Node[index].right);
	}else{
		return 1+countnode(Node[index].left)+countnode(Node[index].right);
	}
}
void insert(int index,int x){
	if(countnode(Node[index].left)!=0){ //左子树不满，往左子树插入
		insert(Node[index].left,x);
	}else if(Node[index].num!=-1){  //左子树满但该结点非空，往右子树插入
		insert(Node[index].right,x);
	}else{                          //左子树满且该结点为空，在该结点处插入
		Node[index].num=x;
	}
}
void Levelorder(int index,int level){
	if(index==-1) return;
	Level[level].push_back(index);
	Levelorder(Node[index].left,level+1);
	Levelorder(Node[index].right,level+1);
}
int main(){
	int N;
	cin>>N;
	nums.resize(N);
	for(int i=0;i<N;i++){
		scanf("%d %d",&Node[i].left,&Node[i].right);
		if(Node[i].left!=-1) tag[Node[i].left]=1;
		if(Node[i].right!=-1) tag[Node[i].right]=1;
	}
	for(int i=0;i<N;i++){
		scanf("%d",&nums[i]);
	}
	sort(nums.begin(),nums.end());
	int root;
	for(int i=0;i<N;i++){
		if(tag[i]==0){
			root=i;
			break;
		}
	}
	Levelorder(root,0);
	for(int i=0;i<N;i++){
		insert(root,nums[i]);
	}
	printf("%d",Node[root].num);
	for(int i=1;i<N;i++){
		for(auto it:Level[i]){
			printf(" %d",Node[it].num);
		}
	}
	return 0;
}