Tim的资源站

一、抽象数据类型

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