A1064 Complete Binary Search Tree

在这里插入图片描述

在这里插入图片描述
这题的建树方式是直接数组，tree[maxn]
因为在题目里已经明确需要一颗完全二叉树。

NOTE

遇到完全二叉树，应该先想到最简单的建树方式，那就是数组表示数，root=1，
左子树parent2 右子树parent2+1
数组的下标表示结点序号，数组的内容也就是结点的内容（数字）这两个也是要好好区分的
将tree数组按下标1~n输出，也即是树的层序遍历。
而树的中序遍历如下：(先序、后序同理)

void inOrder(int root)
 {
     if(root>n) return;
     inOrder(root*2);//先遍历左子树
     访问结点root
     inOrder(root*2+1); //最后遍历右子树
 }

而二叉搜索树有一个重要性质，按中序遍历树，得到的是从小到大的有序序列。

因此上述遍历中访问结点root一步的代码便是将序列中的值赋给结点
tree[root]=number[index1++];
若使用#include<bits/stdc++>，不要给全局变量取名为index，这与一个函数冲突。

此题代码如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int tree[maxn],number[maxn];
int n,index1=0;
 void inOrder(int root)
 {
     if(root>n) return;
     inOrder(root*2);
     tree[root]=number[index1++];
     inOrder(root*2+1);
 }


int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&number[i]);
    }
    sort(number,number+n);
    inOrder(1);
    for(int i=1;i<=n;i++)  
    {
        printf("%d",tree[i]);
        if(i<n) printf(" ");
    }

    
}

A1099 Build A Binary Search Tree

在这里插入图片描述

会了上一题以后，这一题就格外简单啦~
不同之处就在于这次不是完全二叉树，所以利用二叉树静态写法（和之前的树一模一样啦）
因此这次结点的顺序是输入规定好的，要多写一个层序遍历的函数将结果输出

#include <bits/stdc++.h>
using namespace std;
const int maxn = 105;
int n;
int k = 0;
int num[maxn];
struct Node
{
    int data;
    int left, right;
} node[maxn];

void inOrder(int root)
{
    if (root == -1)
        return;
    inOrder(node[root].left);
    node[root].data = num[k++];
    inOrder(node[root].right);
}

void BFS(int root)
{
    queue<int> q;
    q.push(root);
    int t = 0;
    while (!q.empty())
    {
        int top = q.front();
        q.pop();
        t++;
        printf("%d", node[top].data);

        if (t != n)
            printf(" ");
        if (node[top].left != -1)
            q.push(node[top].left);
        if (node[top].right != -1)
            q.push(node[top].right);
    }
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d%d", &node[i].left, &node[i].right);
    }

    for (int i = 0; i < n; i++)
    {
        scanf("%d", &num[i]);
    }
    sort(num, num + n);
    inOrder(0);
    BFS(0);
}