#include<iostream> #include<stdlib.h> #include<cassert> 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"); }