二叉树节点的定义
template <class T> class BinaryTree;//提前声明,为了friend class BinaryTree<T>; 使用
template<class T> // 二叉树节点ADT
class BinaryTreeNode{
private:
T info; // 二叉树节点的数据域
BinaryTreeNode<T>* left; //二叉树结点指向左子树的指针
BinaryTreeNode<T>* right; //二叉树结点指向左子树的指针
public:
BinaryTreeNode();
BinaryTreeNode(const T& ele);
BinaryTreeNode(const T& ele,BinaryTreeNode<T> *l,BinaryTreeNode<T> *r);
T value() const; //返回 当前节点的数据域
BinaryTreeNode<T>* leftchild() const; // 返回左子树
BinaryTreeNode<T>* rightchild() const; // 返回右子树
void setLeftchild(BinaryTreeNode<T>*); // 设置左子树
void setRightchild(BinaryTreeNode<T>*) ; //设置当前结点的右子树
void setValue(const T& val); //设置当前结点的数据域void setRightchild(BinaryTreeNode<T>*); //
bool isLeaf() const; //判定当前结点是否为叶结点,若是返回true
BinaryTreeNode<T>& operator=(const BinaryTreeNode<T>& node);
friend class BinaryTree<T>; // 友元函数:使BinaryTree可以访问BinaryTreeNode的私有数据成员
};
template<class T>
BinaryTreeNode<T>::BinaryTreeNode() {
left = right = NULL;
}
template<class T>
BinaryTreeNode<T>::BinaryTreeNode(const T& inf) { //给定数据的构造函数
info = inf;
left = right = NULL;
}
template<class T>
BinaryTreeNode<T>::BinaryTreeNode(const T& inf,BinaryTreeNode* l, BinaryTreeNode* r) {//给定数据的左右指针的构造函数
info = inf;
left = l;
right = r;
}
template<class T>
T BinaryTreeNode<T>::value() const {
return info;
}
template<class T>
BinaryTreeNode<T>* BinaryTreeNode<T>::leftchild() const { //返回当前结点指向左子树的指针
return left;
}
template<class T>
BinaryTreeNode<T>* BinaryTreeNode<T>::rightchild() const { //返回当前结点指向右子树的指针
return right;
}
template<class T>
void BinaryTreeNode<T>::setLeftchild(BinaryTreeNode<T>* subroot) { //设置当前结点的左子树
left = subroot;
}
template<class T>
void BinaryTreeNode<T>::setRightchild(BinaryTreeNode<T>* subroot) { //设置当前结点的右子树
right = subroot;
}
template<class T>
void BinaryTreeNode<T>::setValue(const T& val) { //设置当前结点的数据域
info = val;
}
template<class T>
bool BinaryTreeNode<T>::isLeaf() const { //判定当前结点是否为叶结点,若是返回true
return (left == NULL) && (right == NULL);
}
template<class T>
class BinaryTree{
private:
BinaryTreeNode<T>* root; // root 节点
public:
BinaryTree(){root=NULL;}
~BinaryTree(){DeleteBinaryTree(root);}
bool isEmpty() const;
BinaryTreeNode<T>* Root(){return root;}
BinaryTreeNode<T>* Parent(BinaryTreeNode<T>* current);//返回current的父结点
BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T>* current);//返回current结点的左兄弟
BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T>* current);//返回current结点的右兄弟
void CreateTree(const T& info, BinaryTree<T>& leftTree, BinaryTree<T>& rightTree);//构造一棵以info为根、leftTree和rightTree为左右子树的新二叉树
void PreOrder(BinaryTreeNode<T>* root); //前序周游二叉树或其子树
void InOrder(BinaryTreeNode<T>* root); //中序周游二叉树或其子树
void PostOrder(BinaryTreeNode<T>* root); //后序周游二叉树或其子树
void PreOrderWithoutRecursion(BinaryTreeNode<T>* root);//非递归前序周游二叉树或其子树
void InOrderWithoutRecursion(BinaryTreeNode<T>* root);//非递归中序周游二叉树或其子树
void PostOrderWithoutRecursion(BinaryTreeNode<T>* root);//非递归后序周游二叉树或其子树
void LevelOrder(BinaryTreeNode<T>* root); //按层次周游二叉树或其子树
void DeleteBinaryTree(BinaryTreeNode<T>* root); //删除二叉树或其子树
void Visit(T Value) {cout << Value;}; //访问
};