需要帮助二叉树程序（非二叉搜索树）

我想实现一个二叉树（不是二叉搜索树）。它将主要是一个由插入/删除/搜索&清除程序组成的类模板。保存在节点中的数据可以是任何东西。类似下面：需要帮助二叉树程序（非二叉搜索树）

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

需要帮助二叉树程序（非二叉搜索树）

回答

相关问题