C++数据结构：二叉排序树实现及相关操作-创新互联

BSTree.h

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
#include
using namespace std;
template
struct BSTreeNode
{
 BSTreeNode* _left;
 BSTreeNode* _right;
 K _key;

 BSTreeNode(const K& key)
     :_left(nullptr)
     , _right(nullptr)
     , _key(key)
 {}
};

template
class BSTree
{
 typedef BSTreeNodeNode;
public:
 typedef K LTDateType;
 typedef struct ListNode
 {
     LTDateType data;
     struct ListNode* next;
 }ListNode;
 bool Insert(const K& key)
 {
     if (_root == nullptr)
     {
         _root = new Node(key);
         return true;
     }

     Node* parent = nullptr;
     Node* cur = _root;
     while (cur)
     {
         if (cur->_key< key)
         {
             parent = cur;
             cur = cur->_right;
         }
         else if (cur->_key >key)
         {
             parent = cur;
             cur = cur->_left;
         }
         else
         {
             return false;
         }
     }

     cur = new Node(key);
     if (parent->_key< cur->_key)
     {
         parent->_right = cur;
     }
     else
     {
         parent->_left = cur;
     }

     return true;
 }

 // 递归的方式插入
 void _InsertR(Node*& root, const K& key)
 {
     if (root == nullptr)
         root = new Node(key);
     if (root->_key< key)
         return _InsertR(root->_right, key);
     else if (root->_key >key)
         return _InsertR(root->_left, key);
     else
         return ;
 }
 void InsertR(const K& key)
 {
     return _InsertR(_root, key);
 }

 Node* Find(const K& key)
 {
     Node* cur = _root;
     while (cur)
     {
         if (cur->_key< key)
             cur = cur->_right;
         else if (cur->_key >key)
             cur = cur->_left;
         else
         {
             cout<< "找到了"<< endl;
             return cur;
         }
     }
     cout<< "找不到"<< endl;
     return NULL;
 }

 Node* _FindR(Node* root, const K& key)
 {
     if (root == nullptr)
         return nullptr;
     if (root->_key< key)
         return _FindR(root->_right, key);
     else if (root->_key >key)
         return _FindR(root->_left, key)
     else
     return  root;
 }

 Node* FindR(const K& key)
 {
     return _FindR(_root, key);
 }

 bool _EraseR(Node*& cur, const K& key)
 {
     if (cur == nullptr)
         return false;
     if (cur->_key< key)
     {
         return _EraseR(cur->_right, key);
     }
     else if (cur->_key >key)
     {
         return _EraseR(cur->_left, key);
     }
     else
     {
         // 1.左为空
         // 2.右为空
         // 3.左右都不为空
         Node* del = cur;
         if (cur->_left == nullptr)
         {
             cur = cur->_right;
             delete del;
             return true;
         }
         else if (cur->_right == nullptr)
         {
             cur = cur->_left;
             delete del;
             return true;
         }
         else
         {
             // 替换法删除  左树的大节点(最右节点) 或者是右树的最小节点(最左节点)
             Node* minNode = cur->_right;
             while (minNode->_left)
             {
                 minNode = minNode->_left;
             }
             cur->_key = minNode->_key;

             // 转换成去右子树中删除这个最小节点的值的子问题。
             return _EraseR(cur->_right, minNode->_key);
         }
     }
 }

 bool EraseR(const K& key)
 {
     return _EraseR(_root, key);
 }

 bool Erase(const K& key)
 {
     Node* parent = nullptr;
     Node* cur = _root;
     while (cur)
     {
         if (cur->_key< key)
         {
             parent = cur;
             cur = cur->_right;
         }
         else if (cur->_key >key)
         {
             parent = cur;
             cur = cur->_left;
         }
         else
         {
             // 1.左为空
             // 2.右为空
             // 3.左右都不为空
             if (cur->_left == nullptr)
             {
                 if (parent == nullptr)
                 {
                     _root = cur->_right;
                 }
                 else
                 {
                     if (cur == parent->_left)
                         parent->_left = cur->_right;
                     else
                         parent->_right = cur->_right;
                 }

                 delete cur;
             }
             else if (cur->_right == nullptr)
             {
                 if (parent == nullptr)
                 {
                     _root = cur->_left;
                 }
                 else
                 {
                     if (cur == parent->_left)
                         parent->_left = cur->_left;
                     else
                         parent->_right = cur->_left;
                 }

                 delete cur;
             }
             else
             {
                 // 替换法删除  左树的大节点(最右节点) 或者是右树的最小节点(最左节点)
                 Node* minNodeParent = cur;  // 这里要注意不能初始化给空
                 Node* minNode = cur->_right;
                 while (minNode->_left)
                 {
                     minNodeParent = minNode;
                     minNode = minNode->_left;
                 }

                 swap(cur->_key, minNode->_key);
                 // 转换成删除minNode

                 // 因为minNode是作为空的节点，可以直接删除
                 if (minNodeParent->_right == minNode)
                     minNodeParent->_right = minNode->_right;
                 else
                     minNodeParent->_left = minNode->_right;

                 delete minNode;
             }

             return true;
         }
     }

     return false;
 }
 void _InOrder(Node* root)
 {
     if (root == nullptr)
         return;
     _InOrder(root->_left);
     cout<< root->_key<< " ";
     _InOrder(root->_right);
 }
 void InOrder()
 {
     _InOrder(_root);
     cout<< endl;
 }
 void _CreatLeafList(Node*root, ListNode*&head, ListNode*&tail)
 {
     if (root == nullptr)
     {
         return;
     }
     if (root->_left == nullptr&&root->_right == nullptr)
     {

         tail->next = new ListNode();
         tail->next->data = root->_key;
         tail = tail->next;
         return;
     }
     _CreatLeafList(root->_left, head, tail);
     _CreatLeafList(root->_right, head, tail);

 }
 void CreatLeafList()
 {
     ListNode*head = new ListNode();//开头节点
     ListNode*tail = head;
     _CreatLeafList(_root, head, tail);
     ListNode*cur = head->next;
     while (cur)
     {
         cout<< cur->data<< " ";
         cur = cur->next;
     }
     cout<< endl;
     while (head)
     {
         ListNode*tmp = head->next;
         delete head;
         head = tmp;
     }
 }
 void _invertTree(Node* root){
     if (root){
         Node* tmp = root->_left;
         root->_left = root->_right;
         root->_right = tmp;
         _invertTree(root->_left);
         _invertTree(root->_right);
     }
 }
 void invertTree(){
     _invertTree(_root);
 }
 int BinaryTreeSize(Node* root)
 {
     return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
 }
 // 二叉树叶子节点个数
 int BinaryTreeLeafSize(Node* root)
 {
     if (!root)
     {
         return 0;
     }
     if (!root->_left&&!root->_right)
     {
         return 1;
     }
     return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
 }
 int  OneChildSize(){
     int TreeSize = BinaryTreeSize(_root);
     int LeafSize = BinaryTreeLeafSize(_root);
     int Size = TreeSize - 2 * LeafSize + 1;
     return Size;
 }
 bool _AncestorNode(stack&st, Node*root, const K&key)
 {
     if (root == nullptr)
     {
         return false;
     }
     st.push(root);
     if (root->_key == key)
     {
         return true;
     }
     if (_AncestorNode(st, root->_left, key))//如果左子树找到入栈了结束路径
     {
         return true;
     }
     if (_AncestorNode(st, root->_right, key))
     {
         return true;
     }
     //都找不到删根路径
     st.pop();
     return false;
 }
 void AncestorNode()
 {
     stackst;
     vectorv;
     int k;
     cout<< "请输入要查找祖先的节点:";
     cin >>k;
     _AncestorNode(st, _root, k);
     while (!st.empty())
     {
         int tmp = st.top()->_key;
         st.pop();
         v.push_back(tmp);
     }
     reverse(v.begin(), v.end());
     for (auto e : v)
     {
         cout<< e<< " ";
     }
     cout<< endl;
 }
private:
 Node* _root = nullptr;
};

test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include"BSTree.h"

typedef enum
{
 QUIT,
 Insert,
 Erase,
 FIND,
 InOrder,
 CreatLeafList,
 invertTree,
 OneChildSize,
 AncestorNode,
 EXIT
}OPER_ENUM;

void Menu()
{
 printf("***************************************\n");
 printf("*  [1] Insert         [2] Erase             *\n");
 printf("*  [3] Find           [4] InOrder          *\n");
 printf("*  [5]CreatLeafList   [6]invertTree  *\n");
 printf("*  [7] OneChildSize   [8]AncestorNode *\n");
 printf("*                 [0] Quit                        *\n");
 printf("***************************************\n");
}

void TestBSTree()
{
 vectorb;
 BSTreebst;
 int e = 0, n = 0;
 cout<< "请输入创建个数"<< endl;
 cin >>n;
 for (int i = 0; i< n; i++)
 {
     cout<< "请输入元素"<< endl;
     cin >>e;
     bst.InsertR(e);
 }
 int select = 1;
 while (select)
 {
     Menu();
     printf("请选择:>");
     scanf("%d", &select);
     if (select == QUIT)
         break;
     switch (select)
     {
     case Insert:
         cout<< "请输入元素："<< endl;
         cin >>e;
         bst.InsertR(e);
         break;
     case Erase:
         cout<< "请输入删除元素："<< endl;
         cin >>e;
         bst.Erase(e);
         break;
     case FIND:
         cout<< "请输入查找元素："<< endl;
         cin >>e;
         bst.Find(e);
         break;
     case InOrder:
         cout<< "中序遍历："<< endl;
         bst.InOrder();
         break;
     case CreatLeafList:
         cout<< "显示叶子节点链表："<< endl;
         bst.CreatLeafList();
         break;
     case invertTree:
         cout<< "反转二叉树：";
         bst.invertTree();
         bst.InOrder();
         break;
     case OneChildSize:
         cout<< "一个孩子节点个数：";
         cout<< bst.OneChildSize()<< endl;
         break;
     case AncestorNode:
         cout<< "查找祖先节点"<< endl;
         bst.AncestorNode();
         break;
     case EXIT:
         printf("感谢使用\n");
         break;
     default:
         printf("输入选择错误，请重新输入...\n");
         break;
     }
 }
}
int main()
{
 TestBSTree();
 system("pause");
 return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧