一、抽象数据类型
typedef int DataType
class BinTreeNode {
public:
DataType data;
BinTreeNode *leftChild;
BinTreeNode *rightChild;
BinTreeNode(){ //构造函数,构造一个空结点
leftChild = NULL;
rightChild = NULL;
}
}
class BinaryTree {
public:
BinTreeNode *root;
BinaryTree(){
root = NULL;
}
~BinaryTree(){
DeleteTree();
}
bool InsertLeft(BinTreeNode *current, DataType x); //将元素 x 插入作为 current 所指结点的左孩子
bool InsertRight(BinTreeNode *current, DataType x); //将元素x插入作为current所指结点的右孩子
void Preorder(BinTreeNode *current); //先序遍历
void InOrder(BinTreeNode *current); //中序遍历
void Postorder(BinTreeNode *current); //后序遍历
BinTreeNode *Find(BinTreeNode *current, DataType x); //搜索值为 x 的结点
void Destroy(BinTreeNode *current); //删除指定子树
void DeleteTree(){ //删除整棵树
Destroy(root);
root = NULL;
}
bool IsEmpty(){ //判树空否
return root == NULL;
}
BinTreeNode *CreatBinTree(); //创建一棵二叉树
}
二、部分成员函数的实现
//插入左孩子
bool BinaryTree::InsertLeft(BinTreeNode *current, DataType item) {
if (current == NULL)
return false;
BinTreeNode *p = new BinTreeNode;
p->data = item;
current->leftChild = p;
return true;
}
//插入右孩子
bool BinaryTree::InsertRight(BinTreeNode *current, DataType item) {
if (current == NULL)
return false;
BinTreeNode *p = new BinTreeNode;
p->data = item;
current->rightChild = p;
return true;
}
//删除指定子树
void BinaryTree::destroy(BinTreeNode *current) {
if (current != NULL) {
destroy(current->leftChild);
destroy(current->rightChild);
delete current;
}
}
//搜索值为 x 的结点
BinTreeNode *BinaryTree::Find(BinTreeNode *current, DataType x) {
if(current == NULL)
return NULL;
if(current->data == x)
return current;
BinTreeNode *p = Find(current->leftChild);
if(p != NULL)
return p;
else
return Find(current->rightChild);
}