資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會科學
時裝研究
法律研究將標準二叉搜尋樹轉換成平衡二叉搜尋樹，用C++實現
在本教程中，我們將討論一個將普通二叉搜尋樹轉換為平衡二叉搜尋樹的程式。
為此，我們將提供一棵向左或向右傾斜的二叉搜尋樹。我們的任務是按照一定的規則將其轉換為一顆平衡二叉搜尋樹。
示例
#include <bits/stdc++.h>
using namespace std;
//node structure of tree
struct Node{
int data;
Node* left, *right;
};
//traversing tree and storing node pointers
//in vector nodes
void store_nodes(Node* root, vector<Node*> &nodes){
if (root==NULL)
return;
store_nodes(root->left, nodes);
nodes.push_back(root);
store_nodes(root->right, nodes);
}
//constructing binary tree
Node* construct_tree(vector<Node*> &nodes, int start,
int end){
if (start > end)
return NULL;
//make the middle element to be the root
int mid = (start + end)/2;
Node *root = nodes[mid];
root->left = construct_tree(nodes, start, mid-1);
root->right = construct_tree(nodes, mid+1, end);
return root;
}
//converting an unbalanced BST to a balanced BST
Node* buildTree(Node* root){
//storing nodes of given BST in sorted order
vector<Node *> nodes;
store_nodes(root, nodes);
int n = nodes.size();
return construct_tree(nodes, 0, n-1);
}
//creation of new node
Node* newNode(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
//performing preorder traversal
void preOrder(Node* node){
if (node == NULL)
return;
printf("%d ", node->data);
preOrder(node->left);
preOrder(node->right);
}
int main(){
Node* root = newNode(10);
root->left = newNode(8);
root->left->left = newNode(7);
root->left->left->left = newNode(6);
root->left->left->left->left = newNode(5);
root = buildTree(root);
printf("Preorder traversal of balanced BST : \n");
preOrder(root);
return 0;
}輸出
Preorder traversal of balanced BST : 7 5 6 8 10
更新於：2020 年 1 月 6 日
161 次瀏覽
廣告