.
.
: 3
-322
: . .
2016
.
, BST - , . .
(Binary Search Tree BST) , , , .
BST - :
( ),
( ),
,
,
,
,
, , ,
, .
BST :
.
(, ) .
: t → L t → R t .
: ( = ).
3.
, , .
.
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
: K T
: K
: K T
|
|
|
: false, , true,
: T K
: K
:
: K
: T K
:
: K
: K
: c K
: true, , false,
: K
:
:
:
:
:
t L R
:
:
: t-L-R
:
: t-L-R
:
:
:
:
:
4. Tree:
Tree() //
~ Tree() //
int nodeCount() //
void clear() //
bool isClean() //
bool add(const K &key, const T &elem) //
T search(T key) //
bool removeByKey(K key) //
void print() //
void tLR() // t-L-R
int getLength() //
. -, .
classes.h
#ifndef __CLASSES_H__
#define __CLASSES_H__
template <class K, class T>
class Tree {
protected:
class Node {
public:
K key;
T item;
Node *left;
Node *right;
Node(K k, T i, Node *s = NULL, Node *b = NULL){
key = k;
item = i;
left = s;
right = b;
}
};
Node *root;
public:
K tmpKey;
T tmpItem;
int length;
Tree(){
root = NULL;
length = 0;
}
~Tree(){
deleteSubtree(root);
}
int nodeCount(){
return nodeCount_helper(root);
};
void clear(){
deleteSubtree(root);
root = NULL;
};
bool isClean(){
return (root)? true: false;
}
bool add(const K &key, const T &elem){
return add_helper(root, key, elem);
}
T search(K search){
return search_helper(root, search);
}
bool removeByKey(K key){
bool deleted = false;
removeByKey_helper(root, key, deleted);
return deleted;
};
void print(){
print_helper(root, 0);
}
void tLR(){
return tLR_helper(root);
}
int getLength(){
return getLength_helper(root, 1);
}
private:
int nodeCount_helper(Node *node);
bool add_helper(Node *&node, const K &key, const T &elem);
|
|
|
T search_helper(Node *node, K search);
Node* removeByKey_helper(Node *&root, K key, bool &deleted);
void print_helper(Node *node, int spaces);
void tLR_helper(Node *node);
int getLength_helper(Node *node, int i);
void deleteSubtree(Node *node);
Node* findMin(Node *root);
};
template <class K, class T>
typename Tree<K, T>::Node* Tree<K, T>::findMin(Node* root){
while(root->left!= NULL) root = root->left;
return root;
};
template <class K, class T>
typename Tree<K, T>::Node* Tree<K, T>::removeByKey_helper(Node *&root, K data, bool &deleted){
if(root == NULL){
return root;
} else if(data < root->key){
root->left = removeByKey_helper(root->left, data, deleted);
} else if (data > root->key){
root->right = removeByKey_helper(root->right, data, deleted);
} else {
if(root->left == NULL && root->right == NULL) {
delete root;
root = NULL;
deleted = true;
} else if(root->left == NULL && root->right!= NULL) {
Node *temp = root;
root = root->right;
delete temp;
deleted = true;
} else if(root->right == NULL && root->left!= NULL) {
Node *temp = root;
root = root->left;
delete temp;
deleted = true;
} else {
Node *temp;
if(root->right)
temp = findMin(root->right);
else
temp = root->left;
root->key = temp->key;
root->item = temp->item;
root->right = removeByKey_helper(root->right, temp->key, deleted);
}
}
return root;
};
template <class K, class T>
int Tree<K, T>::getLength_helper(Node *node, int i){
int local = 0;
if(!node){
return 0;
}
if(node->left && node->right)
local += i;
local += getLength_helper(node->left, i+1) + getLength_helper(node->right, i+1);
return local;
};
template <class K, class T>
void Tree<K, T>::tLR_helper(Node *node){
if(node){
cout << node->key << " ";
tLR_helper(node->left);
tLR_helper(node->right);
}
};
template <class K, class T>
int Tree<K, T>::nodeCount_helper(Node *node){
int cnt = 0;
if(node){
cnt += nodeCount_helper(node->right);
cnt += nodeCount_helper(node->left);
cnt++;
}
return cnt;
};
template <class K, class T>
void Tree<K, T>::deleteSubtree(Node *node){
if(node){
deleteSubtree(node->left);
deleteSubtree(node->right);
delete node;
}
};
template <class K, class T>
bool Tree<K, T>::add_helper(Node *&node, const K &key, const T &item){
if(node == NULL){
node = new Node(key, item);
return true;
} else if(key == node->key){
return false;
} else if(key < node->key){
add_helper(node->left, key, item);
} else {
add_helper(node->right, key, item);
}
};
template <class K, class T>
T Tree<K, T>::search_helper(Node *node, K search){
if (node == NULL){
T val;
return val;
}
if(node->key == search){
return node->item;
}
if(search <= node->key){
if(node->left!= NULL)
return search_helper(node->left, search);
} else {
if(node->right!= NULL)
return search_helper(node->right, search);
}
T val;
return val;
};
template <class K, class T>
void Tree<K, T>::print_helper(Node *node, int spaces){
while (node!= NULL){
if(node->right)
print_helper(node->right, spaces + 5);
for (int i = 1; i < spaces; ++i)
std::cout << ' ';
//std::cout << "(" << node->key << ")=" << node->item << std::endl;
std::cout << "(" << node->key << ")" << std::endl;
|
|
|
node = node->left;
spaces += 5;
}
};
#endif // __CLASSES_H__
