这是我们老师给我们写的二叉树最基本的.......追加、删除节点的程序，很简单，但是也不简单，如果你基础比较好，这个可以忽略，如果不好，看看也无妨，打酱油路过.......呵呵
#include
using namespace std;
// 二叉搜索树
class BsTree {
public:
// 构造函数中初始化为空树
BsTree (void) : m_root (NULL), m_size (0) {}
// 析构函数中释放剩余节点
~BsTree (void) {
Clear ();
}
// 插入数据
void Insert (int data) {
Insert (new Node (data), m_root);
m_size++;
}
// 删除数据，不存在返回false
bool Remove (int data) {
Node*& find = Find (data, m_root);
if (find) {
Insert (find -> m_left, find -> m_right);
Node* node = find;
find = find -> m_right;
delete node;
m_size--;
return true;
}
return false;
}
// 删除所有值为data的数据
void RemoveAll (int data) {
while (Remove (data));
}
// 清空树
void Clear (void) {
Clear (m_root);
m_size = 0;
}
// 将全部old更新为_new
void Update (int old, int _new) {
while (Remove (old))
Insert (_new);
}
// 能否找到data
bool Find (int data) {
return Find (data, m_root) != NULL;
}
// 中序遍历
void Travel (void) {
cout m_left);
else
Insert (node, tree -> m_right);
}
}
Node*& Find (int data, Node*& tree) {
if (! tree)
return tree;
else
if (data == tree -> m_data)
return tree;
else
if (data < tree -> m_data)
return Find (data, tree -> m_left);
else
return Find (data, tree -> m_right);
}
void Clear (Node*& tree) {
if (tree) {
Clear (tree -> m_left);
Clear (tree -> m_right);
delete tree;
tree = NULL;
}
}
void Travel (Node*& tree) {
if (tree) {
Travel (tree -> m_left);
cout m_left);
size_t rh = GetHeight (tree -> m_right);
return (lh > rh ? lh : rh) + 1;
}
return 0;
}
Node* m_root; // 树根
size_t m_size; // 树的大小
};
int main (void) {
BsTree bs;
bs.Insert (50);
bs.Insert (70);
bs.Insert (20);
bs.Insert (60);
bs.Insert (40);
bs.Insert (30);
bs.Insert (10);
bs.Insert (90);
bs.Insert (80);
bs.Travel ();
cout |
转播
