Дърво

Дърво

---

страницата се нуждае от дописване/преглеждане

---

В тази статия ще обясняваме за дървета.

Тук трябваше да обясняваме какво е двоично дърво за търсене…
Но, в крайна сметка, добре написаният код говори сам за себе си.

C++ Имплементация

Покажи

/*
Това е реализация на двоично дърво за търсене със шаблони.
Дървото има един шаблонен аргумент, който представлява типа на данните в него.
Гарантирано е, че скоростта на търсенето в дървото ще бъде пропорционална на неговата дълбочина.
Дървото не е балансирано, така че дълбочината може потенциално да стане пропорционална на размера му.
Но, в почти всички случаи се гарантира логаритмична скорост на търсене.
 
Copyleft 2009 fmi.wikidot.com
Unless stated otherwise Content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License
*/
#include <iostream>
 
using std::cout;
using std::endl;
 
/*
Tова е структурата, която ще отговаря на един връх в дървото.
Върхът трябва да има данни **data**, както и указатели към ляво и дясно поддърво.
*/
template <typename T>
struct TreeNode {
    T data;
    TreeNode<T> *left, *right;
    TreeNode(const T &_data, TreeNode<T> *_left = NULL, TreeNode<T> *_right = NULL)
    : data(_data), left(_left), right(_right) {}
};
 
/*
Самият клас за дървото.
Поддържат се операции за вадене и добавяне на стойност, както и за търсене на елемент.
*/
template <typename T>
class Tree {
private:
    enum TraversalType{PREORDER, INORDER, POSTORDER};
    TreeNode<T> *root;
 
public:
    /*
    Конструкторът по подразбиране всъщност не прави много...
    */
    Tree() : root(NULL) {}
 
    /*
    Деструкторът извиква функция, която рекурсивно да изтрие върховете на дървото.
    */
    ~Tree() {
        _delete(root);
    }
 
    /*
    Търсене на стойноста val в дървото.
    */
    const TreeNode<T> *find(const T &val) const {
        return _find(root, val);
    }
 
    /*
    Добавяне на стойност **val** в дървото.
    */
    bool add(const T &val) {
        TreeNode <T> *&tmp = const_cast<TreeNode <T> *&>(_find(root, val));
        if (tmp != NULL) return false; // Вече е в дървото
        tmp = new TreeNode<T> (val); // Запиши новия елемент
    }
 
    /*
    Триене на стойност **val** в дървото.
    */
    bool remove(const T &val) {
        TreeNode <T> *&tmp = const_cast<TreeNode<T> *&>(_find(root, val));
        if (tmp == NULL) return false; // Няма го в дървото
        _remove(tmp);
    }
 
    /*
    Следващите три метода рекурсивно обхождат и отпечатват дървото.
    M е означение за корена(middle), L - за лявото поддърво, а R - за дясното.
    */
 
    /*
    Обхождане на дърво: **LMR**
    */
    void inOrderTraversal() const {
        _traverse(root, INORDER); cout << endl;
    }
    /*
    Обхождане на дърво: **MLR**
    */
    void preOrderTraversal() const {
        _traverse(root, PREORDER); cout << endl;
    }
    /*
    Обхождане на дърво: **LRM**
    */
    void postOrderTraversal() const {
        _traverse(root, POSTORDER); cout << endl;
    }
 
private:
    /*
    Помощни функции често се отбелязват с _ пред името.
    В някои по-развити езици, това е част от синтаксиса, тук е просто по конвенция.
    */
 
    /*
    Трие всички елементи на дървото. Вика се от деструктора.
    */
    void _delete(TreeNode<T> *r) {
        if (r == NULL) return;
        _delete(r->left);
        _delete(r->right);
        delete r;
    }
 
    /*
    Търси елемент search в дървото.';
    */
    TreeNode<T> * const &_find(TreeNode<T> * const &r, const T &val) const {
        if (r == NULL || r->data == val)
            return r;
        if (val < r->data)
            return _find(r->left, val);
        else
            return _find(r->right, val);
    }
 
    /*
    Трие един елемент от дървото. Функцията се вика от **remove**
    Приема се псевдоним към указател към връх, който трябва да бъде изтрит
    (т.е. няма проверка дали такъв връх съществува).
    Алгоритъмът е следният:
    Ако върхът е листо(няма деца) - спокойно можем да го изтрием.
    r = NULL занулява указателя на родителя на върха(или root указателя).
    В противен случай, върхът за триене се премества едно ниво по-надолу
    (бива разместен с някой от наследниците си) и програмата опитва пак да го изтрие.
    По този начин все някога ще се стигне до ситуация, в която върхът няма наследници.
 
    Съществува и по-качествена реализация, намираща inorder predcessor/successor,
    но нейният алгоритъм е по-сложен.
    */
    void _remove(TreeNode<T> *&r) {
        if (r->left == NULL && r->right == NULL) {
            delete r;
            r = NULL;
        }
 
        if (r->left) {
            // Разменя местата на дясното дете и корена, и продължава да трие надясно.
            _remove(_rotr(r)->right);
        } else {
            // Разменя местата на лявото дете и корена, и продължава да трие наляво.
            _remove(_rotl(r)->left);
        }
    }
 
    /*
    Размества връх с левия му наследник
    */
    TreeNode<T> *&_rotl(TreeNode<T> *&r) {
        TreeNode<T> *tmp = r->right;
        r->right = tmp->left;
        tmp->left = r;
        return r = tmp;
    }
 
    /*
    Размества връх с десния му наследник
    */
    TreeNode<T> *&_rotr(TreeNode<T> *&r) {
        TreeNode<T> *tmp = r->left;
        r->left = tmp->right;
        tmp->right = r;
        return r = tmp;
    }
 
    /*
    Обхожда дървото, отпечатвайки го.
    Самият вид на обхождането зависи от type и се дава
    чрез някой от методите, които използват _traverse
    preOrderTraversal, inOrderTraversal, postOrderTraversal
    */
    void _traverse(TreeNode<T> *r, TraversalType type) const {
        if (r == NULL) return;
        if (type == PREORDER) cout << r->data << ' ';
        _traverse(r->left, type);
        if (type == INORDER) cout << r->data << ' ';
        _traverse(r->right, type);
        if (type == POSTORDER) cout << r->data << ' ';
    }
 
private: // TODO:
    Tree<T> &operator = (const Tree<T>);
};
 
/*
Пример за използване на класа с дърво от цели числа.
*/
int main() {
    Tree<int> t;
    t.add(5);
    t.add(7);
    t.add(1);
    t.add(10);
    t.add(12);
    t.inOrderTraversal();  // 1 5 7 10 12
    t.preOrderTraversal(); // 5 1 7 10 12
    t.postOrderTraversal(); // 1 12 10 7 5
    return 0;
}

Python

Естествено, тук има включена и реализация на Питон. Няма как.
Тя е взета от Уикипедия

Покажи

class Node:
    def __init__(self, lchild=None, rchild=None, value=-1, data=None):
        self.lchild = lchild
        self.rchild = rchild
        self.value = value
        self.data = data
 
class Bst:
    """Implement Binary Search Tree."""
 
    def __init__(self):
        self.l = []  # Nodes
        self.root = None
 
    def add(self, key, dt):
        """Add a node in tree."""
        if self.root == None:
            self.root = Node(value=key, data=dt)
            self.l.append(self.root)
            return 0
        else:
            self.p = self.root
            while True:
                if self.p.value > key:
                    if self.p.lchild == None:
                        self.p.lchild = Node(value=key, data=dt)
                        return 0  # Success
                    else:
                        self.p = self.p.lchild
                elif self.p.value == key:
                    return -1  # Value already in tree
                else:
                    if self.p.rchild == None:
                        self.p.rchild = Node(value=key, data=dt)
                        return 0  # Success
                    else:
                        self.p = self.p.rchild
        return -2  # Should never happen
 
    def search(self, key):
        """Search Tree for a key and return data; if not found return None."""
        self.p = self.root
        if self.p == None:
            return None
 
        while True:
#            print self.p.value, self.p.data
            if self.p.value > key:
                if self.p.lchild == None:
                    return None  # Not found
                else:
                    self.p = self.p.lchild
            elif self.p.value == key:
                return self.p.data
            else:
                if self.p.rchild == None:
                    return None  # Not found
                else:
                    self.p = self.p.rchild
        return None  # Should never happen
 
    def deleteNode(self, key):
        """Delete node with value == key."""
        if self.root.value == key:
            if self.root.rchild == None:
                if self.root.lchild == None:
                    self.root = None
                else: self.root = self.root.lchild
            else:
                self.root.rchild.lchild = self.root.lchild
                self.root = self.root.rchild
            return 1
        self.p = self.root
        while True:
            if self.p.value > key:
                if self.p.lchild == None:
                    return 0  # Not found anything to delete
                elif self.p.lchild.value == key:
                    self.p.lchild = self.proceed(self.p, self.p.lchild)
                    return 1
                else:
                    self.p = self.p.lchild
            # There's no way for self.p.value to be equal to key:
            if self.p.value < key:
                if self.p.rchild == None:
                    return 0  # Not found anything to delete
                elif self.p.rchild.value == key:
                    self.p.rchild = self.proceed(self.p, self.p.rchild)
                    return 1
                else:
                    self.p = self.p.rchild
        return 0
 
    def proceed(self, parent, delValue):
        if delValue.lchild == None and delValue.rchild == None:
            return None
        elif delValue.rchild == None:
            return delValue.lchild
        else:
            return delValue.rchild
 
    def sort(self):
        self.__traverse__(self.root, mode=1)
 
    def __traverse__(self, v, mode=0):
        """Traverse in: preorder = 0, inorder = 1, postorder = 2."""
        if v == None:
            return
        if mode == 0:
            print (v.value, v.data)
            self.__traverse__(v.lchild)
            self.__traverse__(v.rchild)
        elif mode == 1:
            self.__traverse__(v.lchild, 1)
            print (v.value, v.data)
            self.__traverse__(v.rchild, 1)
        else:
            self.__traverse__(v.lchild, 2)
            self.__traverse__(v.rchild, 2)
            print (v.value, v.data)
 
def main():
    tree = Bst()
    tree.add(4, "test1")
    tree.add(10, "test2")
    tree.add(23, "test3")
    tree.add(1, "test4")
    tree.add(3, "test5")
    tree.add(2, "test6")
    tree.sort()
    print tree.search(3)
    print tree.deleteNode(10)
    print tree.deleteNode(23)
    print tree.deleteNode(4)
    print tree.search(3)
    tree.sort()
if __name__ == "__main__": main()