本文共 10751 字，大约阅读时间需要 35 分钟。
1.tree.h
#includeusing std::vector;//元素节点typedef struct _TREE_NODE{ int nElement; //数据 _TREE_NODE* pLChild; //左子树 _TREE_NODE* pRChild; //右子树}TREE_NODE, *PTREE_NODE;class CTree{public: CTree(); ~CTree();public: bool AddData(int nData); //添加元素 bool DelData(int nData); //删除元素 void ClearTree(); //清空元素 void TravsoualPre(); //前序遍历 void TravsoualMid(); //中序遍历 void TravsoualBack(); //后序遍历 void LevelTravsoual(); //层序遍历 int GetCount(); //获取元素个数 bool empty();private: bool AddData(PTREE_NODE& pTree, int nData); //添加元素 bool DelData(PTREE_NODE& pTree, int nData); //删除元素 int GetDeep(PTREE_NODE pTree); //获取深度 void ClearTree(PTREE_NODE& pTree); //清空元素 PTREE_NODE GetMaxOfLeft(PTREE_NODE pTree); //获取左子树中的最大值节点 PTREE_NODE GetMinOfRight(PTREE_NODE pTree); //获取又子树中的最小值节点 void TravsoualPre(PTREE_NODE pTree); //前序遍历 void TravsoualMid(PTREE_NODE pTree); //中序遍历 void TravsoualBack(PTREE_NODE pTree); //后序遍历 //旋转操作 void LeftWhirl(PTREE_NODE& pTree); //左旋 void RightWhirl(PTREE_NODE& pTree); //右旋 void LeftRightWhirl(PTREE_NODE& pTree); //左右旋 void RightLeftWhirl(PTREE_NODE& pTree); //右左旋private: PTREE_NODE m_pRoot; //根节点 int m_nCount; //元素个数};
2.tree.cpp
#include#include "Tree.h"CTree::CTree() :m_pRoot(0), m_nCount(0){}CTree::~CTree(){}//************************************// Method: AddData 添加数据// FullName: CTree::AddData// Access: private // Returns: bool// Parameter: int nData//************************************bool CTree::AddData(int nData){ return AddData(m_pRoot, nData);}//************************************// Method: AddData// FullName: CTree::AddData// Access: private // Returns: bool// Parameter: PTREE_NODE & pTree 根节点// Parameter: int nData//************************************bool CTree::AddData(TREE_NODE*& pTree, int nData){ //pTree是否为空,如果为空说明有空位可以添加 if (!pTree) { pTree = new TREE_NODE{}; pTree->nElement = nData; m_nCount++; return true; } //与根做对比，小的放在其左子树，否则放在右子树 if (nData > pTree->nElement) { AddData(pTree->pRChild, nData); } if (nData < pTree->nElement) { AddData(pTree->pLChild, nData); }}//************************************// Method: DelData 删除元素// FullName: CTree::DelData// Access: private // Returns: bool// Parameter: int nData//************************************bool CTree::DelData(int nData){ return DelData(m_pRoot, nData);}//************************************// Method: DelData// FullName: CTree::DelData// Access: private // Returns: bool// Parameter: PTREE_NODE & pTree 根节点// Parameter: int nData//************************************bool CTree::DelData(PTREE_NODE& pTree, int nData){ bool bRet = false; //判断是否为空树 if (empty()) { return false; } //开始遍历要删除的数据 if (pTree->nElement == nData) { //判断是否为叶子节点，是就可以直接删除， //不是则需要找代替 if (!pTree->pLChild && !pTree->pRChild) { delete pTree; pTree = nullptr; m_nCount--; return true; } //根据左右子树的深度查找要替换的节点 if (GetDeep(pTree->pLChild) >= GetDeep(pTree->pRChild)) { PTREE_NODE pMax = GetMaxOfLeft(pTree->pLChild); pTree->nElement = pMax->nElement; DelData(pTree->pLChild, pMax->nElement); } else { PTREE_NODE pMin = GetMinOfRight(pTree->pRChild); pTree->nElement = pMin->nElement; DelData(pTree->pRChild, pMin->nElement); } } else if (nData > pTree->nElement) { bRet = DelData(pTree->pRChild, nData); } else /*if (nData < pTree->nElement)*/ { bRet = DelData(pTree->pLChild, nData); } return bRet;}//************************************// Method: ClearTree 清空元素// FullName: CTree::ClearTree// Access: private // Returns: void//************************************void CTree::ClearTree(){ ClearTree(m_pRoot); m_nCount = 0;}//************************************// Method: ClearTree// FullName: CTree::ClearTree// Access: private // Returns: void// Parameter: PTREE_NODE & pTree 根节点//************************************void CTree::ClearTree(PTREE_NODE& pTree){ //判断是否为空树 if (empty()) { return; } //判断是否为叶子节点 if (!pTree->pLChild && !pTree->pRChild) { delete pTree; pTree = nullptr; return; } ClearTree(pTree->pLChild); ClearTree(pTree->pRChild); ClearTree(pTree);}//************************************// Method: TravsoualPre 前序遍历// FullName: CTree::TravsoualPre// Access: private // Returns: void//************************************void CTree::TravsoualPre(){ TravsoualPre(m_pRoot);}//************************************// Method: TravsoualPre// FullName: CTree::TravsoualPre// Access: private // Returns: void// Parameter: PTREE_NODE pTree 根节点//************************************void CTree::TravsoualPre(PTREE_NODE pTree){ //递归的返回条件 if (!pTree) { return; } printf("%d ", pTree->nElement); TravsoualPre(pTree->pLChild); TravsoualPre(pTree->pRChild);}//************************************// Method: TravsoualMid 中序遍历// FullName: CTree::TravsoualMid// Access: private // Returns: void//************************************void CTree::TravsoualMid(){ TravsoualMid(m_pRoot);}//************************************// Method: TravsoualMid// FullName: CTree::TravsoualMid// Access: private // Returns: void// Parameter: PTREE_NODE pTree 根节点//************************************void CTree::TravsoualMid(PTREE_NODE pTree){ //递归的返回条件 if (!pTree) { return; } TravsoualMid(pTree->pLChild); printf("%d ", pTree->nElement); TravsoualMid(pTree->pRChild);}//************************************// Method: TravsoualBack 后序遍历// FullName: CTree::TravsoualBack// Access: private // Returns: void//************************************void CTree::TravsoualBack(){ TravsoualBack(m_pRoot);}//************************************// Method: TravsoualBack// FullName: CTree::TravsoualBack// Access: private // Returns: void// Parameter: PTREE_NODE pTree 根节点//************************************void CTree::TravsoualBack(PTREE_NODE pTree){ //递归的返回条件 if (!pTree) { return; } TravsoualBack(pTree->pLChild); TravsoualBack(pTree->pRChild); printf("%d ", pTree->nElement);}//************************************// Method: 层序遍历// FullName: CTree::LevelTravsoual// Access: public // Returns: void//************************************void CTree::LevelTravsoual(){ vector vecRoot; vector vecChild; vecRoot.push_back(m_pRoot); while (vecRoot.size()) { for (int i = 0; i < vecRoot.size();i++) { printf("%d ", vecRoot[i]->nElement); //判断其是否左右子节点 if (vecRoot[i]->pLChild) { vecChild.push_back(vecRoot[i]->pLChild); } if (vecRoot[i]->pRChild) { vecChild.push_back(vecRoot[i]->pRChild); } } vecRoot.clear(); vecRoot = vecChild; vecChild.clear(); printf("\n"); }}//************************************// Method: GetCount 获取元素个数// FullName: CTree::GetCount// Access: public // Returns: int//************************************int CTree::GetCount(){ return m_nCount;}//************************************// Method: GetDeep 获取节点深度// FullName: CTree::GetDeep// Access: private // Returns: int// Parameter: PTREE_NODE & pTree //************************************int CTree::GetDeep(PTREE_NODE pTree){ //判断pTree是否为空 if (!pTree) { return 0; } int nL = GetDeep(pTree->pLChild); int nR = GetDeep(pTree->pRChild); return (nL >= nR ? nL : nR) + 1;}//************************************// Method: GetMaxOfLeft 获取左子树中的最大值// FullName: CTree::GetMaxOfLeft// Access: private // Returns: PTREE_NODE// Parameter: PTREE_NODE pTree//************************************PTREE_NODE CTree::GetMaxOfLeft(PTREE_NODE pTree){ //是否空 if (!pTree) { return 0; } //判断是否有右子树 while (pTree->pRChild) { pTree = pTree->pRChild; } return pTree;}//************************************// Method: GetMinOfRight 获取右子树中的最小值// FullName: CTree::GetMinOfRight// Access: private // Returns: PTREE_NODE// Parameter: PTREE_NODE pTree//************************************PTREE_NODE CTree::GetMinOfRight(PTREE_NODE pTree){ //是否空 if (!pTree) { return 0; } //判断是否有右子树 while (pTree->pLChild) { pTree = pTree->pLChild; } return pTree;}//************************************// Method: LeftWhirl 左旋// FullName: CTree::LeftWhirl// Access: private // Returns: void// Parameter: PTREE_NODE & pTree//************************************void CTree::LeftWhirl(PTREE_NODE& pK2){/* k2 k1 k1 ==> k2 N X N X*/}//************************************// Method: RightWhirl 右旋// FullName: CTree::RightWhirl// Access: private // Returns: void// Parameter: PTREE_NODE & pTree//************************************void CTree::RightWhirl(PTREE_NODE& pK2){/* k2 k1 k1 ==> N k2 N X X*/}//************************************// Method: LeftRightWhirl 左右旋// FullName: CTree::LeftRightWhirl// Access: private // Returns: void// Parameter: PTREE_NODE & pTree//************************************void CTree::LeftRightWhirl(PTREE_NODE& pK2){/* k2 k2 N k1 左旋 N 右旋 K1 K2 N k1 [x] [x] [x] */}//************************************// Method: RightLeftWhirl 右左旋// FullName: CTree::RightLeftWhirl// Access: private // Returns: void// Parameter: PTREE_NODE & pTree//************************************void CTree::RightLeftWhirl(PTREE_NODE& pK2){/* k2 k2 N k1 右旋 N 左旋 k2 K1 N [x] k1 [x] [x]*/}bool CTree::empty(){ return m_pRoot == 0;}
3.main.cpp
#include#include "Tree.h"int _tmain(int argc, _TCHAR* argv[]){ CTree tree; tree.AddData(50); tree.AddData(40); tree.AddData(60); tree.AddData(70); tree.AddData(30); tree.AddData(45); tree.LevelTravsoual(); tree.DelData(50); tree.LevelTravsoual(); return 0;}
转载于:https://blog.51cto.com/haidragon/2074541