二叉树实现STL.doc

//头结点定义类BinaryTreeNode.h #ifndef BINARYTREENODE_H #define BINARYTREENODE_H #include iostream using namespace std; template class Type class BinaryTreeNode { Type m_data; BinaryTreeNodeType *m_leftChild;//存储该节点的左指针 BinaryTreeNodeType *m_rightChild;//存储该节点的右指针 public: BinaryTreeNode(){m_leftChild=m_rightChild=NULL;}; BinaryTreeNode(const Type data,BinaryTreeNode *leftChild=NULL,BinaryTreeNode *rightChild=NULL) { m_data=data; m_leftChild=leftChild; m_rightChild=rightChild; }; Type GetData(){return m_data;};//返回该节点的数据 //返回该节点的左孩子节点的指针 BinaryTreeNodeType* GetLeftChild(){return m_leftChild;}; //返回该节点的右孩子节点的指针 BinaryTreeNodeType* GetRightChild(){return m_rightChild;}; //设置该节点的数据 void SetData(const Type data) { m_data=data; }; void SetLeftChild(BinaryTreeNodeType *leftChild) { m_leftChild=leftChild; }; void SetRightChild(BinaryTreeNodeType* rightChild) { m_rightChild=rightChild; }; }; #endif //二叉树定义及实现类BinaryTree.h #include BinaryTreeNode.h #include queue #include stack using namespace std; templateclass T class BinaryTree { BinaryTreeNodeT *m_root; public: BinaryTree(T data) { m_root=new BinaryTreeNodeT(data); }; virtual ~BinaryTree(); bool IsEmpty() const//判断树是否为空 { return m_root==NULL ? true : false; }; //判断一个节点是否为左孩子 bool IsLeftChild(BinaryTreeNodeT *p) { return p==GetParent(p)-GetLeftChild() ? true: false; }; //判断一个节点是否为右孩子 bool IsRightChild(BinaryTreeNodeT *p) { return p==GetParent(p)-GetRightChild() ? true: false; }; //取得根节点 BinaryTreeNodeT* GetRoot() { return m_root; }; //取得一个节点的父亲节点 BinaryTreeNodeT* GetParent(BinaryTreeNodeT *p) { return Parent(m_root,p); }; //取得一个节点的左子树指针 BinaryTreeNodeT* LeftChild(BinaryTreeNodeT *root) const { return root==NULL?NULL:root-GetLeftChild(); }; //取得一个节点的右子树指针 BinaryTreeNodeT* RightChild(BinaryTreeNodeT* root) const { return root==NULL?NULL:root-GetRightChild(); }; //取得一个节点的左兄弟指针