算法笔记Codeup题解

100000612 - 《算法笔记》9.3小节——数据结构专题(2)->树的遍历

问题 A: 树查找

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int arr[MAXN];


typedef long long ll;

ll fast_pow(int d, int base){
    int n = d;
    ll res = 1;
    while(n>0){
        if( n & 1) res = res*base;
        base = base * base;
        n >>= 1;
    }
    return res;
}

int main(int argc, char const *argv[])
{
    int n, d;
    while(cin >>n && n){
        for (int i = 0; i < n; ++i)
           cin >> arr[i]; 
        cin >>d;
        if ( n < fast_pow(d, 2) ){      // d层没有节点
            cout << "EMPTY"<<endl; 
        }else{
            int beginn = fast_pow(d-1, 2);
            int endn = fast_pow(d, 2);
            cout << beginn;
            for (int i = beginn+ 1; i < n && i< endn; ++i)
                cout<< " " << i ;
            cout << endl;
        }

    }

    return 0;
}

问题 B: 树的高度

题目要求我们练习树的静态写法。但其实这道题直接计算每个节点的高度就行了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;

struct Node{
    int height;  
    std::vector<int> child;
}Nodearr[MAXN];

int getHeight(){
    int m = -1;
    for (int i = 1; i <= n; ++i){
        if(Nodearr[i].height > m)
            m = Nodearr[i].height;
    }
    return m;
}

int main(int argc, char const *argv[]){
    scanf("%d", &n);
    int a, b;
    Nodearr[1].height = 1;
    while(scanf("%d %d",&a,&b)!=EOF){
        // Nodearr[a].child.push_back(b);
        Nodearr[b].height = Nodearr[a].height +1;
    }
    cout << getHeight() << endl;
    return 0;
}

正规写法：先构建树， 然后再层次遍历计算高度

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int m=10010;
struct node{
	int layer;
	vector<int> child;
}tree[m];
int MaxHigh;

// 树的静态写法的层次遍历
void BFS(int root){
	MaxHigh=0;
	queue<int> q;
	tree[root].layer =1;
	q.push(root);
	if(tree[root].layer>MaxHigh) MaxHigh=tree[root].layer;
	while(!q.empty()){
		int front=q.front() ;
		q.pop();
		for(int i=0;i<tree[front].child.size();i++){
			int child=tree[front].child[i];
			tree[child].layer =tree[front].layer +1;
			q.push(child);
			if(tree[child].layer>MaxHigh) MaxHigh=tree[child].layer;
		}
	}
}

int main(){
	int n,a,b;
	while(scanf("%d",&n)!=EOF){
        while(scanf("%d %d",&a,&b)!=EOF){
			tree[a].child.push_back(b);
		}
		BFS(1);
		printf("%d\n",MaxHigh);
	}
	return 0;
}

100000613 - 《算法笔记》9.4小节——数据结构专题(2)->二叉查找树（BST）

问题 A: 二叉排序树

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;
int data[MAXN];

struct Node{
    int v;
    Node *lc, *rc;
};

Node* newNode(int x){
    Node *now = new Node;
    now->v = x;
    now->lc = now->rc = NULL;
    return now;
}

void insert(Node* &root, int x){
    if(root == NULL){   
        root = newNode(x);
    }
    if(root->v == x) return; // 已存在
    else if (x < root->v ) insert(root->lc, x);
    else if (x > root->v ) insert(root->rc, x);
}

Node *createTree(){
    Node *root = NULL;  // ▲注意此处是NULL， 而不是new Node
    for (int i = 0; i < n; ++i)
        insert(root, data[i]);
    return root;
}

void preOrder(Node *root){
    if(root == NULL ) return;
    cout << root->v << " ";
    preOrder(root->lc);
    preOrder(root->rc);
}

void inOrder(Node *root){
    if(root == NULL ) return;
    inOrder(root->lc);
    cout << root->v << " ";
    inOrder(root->rc);
}

void postOrder(Node *root){
    if(root == NULL ) return;
    postOrder(root->lc);
    postOrder(root->rc);
    cout << root->v << " ";
}

int main(int argc, char const *argv[]){
    while(cin >> n){
        for (int i = 0; i < n; ++i)
            cin >> data[i];
        Node* root = createTree();
        preOrder(root);
        cout << endl;
        inOrder(root);
        cout << endl;
        postOrder(root);
        cout << endl;
    }
    return 0;
}

问题 B: 二叉搜索树

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 5;
int n;
int data[MAXN];

struct Node{
    char v;
    Node *lc, *rc;
};

Node* newNode(char x){
    Node *now = new Node;
    now->v = x;
    now->lc = now->rc = NULL;
    return now;
}

void insert(Node* &root, char x){
    if (root == NULL){
        root = newNode(x);
        return ;
    }
    if (x == root->v ) return;
    else if (x < root->v ) insert(root->lc, x);
    else if (x > root->v ) insert(root->rc, x);
}

Node* createTree(string s){
    Node *root = NULL;
    for (int i = 0; i < s.size(); ++i){
        insert(root, s[i]);
    }
    return root;
}


void preOrder(Node *root, string &s){
    if(root == NULL ) return;
    s += root->v;
    preOrder(root->lc, s);
    preOrder(root->rc, s);
}

void inOrder(Node *root, string &s){
    if(root == NULL ) return;
    inOrder(root->lc, s);
    s += root->v;
    inOrder(root->rc, s);
}

void postOrder(Node *root, string &s){
    if(root == NULL ) return;
    postOrder(root->lc, s);
    postOrder(root->rc, s);
    s += root->v;
}


int main(int argc, char const *argv[]){
    int n;
    while( cin >> n && n){
        string target;
        cin >> target;
        string preans, postans;
        Node *ans = createTree(target);
        preOrder(ans, preans);
        postOrder(ans, postans);
        // inOrder(root, in);     // 由于中序遍历的结果就是排序的结果, 因此都一样
        for (int i = 0; i < n; ++i){
            string s;
            cin >> s;
            string in, pre, post;
            Node *root = createTree(s);
            preOrder(root, pre);
            if (pre == preans){
                postOrder(root, post);
                if (post == postans) cout << "YES" <<endl;
                else  cout << "NO" <<endl;
            }else  cout << "NO" <<endl;
         }  
    }
    return 0;
}