浙大数据结构-树-04-树6 Complete Binary Search Tree (30 分)

博主： lnnn
发布时间：2022 年 03 月 29 日
171 次浏览
暂无评论
3349字数
分类：算法 C++ 学习笔记

## 题目

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

* The left subtree of a node contains only nodes with keys less than the node's key.
* The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
* Both the left and right subtrees must also be binary search trees.A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right.
  
  Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.
  
  ### Input Specification:
  
  Each input file contains one test case. For each case, the first line contains a positive integer **N** (**≤****1000**). Then **N** distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.
  
  ### Output Specification:
  
  For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.
  
  ### Sample Input:
  
  ```in
  10
  1 2 3 4 5 6 7 8 9 0
  ```
  
  ### Sample Output:
  
  ```out
  6 3 8 1 5 7 9 0 2 4
  ```
  
  ## 题解

首先根据将原始数据排序

然后使用cbst函数将根节点依次入队

根据这个队中的序列可以构建出题目要求的树

然后再层序遍历

```
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

const int N = 1010;
int n;
int q[N];
queue<int>* pQueue = new queue<int>;

template<class T>
class node{
public:
    node(T ele){
        element = ele;
        pLeft = NULL;
        pRight = NULL;
    }
public:
    T element;
    node* pLeft;
    node* pRight;
};
    
template<class T>
class BTree{
public:
    BTree(){
        pRoot = NULL;
    }
    
    void Insert(T element){
        pRoot = insert(pRoot, element);
    }
    
    void LevelFirstTraversal(){
        int firstFlag = 1;
        
        node<T>* pTmp = NULL;
        
        queue<node<T>*>* pQueue = new queue<node<T>*>;
        pQueue->push(pRoot);
        
        while(!pQueue->empty()){
            pTmp = pQueue->front();
            pQueue->pop();
            if(firstFlag){
                cout << pTmp->element;
                firstFlag = 0;
            }else{
                cout << " " << pTmp->element;
            }
            
            if(pTmp->pLeft){
                pQueue->push(pTmp->pLeft);
            }
            if(pTmp->pRight){
                pQueue->push(pTmp->pRight);
            }
        }
        
    }
    
private:
    node<T>* insert(node<T>* pTmpRoot, T element){
        if(!pTmpRoot){
            node<T>* pNewNode = new node<T>(element);
            return pNewNode; 
        }
        
        if(element > pTmpRoot->element){
            pTmpRoot->pRight = insert(pTmpRoot->pRight, element);
        }else if(element < pTmpRoot->element){
            pTmpRoot->pLeft = insert(pTmpRoot->pLeft, element);
        }
        
        return pTmpRoot;
    }
    
private:
    node<T>* pRoot;
};

void cbst(const int q[], int l, int r){
    if(r == l){
        //cout << q[l] << " ";
        pQueue->push(q[l]);
        return;
    }
    
    int i = l, j = r;
    int sl = 0, sr = 0;
    int all_num = r - l + 1;
    int fulled_level = log(all_num + 1)/log(2);
    int fulled_num = pow(2, fulled_level) - 1;
    int half_fulled_num = pow(2, fulled_level - 1) - 1;
    int scatte_gate = pow(2, fulled_level - 1);
    int scatte_num = all_num - fulled_num;

if(scatte_num <= scatte_gate){
        sl = scatte_num;
        sr = 0;
    }else{
        sl = scatte_gate;
        sr = scatte_num  - scatte_gate;
    }
    
    int l_num = half_fulled_num + sl;
    int r_num = all_num - l_num - 1;
    
    i = l + l_num + 1 > r ? r : l + l_num + 1;
    //cout << q[l + l_num] << " ";
    pQueue->push(q[l + l_num]);
    //cout << l << "->" << l + l_num - 1 << endl;
    
    cbst(q, l, l + l_num - 1);
    
    if(r_num){
        //cout << i << "->" << r << endl;
        cbst(q, i, r);
    }

}

int main(){
    int inputTmp;
    BTree<int>* pTree = new BTree<int>;
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> q[i];
    }
    sort(q, q + n);

cbst(q, 0, n - 1);
        
    while(!pQueue->empty()){
        inputTmp = pQueue->front();
        pQueue->pop();
        pTree->Insert(inputTmp);
    }
    pTree->LevelFirstTraversal();
    
    return 0;
}
```

最后修改：2022 年 03 月 29 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

浙大数据结构-树-04-树6 Complete Binary Search Tree (30 分)

lnnn • 2022 年 03 月 29 日

## 题目

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:

首先根据将原始数据排序

然后使用cbst函数将根节点依次入队

根据这个队中的序列可以构建出题目要求的树

然后再层序遍历

```
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>

using namespace std;

const int N = 1010;
int n;
int q[N];
queue<int>* pQueue = new queue<int>;

}

int main(){
    int inputTmp;
    BTree<int>* pTree = new BTree<int>;
    
    cin >> n;
    
    for(int i = 0; i < n; i++){
        cin >> q[i];
    }
    sort(q, q + n);

浙大数据结构-树-04-树6 Complete Binary Search Tree (30 分)

发表评论取消回复

LG gram 14Z970 Hackintosh

浙大数据结构-线性表-Reversing Linked List

第一把Gasket——zuoer68（ciy68改）

腹灵870单模套件——驱动遇坑

闲来无事

闲来无事

浙大数据结构-线性表-Reversing Linked List

第一把Gasket——zuoer68（ciy68改）

浙大数据结构-二叉树-Tree Traversals Again

837. 连通块中点的数量 (ACWing)

浙大数据结构-树-04-树6 Complete Binary Search Tree (30 分)

发表评论 取消回复

浙大数据结构-树-04-树6 Complete Binary Search Tree (30 分)

发表评论取消回复