Practice:BinaryTree

8 minute read

一·基础题目

二叉树的 BFS 遍历

题目描述

给定一棵二叉树（以结点编号和左右孩子编号的形式输入），请输出这棵树的 层序遍历（BFS 遍历） 序列。

输入格式

第一行：一个整数 n (1 ≤ n ≤ 1000)，表示结点数。
接下来 n 行：每行三个整数 val left right，分别表示：
- 当前结点的值
- 左孩子的编号
- 右孩子的编号
  其中 -1 表示没有对应的孩子。
结点编号从 1 开始，第 1 个结点为根结点。

输出格式

输出二叉树的层序遍历结果，数字之间用空格分隔。

输入样例

5
2 3
4 -1
-1 5
-1 -1
-1 -1

输出样例

1 2 3 4 5

解：

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int n;
vector<int> l,r,final,val;

void input(){
    l.push_back(-1);
    r.push_back(-1);
    val.push_back(-1);
    cin>>n;
    for(int i=1;i<=n;i++){
        int temp,L,R;
        cin>>temp>>L>>R;
        val.push_back(temp);
        l.push_back(L);
        r.push_back(R);
    }
}

void BFS(int start){
    queue<int> q;
    q.push(start);
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        final.push_back(val[cur]);
        if(l[cur]!=-1){
            q.push(l[cur]);
        }
        if(r[cur]!=-1){
            q.push(r[cur]);
        }
    }
}

int main(){
    input();
    BFS(1);
    for(int i=0;i<final.size();i++){
        if(i>0) cout<<" ";
        cout<<final[i];
    }
    return 0;
}

二叉搜索树的基本操作

题目描述

请你实现一个二叉搜索树（BST），支持以下四种操作：

建立：给定一系列整数，依次插入到 BST 中，建立一棵二叉搜索树。
检索：查询某个值是否存在于 BST 中。
插入：将一个新的值插入 BST。
删除：删除 BST 中的某个值（若不存在则忽略）。

请在所有操作完成后，输出这棵 BST 的中序遍历结果。

输入格式

第一行：两个整数 n m，分别表示初始插入的元素数量和操作数量 (1 ≤ n, m ≤ 1000)。
第二行：n 个互不相同的整数，表示依次插入 BST 的结点值。
接下来 m 行，每行表示一次操作，格式如下：
- Q x：检索值 x 是否在 BST 中（输出 Found 或 Not Found）。
- I x：向 BST 中插入值 x（若已存在则忽略）。
- D x：从 BST 中删除值 x（若不存在则忽略）。

输出格式

对于每个检索操作 Q，输出一行 Found 或 Not Found。
最后一行输出 BST 的中序遍历结果。

输入样例

输出样例

Found
Not Found
Not Found
1 3 4 5 6

解：

#include<iostream>
#include<vector>

using namespace std;

struct Node{
    int v;
    Node* l;
    Node* r;
    Node(int x):v(x),l(NULL),r(NULL){}
};

Node* insertBST(Node* root,int x){
    if(root==NULL) return new Node(x);
    if(x<root->v) root->l=insertBST(root->l,x);
    else if(x>root->v) root->r=insertBST(root->r,x);
    return root;
}

bool searchBST(Node* root,int x){
    if(root==NULL) return false;
    if(root->v==x) return true;
    else if(x<root->v) return searchBST(root->l,x);
    else return searchBST(root->r, x);
}

Node* findmin(Node* root){
    while(root->l!=NULL) root=root->l;
    return root;
}

Node* deleteBST(Node* root,int x){
    if(root==NULL) return NULL;
    if(x<root->v){
        root->l=deleteBST(root->l,x);
    }
    else if(x>root->v){
        root->r=deleteBST(root->r,x);
    }
    else{
        if(root->l==NULL&&root->r==NULL){
            delete root;
            return NULL;
        }
        else if(root->l==NULL){
            Node* tmp=root->r;
            delete root;
            return tmp;
        }
        else if(root->r==NULL){
            Node* tmp=root->l;
            delete root;
            return tmp;
        }
        else{
            Node* successor=findmin(root->r);
            root->v=successor->v;//用它右子树的最小结点（中序后继）替代它
            root->r=deleteBST(root->r,successor->v);//再在右子树中删除这个后继结点
        }
    }
    return root;
}

void inorder(Node* root,vector<int>& result){
    if(root==NULL) return;
    inorder(root->l,result);
    result.push_back(root->v);
    inorder(root->r,result);
}

int main(){
    int n,m;
    cin>>n>>m;
    Node* root=NULL;
    for(int i=0;i<n;i++){
        int x;
        cin>>x;
        root=insertBST(root,x);
    }
    for(int i=0;i<m;i++){
        char op;
        int x;
        cin>>op>>x;
        if(op=='Q'){
            if(searchBST(root,x)) cout<<"Found\n";
            else cout<<"Not Found\n";
        }
        else if(op=='I'){
            root=insertBST(root,x);
        }
        else if(op=='D'){
            root=deleteBST(root,x);
        }
    }
    vector<int> result;
    inorder(root,result);
    for(int i=0;i<result.size();i++){
        if(i) cout<<" ";
        cout<<result[i];
    }
    cout<<"\n";
    return 0;
}

最小堆的基本操作

题目描述

请你实现一个 最小堆（Min-Heap），支持以下操作：

建立：根据输入的初始元素序列，建立最小堆。
检索：查询某个值是否存在于堆中。
插入：将一个新的元素插入堆中，并保持堆的性质。
删除：删除堆中的某个元素（若不存在则忽略），并保持堆的性质。
SiftUp：对某个下标位置的元素执行上滤操作。
SiftDown：对某个下标位置的元素执行下滤操作。

最后输出堆的层序遍历（即数组存储顺序）。

输入格式

第一行：两个整数 n m，分别表示初始元素个数和操作次数 (1 ≤ n, m ≤ 1000)。
第二行：n 个整数，表示初始元素。
接下来 m 行，每行表示一次操作，格式如下：
- Q x：检索值 x 是否在堆中（输出 Found 或 Not Found）。
- I x：将值 x 插入堆中。
- D x：删除堆中的值 x（若不存在则忽略）。
- U k：对下标为 k 的结点执行 SiftUp（1 ≤ k ≤ 当前堆大小）。
- DWN k：对下标为 k 的结点执行 SiftDown（1 ≤ k ≤ 当前堆大小）。

输出格式

对于每个检索操作 Q，输出一行 Found 或 Not Found。
所有操作执行完毕后，输出一行堆的层序遍历（即内部数组顺序）。

输入样例

5 6
4 5 1 3 2
Q 3
I 0
Q 0
D 5
U 3
DWN 2

输出样例

Found
Found
0 2 1 3 4

解：

#include<iostream>
#include<vector>

using namespace std;

struct MinHeap{
    vector<int> h;
    MinHeap(){h.push_back(0);}
    int size(){return h.size()-1;}
    void swapNode(int i,int j){
        int tmp=h[i];
        h[i]=h[j];
        h[j]=tmp;
    }
    void siftUp(int k){
        while(k>1&&h[k]<h[k/2]){
            swapNode(k,k/2);
            k/=2;
        }
    }
    void siftDown(int k){
        int n=size();
        while(2*k<=n){
            int child=2*k;
            if(child+1<=n&&h[child+1]<h[child]) child++;
            if(h[k]<=h[child]) break;
            swapNode(k,child);
            k=child;
        }
    }
    void insert(int x){
        h.push_back(x);
        siftUp(size());
    }
    void build(vector<int>& arr){
        h={0};
        for(int x:arr) h.push_back(x);
        for(int i=size()/2;i>=1;i--){
            siftDown(i);
        }
    }
    bool search(int x){
        for(int i=1;i<=size();i++){
            if(h[i]==x) return true;
        }
        return false;
    }
    void remove(int x){
        int n=size();
        int idx=-1;
        for(int i=1;i<=n;i++){
            if(h[i]==x){
                idx=i;
                break;
            }
        }
        if(idx==-1) return;
        h[idx]=h[n];
        h.pop_back();
        if(idx<=size()){
            siftUp(idx);
            siftDown(idx);
        }
    }
    void printHeap(){
        for(int i=1;i<=size();i++){
            if(i>1) cout<<" ";
            cout<<h[i];
        }
        cout<<"\n";
    }
};

int main(){
    int n,m;
    cin>>n>>m;
    vector<int> arr(n);
    for(int i=0;i<n;i++) cin>>arr[i];
    MinHeap heap;
    heap.build(arr);
    for (int i = 0; i < m; i++) {
        string op;
        int x;
        cin >> op >> x;
        if (op == "Q") { 
            if (heap.search(x)) cout << "Found\n";
            else cout << "Not Found\n";
        } 
        else if (op == "I") { 
            heap.insert(x);
        } 
        else if (op == "D") { 
            heap.remove(x);
        } 
        else if (op == "U") { 
            if (x >= 1 && x <= heap.size()) heap.siftUp(x);
        } 
        else if (op == "DWN") { 
            if (x >= 1 && x <= heap.size()) heap.siftDown(x);
        }
    }
    heap.printHeap();
    return 0;
}

用堆实现优先队列

题目描述

请你实现一个 优先队列（priority_queue），支持以下操作：

插入一个元素 x。
删除队列中的最大元素。
查询当前队列中的最大元素。

你需要用堆（优先队列）来实现这些操作。

输入格式

第一行输入一个整数 Q，代表操作的次数。

接下来 Q 行，每行是以下操作之一：

1 x 表示插入元素 x。
2 表示删除队列中的最大元素（如果队列为空，则忽略）。
3 表示输出当前队列中的最大元素（如果队列为空，则输出 Empty）。

输出格式

对于每次操作 3，输出对应的最大元素或 Empty。

输入样例

输出样例

5
3
3
Empty

解：

#include<iostream>
#include<vector>

using namespace std;

class PriorityQueue{
private:
	vector<int> heap;

	void siftUp(int x){
		while(x>0){
			int parent=(x-1)/2;
			if(heap[x]>heap[parent]){
				swap(heap[x],heap[parent]);
				x=parent;
			}
			else{
				break;
			}
		}
	}

	void siftDown(int x){
		int n=heap.size();
		while(x<n){
			int l=2*x+1;
			int r=2*x+2;
			int largest=x;

			if(l<n&&heap[l]>heap[largest])
				largest=l;
			if(r<n&&heap[r]>heap[largest])
				largest=r;
			if(largest!=x){
				swap(heap[x],heap[largest]);
				x=largest;
			}
			else{
				break;
			}
		}
	}

public:
	void push(int x){
		heap.push_back(x);
		siftUp(heap.size()-1);
	}

	void pop(){
		if(heap.empty()) return;
		swap(heap[0],heap.back());
		heap.pop_back();
		if(!heap.empty()) siftDown(0);
	}

	int top(){
		return heap.empty()? -1:heap[0];
	}

	bool empty(){
		return heap.empty();
	}
};

int main(){
	PriorityQueue pq;
	int Q;
	cin>>Q;
	while(Q--){
		int op,x;
		cin>>op;
		switch(op){
			case 1:
				cin>>x;
				pq.push(x);
				break;
			case 2:
				pq.pop();
				break;
			case 3:
				if(pq.empty()){
					cout<<"Empty"<<endl;
				}
				else{
					cout<<pq.top()<<endl;
				}
				break;
		}
	}
	return 0;
}

二·经典例题

B3642 二叉树的遍历

题目描述

有一个 n(n<=10^6) 个结点的二叉树。给出每个结点的两个子结点编号（均不超过 n），建立一棵二叉树（根节点的编号为 1），如果是叶子结点，则输入 0 0。

建好树这棵二叉树之后，依次求出它的前序、中序、后序列遍历。

输入格式

第一行一个整数 n，表示结点数。

之后 n 行，第 i 行两个整数 l、r，分别表示结点 i 的左右子结点编号。若 l=0 则表示无左子结点，r=0 同理。

输出格式

输出三行，每行 n 个数字，用空格隔开。

第一行是这个二叉树的前序遍历。

第二行是这个二叉树的中序遍历。

第三行是这个二叉树的后序遍历。

输入输出样例 #1

输入 #1

输出 #1

2 4 3 7 6 5
3 2 1 6 5 7
4 2 5 6 7 1

解：

a.首先进行前期处理

#include<iostream>
#include<vector>

using namespace std;

int main(){
    int n;
    vector<int> l;
    vector<int> r;
    cin >> n;
    l.push_back(0);
    r.push_back(0);
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        l.push_back(x);
        r.push_back(y);
    }

    return 0;
}

b.遍历策略

递归搜索

DFS

void DFS_pre(int node,const vector<int>& l,const vector<int>& r){
  if(node==0) return;
  cout<<node<<" ";
  DFS_pre(l[node],l,r);
  DFS_pre(r[node],l,r);
}

void DFS_in(int node,const vector<int>& l,const vector<int>& r){
  if(node==0) return;
  DFS_in(l[node],l,r);
  cout<<node<<" ";
  DFS_in(r[node],l,r);
}

void DFS_post(int node,const vector<int>& l,vector<int>& r){
  if(node==0) return;
  DFS_post(l[node],l,r);
  DFS_post(r[node],l,r);
  cout<<node<<" ";
}

非递归（用栈模拟）

void WR_pre(int node,const vector<int>& l, const vector<int>& r){
    stack<int> s;
    s.push(node);
    while(!s.empty()) {
        int current = s.top();
        s.pop();
        cout << current << " ";
        if (r[current] != 0) {
            s.push(r[current]);
        }
        if (l[current] != 0) {
            s.push(l[current]);
        }
    }
}

void WR_in(int node,const vector<int>& l, const vector<int>& r) {
    stack<int> s;
    int current = node;
    while (current != 0 || !s.empty()) {
        while (current != 0) {
            s.push(current);
            current = l[current];
        }
        current = s.top();
        s.pop();
        cout << current << " ";
        current = r[current];
    }
}

void WR_post(int node,const vector<int>& l, const vector<int>& r) {
    stack<int> s;
    int current = node;
    int lastVisited = 0;
    while(current|| !s.empty()) {
        while(current) {
            s.push(current);
            current = l[current];
        }
        current = s.top();
        if(r[current] == 0 || r[current] == lastVisited) {
            cout << current << " ";
            s.pop();
            lastVisited = current; 
            current = 0; 
        } 
        else {
            current = r[current];
        }
    }   
}

0510 由中根序列和后根序列重建二叉树

题目描述

我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。反过来，如果给定二叉树的中根序列和后根序列，或者给定中根序列和前根序列，可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。

输入格式

两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。

输出格式

一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。

输入输出样例 #1

输入 #1

9 5 32 67
9 32 67 5

输出 #1

5 9 67 32

解：

法一：

a.全局初始化

#include<iostream>
#include<vector>
#include<sstream>
#include<string>

using namespace std;

vector<int> in;
vector<int> post;
vector<int> pre;
vector<int> index;
vector<int> l;
vector<int> r;

int search(int x) {
	for (int i = 0; i < index.size(); i++) {
		if (index[i] == x) return i;
	}
	return -1;
}

int main() {
    input();
	build(0, in.size() - 1, 0, post.size() - 1);
	for (int i = 0; i < pre.size(); i++) {
		if (i > 0) cout << " ";
		cout << pre[i];
	}
	cout << endl;
	return 0;
}

b.输入处理

void input() {
	string line;
	getline(cin, line);
	stringstream ss(line);
	int num;
	while (ss >> num) {
		in.push_back(num);
	}
	getline(cin, line);
	ss.clear();
	ss.str(line);
	while (ss >> num) {
		post.push_back(num);
		index.push_back(num);
	}
}

c.重建与前序遍历（惊艳🤩）

void build(int in_start,int in_end,int post_start,int post_end) {
	if (in_start > in_end || post_start > post_end) return;
	int root_val = post[post_end];
	pre.push_back(root_val);
	int post_in = -1;
	for(int i = in_start; i <= in_end; i++) {
		if (in[i] == root_val) {
			post_in = i;
			break;
		}
	}
	int left_size = post_in - in_start;
	build(in_start, post_in - 1, post_start, post_start + left_size - 1);
	build(post_in + 1, in_end, post_start + left_size, post_end - 1);
}

法二：

#include <iostream>
#include <vector>
#include <unordered_map>
#include <sstream>
using namespace std;

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

TreeNode* buildTreeHelper(vector<int>& inorder, vector<int>& postorder, int inStart, int inEnd, int postStart, int postEnd, unordered_map<int, int>& inMap) {
    if (inStart > inEnd || postStart > postEnd) 
        return nullptr;

    int rootVal = postorder[postEnd];
    TreeNode* root = new TreeNode(rootVal);

    int pos = inMap[rootVal];
    int leftSize = pos - inStart;

    root->left = buildTreeHelper(inorder, postorder, inStart, pos - 1, postStart, postStart + leftSize - 1, inMap);
    root->right = buildTreeHelper(inorder, postorder, pos + 1, inEnd, postStart + leftSize, postEnd - 1, inMap);

    return root;
}

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if (inorder.empty() || postorder.empty()) 
        return nullptr;

    unordered_map<int, int> inMap;
    for (int i = 0; i < inorder.size(); i++) {
        inMap[inorder[i]] = i;
    }
    return buildTreeHelper(inorder, postorder, 0, inorder.size() - 1, 0, postorder.size() - 1, inMap);
}

void preorderTraversal(TreeNode* root, vector<int>& result) {
    if (root == nullptr) 
        return;
    result.push_back(root->val);
    preorderTraversal(root->left, result);
    preorderTraversal(root->right, result);
}

int main() {
    string inLine, postLine;
    getline(cin, inLine);
    getline(cin, postLine);

    vector<int> inorder, postorder;
    stringstream ssIn(inLine), ssPost(postLine);
    int num;

    while (ssIn >> num) {
        inorder.push_back(num);
    }
    while (ssPost >> num) {
        postorder.push_back(num);
    }

    TreeNode* root = buildTree(inorder, postorder);
    vector<int> preResult;
    preorderTraversal(root, preResult);

    for (int i = 0; i < preResult.size(); i++) {
        if (i > 0) 
            cout << " ";
        cout << preResult[i];
    }
    cout << endl;
    return 0;
}

0513 Huffman编码树

题目描述

构造一个具有n个外部节点的扩充二叉树，每个外部节点\(K_i\)有一个\(W_i\)对应，作为该外部节点的权。使得这个扩充二叉树的叶节点带权外部路径长度总和最小：

\[\min \left( W_1 \cdot L_1 + W_2 \cdot L_2 + W_3 \cdot L_3 + \cdots + W_n \cdot L_n \right)\]

\(W_i\):每个节点的权值。

\(L_i\):根节点到第i个外部叶子节点的距离。

编程计算最小外部路径长度总和。

输入格式

第一行输入一个整数t，代表测试数据的组数。对于每组测试数据，第一行输入一个整数n，外部节点的个数。第二行输入n个整数，代表各个外部节点的权值。 2<=N<=100

输出格式

输出最小外部路径长度总和。

输入输出样例 #1

输入 #1

输出 #1

9
17

解：

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		priority_queue<int,vector<int>,greater<int>> minHeap;
		for(int i=0;i<n;i++){
			int w;
			cin>>w;
			minHeap.push(w);
		}
		int totalWPL=0;
		while(minHeap.size()>1){
			int a=minHeap.top();
			minHeap.pop();
			int b=minHeap.top();
			minHeap.pop();
			int sum=a+b;
			totalWPL+=sum;
			minHeap.push(sum);
		}
		cout<<totalWPL<<endl;
	}
	return 0;
}

【评】这里有个定理：哈夫曼树中最小带权路径长度（WPL）等于所有非叶子节点权值之和（数学归纳法易证），又等于每次合并后所得新权值之和

Share on

X Facebook LinkedIn Bluesky

Qiyu Zhang

二叉树的 BFS 遍历

题目描述

输入格式

输出格式

输入样例

输出样例

二叉搜索树的基本操作

题目描述

输入格式

输出格式

输入样例

输出样例

最小堆的基本操作

题目描述

输入格式

输出格式

输入样例

输出样例

用堆实现优先队列

题目描述

输入格式

输出格式

输入样例

输出样例

B3642 二叉树的遍历

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

0510 由中根序列和后根序列重建二叉树

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

0513 Huffman编码树

题目描述

输入格式

输出格式

输入输出样例 #1

输入 #1

输出 #1

Share on

Comments

You May Also Enjoy

Music Recommendation:Merry Go Round of Life

Music Recommendation:Hey Jude

Test

Practice:Tree