需要幫助二叉樹程序（非二叉搜索樹）

我想實現一個二叉樹（不是二叉搜索樹）。它將主要是一個由插入/刪除/搜索&清除程序組成的類模板。保存在節點中的數據可以是任何東西。類似下面：需要幫助二叉樹程序（非二叉搜索樹）

template<class T> 
class BinaryTree 
{ 
public: 
    BinaryTree(int size); 
    ~BinaryTree(); 
    virtual bool insert(T data); 
    virtual bool remove(T data); 
    virtual void clear(); 
    virtual bool search(T data); 
    virtual void display(std::string str, ETravType type); 
    virtual unsigned int getSize(); 
    //friend void swapWithLastNode(Node *root, Node **nodeToRemove); 
protected: 
    virtual void inorder(Node<T>* root); 
    virtual void preorder(Node<T>* root); 
    virtual void postorder(Node<T>* root); 
    virtual void removeAll(Node<T>* root); 
    Node<T>* root; 
    int max; 
    unsigned int curSize; 
};

我需要在算法的一些幫助，最好迭代（要避免重複，由於堆棧大小限制），用於插入，搜索&刪除：

插入：如何確保樹不會左右偏斜？
刪除：當節點同時擁有兩個子節點時，刪除的最佳方式是什麼（例如：在BST中，用inorder後繼替換）。
搜索：有沒有有效的方法來防止O（n）搜索？

有資源的網絡的BST程序（主要是遞歸）上的豐富，但沒有二叉樹（或至少我無法找到任何東西）。因此想到在這裏發佈它。

來源

2016-11-02 vinit

您對插入的問題，並刪除似乎表明對我說，你不關心節點的樹，並在這一點上我要問你爲什麼即使使用二叉樹而不是位置只是一個單鏈表？ – PeterT

有一個真正的理由贊成BST通過英國電信。

BST是log(N)用於插入，刪除和搜索，而BT可能以O(N)爲代價以樹遍歷完成。

插入：如何確保樹不會左右偏斜？

恐怕會不使任何差樹的整體性能。如果你仍然想這樣做，請了解self-balancing tree。
刪除：當節點同時擁有兩個子節點時，刪除的最佳方式是什麼（例如：在BST中，用inorder後繼替換）。

對於刪除，只需選擇該樹的任意葉節點並替換該位置。二叉樹沒有模式，所以選擇隨機節點不會產生任何差異。所以，在拾取葉節點時沒有問題。
搜索：有沒有任何有效的方法來防止O（n）搜索？

不，沒有更好的方法來阻止O(n)搜索。您需要遍歷整個樹，BT中沒有節點的模式/順序可幫助您高效地導航。

來源

2016-11-02 07:44:08

需要幫助二叉樹程序（非二叉搜索樹）

回答

相關問題