需要二叉树程序的帮助（不是二叉搜索树）

Question

我试图实现一个二叉树（不是二叉搜索树）。它主要是一个由insert/delete/search和clear过程组成的类模板。节点中保存的数据可以是任何东西。如下所示：

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;
};

我需要一些算法方面的帮助，最好是迭代的（由于堆栈大小的限制，希望避免递归的），以用于插入、搜索和删除：

Answer 1

有一个真正的理由支持英国夏令营而不是英国电信。

BST是用于插入、删除和搜索的log(N)，而BT最终可能会以O(N)为代价完成树的遍历。

>

插入：如何确保树不向左/向右倾斜？

不，没有更好的方法来防止O(n)搜索。您需要遍历完整的树，在BT中没有节点的模式/顺序来帮助您有效地导航。