二叉搜索树的插入与删除

二叉搜索树的插入与删除 学习各种外挂制作技术，马上去百度搜索 """"魔鬼作坊"""" 点击第一个站进入、快 速成为做挂达人。 思路添加结点： 添加结点其实很容易，我们只需要找到结点所行对应的位置就可以了，而且没有要求是 平衡的二叉搜索树，因此每次添加结点都是在叶子结点上操作，不需要修改二叉搜索树整体 的结构。要找出添加节点在二叉搜索树中的位置，可以用一个循环解决。判断插入结点与当 前头结点的大小，如果大于头结点则继续搜索右子树，如果小于头结点则继续搜索左子树。 直到搜索到叶子结点，此时进行插入结点操作。如果插入的结点等于二叉搜索树中当前某一 结点的值，那么退出插入操作，并告知用户该结点已经存在。 删除结点： 删除结点比较麻烦，因为需要调整树的结构，这是因为删除结点并不一定发生在叶子结 点。如果删除的是叶子结点，那么操作非常简单，只是做相应的删除就可以了，但如果删除 的是非叶子结点，那么就需要调整二叉搜索树的结构。调整的策略有两个。假设当前需要删 除的结点为A, 找出A结点左子树中的最大值结点 B,将 B调整到原先A的位置。 找出A结点右子树中的最小值结点 C,将 C调整到原先A的位置。 这其中涉及到许多复杂的指针操作，在下面的代码示例中并没有完成结点删除操作，等 有空再补充研究一下。 代码示例 View Code #include #include #include using namespace std; //二叉树结点 struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }; class BST { public: BST（int value）；//构造函数 ~BST（）；//析构函数 void AddNode（int value）；//添加结点 void DeleteNode（int value）；//删除结点 BinaryTreeNode* CreateBinaryTreeNode（int value）；//创建一个二叉树结点 void InOrderPrintTree（）；//中序遍历 void InOrderPrintTree（BinaryTreeNode* pRoot）；//中序遍历 BinaryTreeNode* GetMaxNode（BinaryTreeNode* pNode）；//求二叉搜索树最大值 BinaryTreeNode* GetMinNode（BinaryTreeNode* pNode）；//求二叉搜索树最小值 private: BinaryTreeNode* pRoot; }; //构造函数 BST::BST（int value） { pRoot=CreateBinaryTreeNode（value）； } //析构函数 BST::~BST（） { delete pRoot; pRoot=NULL; } //创建二叉树结点 BinaryTreeNode* BST::CreateBinaryTreeNode（int value） { BinaryTreeNode* pNode=new BinaryTreeNode（）； pNode->m_nValue=value; pNode->m_pLeft=NULL; pNode->m_pRight=NULL; return pNode; } //求二叉搜索树最大值 BinaryTreeNode* BST::GetMaxNode（BinaryTreeNode* pNode） { assert（pNode!=NULL）； // 使用断言，保证传入的头结点不为空 //最大值在右子树上，因此一直遍历右子树，让 pNode等于其右子树；如果只有一个结 点则直接返回 pNode while（pNode->m_pRight!=NULL） { pNode=pNode->m_pRight; } return pNode; } //求二叉搜索树最小值 BinaryTreeNode* BST::GetMinNode（BinaryTreeNode* pNode） { assert（pNode!=NULL）； // 使用断言 //最小值在左子树上，整体思路跟求最大值相同。 while（pNode->m_pLeft!=NULL） { pNode=pNode->m_pLeft; } return pNode; } //二叉搜索树添加结点 void BST::AddNode（int value） { BinaryTreeNode* pInsertNode=CreateBinaryTreeNode（value）；//初始化需要创建的结点。 BinaryTreeNode* pNode=pRoot; while（true） { //如果插入的值在二叉搜索树中已经存在，则不进行插入操作，跳出循环。 if（pNode->m_nValue==value） { cout《“结点值已经存在”《endl; break; } //寻找结点插入的位置，如果待插入结点小于当前头结点，则继续搜索左子树 else if（pNode->m_nValue > value） { if（pNode->m_pLeft==NULL）//如果当前头结点是叶子结点了，那么直接将待插入结点 插入到左子树中，然后跳出循环 { pNode->m_pLeft=pInsertNode; break; } else//否则继续遍历其左子树 pNode=pNode->m_pLeft; } //思路跟上述相同 else if（pNode->m_nValue < value） { if（pNode->m_pRight==NULL） { pNode->m_pRight=pInsertNode; break; } pNode=pNode->m_pRight; } } } //未完成 void BST::DeleteNode（int value） { BinaryTreeNode* pNode=pRoot; while（true） { if（pRoot->m_nValue==value）//如果是头结点 { if（pRoot->m_pLeft!=NULL） { BinaryTreeNode* pLeftMaxNode=GetMaxNode（pRoot->m_pLeft）； } else if（pRoot->m_pRight!=NULL） { } else { delete pRoot; pRoot=NULL; } } if（pNode->m_nValue==value） { if（pNode->m_pLeft!=NULL） { } else if（pNode->m_pRight!=NULL） { } else { } } } } void BST::InOrderPrintTree（BinaryTreeNode* pRoot）//中序遍历 { if（pRoot!=NULL） { //如果左子树不为空，则遍历左子树 if（pRoot->m_pLeft!=NULL） InOrderPrintTree（pRoot->m_pLeft）； //遍历左子树的叶子结点 cout《“value of this node is ”《pRoot->m_nValue《endl; //如果右子树不为空，遍历右子树 if（pRoot->m_pRight!=NULL） InOrderPrintTree（pRoot->m_pRight）； } else { cout《“this node is null.”《endl; } } //因为需要使用递归来进行中序遍历，所以还需要调用一个带参数的中序遍历函数 void BST::InOrderPrintTree（）//中序遍历 { InOrderPrintTree（pRoot）； } void main（） { BST* b=new BST（10）；//初始化类的时候定义了二叉搜索树的头结点，这样省去了头 结点为空的判断 b->AddNode（6）； b->AddNode（14）； b->InOrderPrintTree（）； system（“pause”）；