二叉樹(shù)的實(shí)現(xiàn)

1、#if 0 #include #include #include using namespace std; template classBinaryTreeNode public:Type m_Data;BinaryTreeNode*m_leftChild; BinaryTreeNode*m_rightChild;public:BinaryTreeNode() m_leftChild = m_rightChild = NULL; BinaryTreeNode(constType&data, BinaryTreeNode *leftChild = NULL, BinaryTreeNode *ri

2、ghtChild = NULL)m_Data = data; m_leftChild = leftChild; m_rightChild = rightChild;Type &GetData() return m_Data; ;BinaryTreeNode*GetleftChild() return m_leftChild; BinaryTreeNode*GetrightChild() return m_rightChild; voidsetData(constType&data) m_Data = data; voidsetLeftChild(BinaryTreeNode*leftChild

3、) m_leftChild = leftChild; voidsetRightChild(BinaryTreeNode*rightChild) m_rightChild = rightChild; ;template classBinaryTree public:BinaryTreeNode*m_root;public:BinaryTree() m_root = NULL; BinaryTree(T data) m_root = new BinaryTreeNode(data); virtual BinaryTree();/判斷節(jié)點(diǎn)是否為空 boolIsEmpty()const;/判斷是否為左

4、孩子 boolIsLeftChild(BinaryTreeNode*p);/判斷是否為右孩子 boolIsRightChild(BinaryTreeNode*p);/獲得整棵樹(shù)的根BinaryTreeNode *GetRoot();/取得一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)指針 BinaryTreeNode*GetParent(BinaryTreeNode*p);/取得一個(gè)節(jié)點(diǎn)的左孩子指針 BinaryTreeNode*GetLeftChild(BinaryTreeNode*p);/取得一個(gè)節(jié)點(diǎn)的右孩子指針 BinaryTreeNode*GetRightChild(BinaryTreeNode*p);/取得一個(gè)節(jié)

5、點(diǎn)的左兄弟指針 BinaryTreeNode*GetLeftSibling(BinaryTreeNode*p);/取得一個(gè)節(jié)點(diǎn)的右兄弟指針 BinaryTreeNode*GetRightSibling(BinaryTreeNode*p);/返回一個(gè)節(jié)點(diǎn)的數(shù)據(jù)TRetrieve(BinaryTreeNode*p);/設(shè)置一個(gè)節(jié)點(diǎn)的數(shù)據(jù)void Assign(BinaryTreeNode*p, const T &d); /插入右邊孩子到當(dāng)前節(jié)點(diǎn) voidInsertRightChild(BinaryTreeNode*p, const T &d); /插入左孩子到當(dāng)前節(jié)點(diǎn) voidInsertLef

6、tChild(BinaryTreeNode*p, const T &d);/線序遍歷二叉樹(shù)virtual void PreOrderTraverse(BinaryTreeNode*root)const;/中序遍歷二叉樹(shù) virtual void InOrderTraverse(BinaryTreeNode*root)const;/后序遍歷二叉樹(shù)virtual void PostOrderTraverse(BinaryTreeNode*root)const; protected:/得到本節(jié)點(diǎn)的父節(jié)點(diǎn) BinaryTreeNode*Parent(BinaryTreeNode*root, Binar

7、yTreeNode*p); /刪除節(jié)點(diǎn)void Destroy(BinaryTreeNode*p);templateBinaryTree:BinaryTree()Destroy(m_root); m_root = NULL;/判斷節(jié)點(diǎn)是否為空template boolBinaryTree:IsEmpty()const return NULL = m_root ? true : false; /判斷是否為左孩子 templateboolBinaryTree:IsLeftChild(BinaryTreeNode*p)return Parent(m_root,p)-GetleftChild() =

8、p;/判斷是否為右孩子template boolBinaryTree:IsRightChild(BinaryTreeNode*p)return Parent(m_root,p)-GetrightChild() = p;/獲得整棵樹(shù)的根templateBinaryTreeNode *BinaryTree:GetRoot()returnm_root;/取得一個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)指針templateBinaryTreeNode*BinaryTree:GetParent(BinaryTreeNode*p)return Parent(m_root,p);/取得一個(gè)節(jié)點(diǎn)的左孩子指針templateBinaryT

9、reeNode*BinaryTree:GetLeftChild(BinaryTreeNode*p) if (NULL=p)return NULL:return p-GetleftChild();/取得一個(gè)節(jié)點(diǎn)的右孩子指針templateBinaryTreeNode*BinaryTree:GetRightChild(BinaryTreeNode*p) if (NULL = p)return NULL;return p-GetrightChild();/取得一個(gè)節(jié)點(diǎn)的左兄弟指針templateBinaryTreeNode*BinaryTree:GetLeftSibling(BinaryTreeNo

10、de*p) if (p = m_root)return NULL;BinaryTreeNode*temp; temp= Parent(m_root,p); if (p=temp-GetleftChild) return NULL;return temp-GetleftChild();/取得一個(gè)節(jié)點(diǎn)的右兄弟指針 templateBinaryTreeNode*BinaryTree:GetRightSibling(BinaryTreeNode*p) if (p = m_root) return NULL;BinaryTreeNode*temp;temp = Parent(m_root, p);if

11、(p = temp-GetrightChild()return NULL;return temp-GetrightChild();/返回一個(gè)節(jié)點(diǎn)的數(shù)據(jù) templateT BinaryTree:Retrieve(BinaryTreeNode*p)return p-GetData();/設(shè)置一個(gè)節(jié)點(diǎn)的數(shù)據(jù) template voidBinaryTree:Assign(BinaryTreeNode*p,const T &d) p-setData(d);/插入右邊孩子到當(dāng)前節(jié)點(diǎn) template voidBinaryTree:InsertRightChild(BinaryTreeNode*p,con

12、st T &d) BinaryTreeNode*temp=new BinaryTreeNode(d); temp-setRightChild(p-GetrightChild();p-setRightChild(temp);/插入左孩子到當(dāng)前節(jié)點(diǎn) template voidBinaryTree:InsertLeftChild(BinaryTreeNode*p, const T &d) BinaryTreeNode*temp = new BinaryTreeNode(d);temp-setLeftChild(p-GetleftChild(); p-setLeftChild(temp);/先序遍歷二

13、叉樹(shù) template voidBinaryTree:PreOrderTraverse(BinaryTreeNode*root)const stackBinaryTreeNode* s;BinaryTreeNode*p = root;while (!s.empty()|p!=NULL)while (p)s.push(p);coutGetData();p = p-GetleftChild();p = s.top();s.pop();p = p-GetrightChild();/中序遍歷二叉樹(shù) template voidBinaryTree:InOrderTraverse(BinaryTreeNo

14、de*root)const stackBinaryTreeNode* s;BinaryTreeNode*p = root;while (!s.empty()|NULL!=p)while (p)s.push(p); p-GetleftChild();p = s.top();s.pop();coutGetData();p = p-GetrightChild(); /后序遍歷二叉樹(shù) template voidBinaryTree:PostOrderTraverse(BinaryTreeNode*root)const if (NULL != root)PostOrderTraverse(root-Ge

15、tleftChild();PostOrderTraverse(root-GetrightChild();coutGetData();/得到本節(jié)點(diǎn)的父節(jié)點(diǎn)templateBinaryTreeNode*BinaryTree:Parent(BinaryTreeNode*root, BinaryTreeNode*p) if (NULL = root)return NULL;if (root-GetleftChild() = p | root-GetrightChild = p)return root;if (NULL != (q = Parent(root-GetleftChild(), p)return q;elsereturn Parent(root-GetrightChild(), p);/刪除節(jié)點(diǎn)template voidBinaryTree:Destroy(BinaryTreeNode*p) if (NULL != p)Destroy(p-GetleftChi