我正在尝试实现二叉树（不是二叉搜索树） . 它主要是一个由插入/删除/搜索和清除程序组成的类模板 . 节点中保存的数据可以是任何数据 . 如下所示：
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;
};
我需要一些关于算法的帮助， preferably iterative （希望避免因堆栈大小限制而递归），用于插入，搜索和删除：
-
插入：如何确保树不会左/右倾斜？
-
删除：当节点同时具有子节点时，删除的最佳方法是什么（例如：在BST中，用inorder后继替换） .
-
搜索：有没有有效的方法来阻止O（n）搜索？
网络上有大量资源用于BST程序（主要是递归），但没有二进制树（或至少我无法找到任何东西） . 因此想到在这里张贴它 .
1 回答
有一个真正的理由支持BST而不是BT .
BST是
log(N)用于插入，删除和搜索，而BT最终可能以O(N)为代价完全遍历树 .恐怕会对树的整体性能产生不同的影响 not . 如果您仍想这样做，请了解self-balancing tree .
要删除，只需选择树的任何叶节点并在该位置替换它 . 二叉树没有模式，因此选择随机节点不会产生任何差异 . 因此，拾取叶节点没问题 .
不，没有更好的方法来阻止
O(n)搜索 . 您需要遍历完整的树，BT中没有节点的模式/顺序来帮助您有效地导航 .