-
求职秘籍
站-
热门城市 全国站>
-
其他省市
-
-
400-636-0069
摘要：本文主要向大家介绍了C/C++知识点之平衡二叉树，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。
本文主要向大家介绍了C/C++知识点之平衡二叉树，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。
#include <vector>using 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(); bool bool cha(int nData){ return cha(m_pRoot, nData);
}private: bool cha(TREE_NODE*& pTree, int nData){ if (pTree==NULL) { return false;
} else if (nData==pTree->nElement) { return true;
} else if (nData < pTree->nElement){ return cha(pTree->pLChild, nData);
} else{ return cha(pTree->pRChild, nData);
}
} 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 <stdio.h> #include ""Tree.hpp""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 (GetDeep(pTree->pRChild) -
GetDeep(pTree->pLChild) == 2)
{ //判断如何旋转 if (pTree->pRChild->pRChild)
{ //左旋
LeftWhirl(pTree);
} else if (pTree->pRChild->pLChild)
{ //右左旋
RightLeftWhirl(pTree);
}
}
} if (nData < pTree->nElement)
{
AddData(pTree->pLChild, nData); //判断是否平衡 if (GetDeep(pTree->pLChild) -
GetDeep(pTree->pRChild) == 2)
{ //判断如何旋转 if (pTree->pLChild->pLChild)
{ //右旋
RightWhirl(pTree);
} else if (pTree->pLChild->pLChild)
{ //左右旋
LeftRightWhirl(pTree);
}
}
}
}//************************************// 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)
{if (!cha(nData)) {
cout<<""没有还删什么删！！！！！！""<<endl; return false;
}
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); //判断是否平衡 if (GetDeep(pTree->pLChild) -
GetDeep(pTree->pRChild) == 2)
{ //判断如何旋转 if (pTree->pLChild->pLChild)
{ //右旋
RightWhirl(pTree);
} else if (pTree->pLChild->pLChild)
{ //左右旋
LeftRightWhirl(pTree);
}
}
} else /*if (nData < pTree->nElement)*/
{
bRet = DelData(pTree->pLChild, nData); //判断是否平衡 if (GetDeep(pTree->pRChild) -
GetDeep(pTree->pLChild) == 2)
{ //判断如何旋转 if (pTree->pRChild->pRChild)
{ //左旋
LeftWhirl(pTree);
} else if (pTree->pRChild->pLChild)
{ //右左旋
RightLeftWhirl(pTree);
}
}
} 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<PTREE_NODE> vecRoot; //保存根节点
vector<PTREE_NODE> 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); //比较左右子树的深度，取最大值加 1 返回 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
*/ //保存k1
PTREE_NODE pK1 = pK2->pRChild; //保存X
pK2->pRChild = pK1->pLChild; //k2变成k1的左子树
pK1->pLChild = pK2; //k1变成k2
pK2 = pK1;
}//************************************// 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
*/ //保存k1
PTREE_NODE pK1 = pK2->pLChild; //保存X
pK2->pLChild = pK1->pRChild; //k1的右子树为k2
pK1->pRChild = pK2; //k2为k1
pK2 = pK1;
}//************************************// 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]
*/
LeftWhirl(pK2->pLChild);
RightWhirl(pK2);
}//************************************// 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]
*/
RightWhirl(pK2->pRChild);
LeftWhirl(pK2);
}
bool CTree::empty()
{ return m_pRoot == 0;
}3.main.cpp
#include <stdio.h> #include ""Tree.h""int _tmain(int argc, _TCHAR* argv[])
{
CTree tree;
tree.AddData(1);
tree.AddData(2);
tree.AddData(3);
tree.AddData(4);
tree.AddData(5);
tree.AddData(6);
tree.AddData(7);
tree.AddData(8);
tree.AddData(9);
tree.AddData(10);
tree.LevelTravsoual();
tree.DelData(4);
tree.LevelTravsoual(); return 0;
}本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！
喜欢 | 0
不喜欢 | 0
您输入的评论内容中包含违禁敏感词
我知道了
请输入正确的手机号码
请输入正确的验证码
您今天的短信下发次数太多了，明天再试试吧！
我们会在第一时间安排职业规划师联系您！
您也可以联系我们的职业规划师咨询：
版权所有 职坐标-一站式IT培训就业服务领导者 沪ICP备13042190号-4
上海海同信息科技有限公司 Copyright ©2015 www.zhizuobiao.com，All Rights Reserved.
沪公网安备 31011502005948号
索取资料
答疑解惑
技术交流
职业测评
面试技巧
高薪秘笈
