BSTree.h

創(chuàng)新互聯(lián)建站主要企業(yè)基礎(chǔ)官網(wǎng)建設(shè)，電商平臺(tái)建設(shè)，移動(dòng)手機(jī)平臺(tái)，成都微信小程序等一系列專(zhuān)為中小企業(yè)按需制作產(chǎn)品體系；應(yīng)對(duì)中小企業(yè)在互聯(lián)網(wǎng)運(yùn)營(yíng)的各種問(wèn)題，為中小企業(yè)在互聯(lián)網(wǎng)的運(yùn)營(yíng)中保駕護(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
??? ??? ?{
??? ??? ??? ?// 替換法刪除 ?左樹(shù)的大節(jié)點(diǎn)(最右節(jié)點(diǎn)) 或者是右樹(shù)的最小節(jié)點(diǎn)(最左節(jié)點(diǎn))
??? ??? ??? ?Node* minNode = cur->_right;
??? ??? ??? ?while (minNode->_left)
??? ??? ??? ?{
??? ??? ??? ??? ?minNode = minNode->_left;
??? ??? ??? ?}
??? ??? ??? ?cur->_key = minNode->_key;

??? ??? ??? ?// 轉(zhuǎn)換成去右子樹(shù)中刪除這個(gè)最小節(jié)點(diǎn)的值的子問(wèn)題。
??? ??? ??? ?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
??? ??? ??? ?{
??? ??? ??? ??? ?// 替換法刪除 ?左樹(shù)的大節(jié)點(diǎn)(最右節(jié)點(diǎn)) 或者是右樹(shù)的最小節(jié)點(diǎn)(最左節(jié)點(diǎn))
??? ??? ??? ??? ?Node* minNodeParent = cur; ?// 這里要注意不能初始化給空
??? ??? ??? ??? ?Node* minNode = cur->_right;
??? ??? ??? ??? ?while (minNode->_left)
??? ??? ??? ??? ?{
??? ??? ??? ??? ??? ?minNodeParent = minNode;
??? ??? ??? ??? ??? ?minNode = minNode->_left;
??? ??? ??? ??? ?}

??? ??? ??? ??? ?swap(cur->_key, minNode->_key);
??? ??? ??? ??? ?// 轉(zhuǎn)換成刪除minNode

??? ??? ??? ??? ?// 因?yàn)閙inNode是作為空的節(jié)點(diǎn)，可以直接刪除
??? ??? ??? ??? ?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();//開(kāi)頭節(jié)點(diǎn)
??? ?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;
?}
?// 二叉樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)
?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))//如果左子樹(shù)找到入棧了結(jié)束路徑
??? ?{
??? ??? ?return true;
??? ?}
??? ?if (_AncestorNode(st, root->_right, key))
??? ?{
??? ??? ?return true;
??? ?}
??? ?//都找不到刪根路徑
??? ?st.pop();
??? ?return false;
?}
?void AncestorNode()
?{
??? ?stackst;
??? ?vectorv;
??? ?int k;
??? ?cout<< "請(qǐng)輸入要查找祖先的節(jié)點(diǎn):";
??? ?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<< "請(qǐng)輸入創(chuàng)建個(gè)數(shù)"<< endl;
?cin >>n;
?for (int i = 0; i< n; i++)
?{
??? ?cout<< "請(qǐng)輸入元素"<< endl;
??? ?cin >>e;
??? ?bst.InsertR(e);
?}
?int select = 1;
?while (select)
?{
??? ?Menu();
??? ?printf("請(qǐng)選擇:>");
??? ?scanf("%d", &select);
??? ?if (select == QUIT)
??? ??? ?break;
??? ?switch (select)
??? ?{
??? ?case Insert:
??? ??? ?cout<< "請(qǐng)輸入元素："<< endl;
??? ??? ?cin >>e;
??? ??? ?bst.InsertR(e);
??? ??? ?break;
??? ?case Erase:
??? ??? ?cout<< "請(qǐng)輸入刪除元素："<< endl;
??? ??? ?cin >>e;
??? ??? ?bst.Erase(e);
??? ??? ?break;
??? ?case FIND:
??? ??? ?cout<< "請(qǐng)輸入查找元素："<< endl;
??? ??? ?cin >>e;
??? ??? ?bst.Find(e);
??? ??? ?break;
??? ?case InOrder:
??? ??? ?cout<< "中序遍歷："<< endl;
??? ??? ?bst.InOrder();
??? ??? ?break;
??? ?case CreatLeafList:
??? ??? ?cout<< "顯示葉子節(jié)點(diǎn)鏈表："<< endl;
??? ??? ?bst.CreatLeafList();
??? ??? ?break;
??? ?case invertTree:
??? ??? ?cout<< "反轉(zhuǎn)二叉樹(shù)：";
??? ??? ?bst.invertTree();
??? ??? ?bst.InOrder();
??? ??? ?break;
??? ?case OneChildSize:
??? ??? ?cout<< "一個(gè)孩子節(jié)點(diǎn)個(gè)數(shù)：";
??? ??? ?cout<< bst.OneChildSize()<< endl;
??? ??? ?break;
??? ?case AncestorNode:
??? ??? ?cout<< "查找祖先節(jié)點(diǎn)"<< endl;
??? ??? ?bst.AncestorNode();
??? ??? ?break;
??? ?case EXIT:
??? ??? ?printf("感謝使用\n");
??? ??? ?break;
??? ?default:
??? ??? ?printf("輸入選擇錯(cuò)誤，請(qǐng)重新輸入...\n");
??? ??? ?break;
??? ?}
?}
}
int main()
{
?TestBSTree();
?system("pause");
?return 0;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前標(biāo)題：C++數(shù)據(jù)結(jié)構(gòu)：二叉排序樹(shù)實(shí)現(xiàn)及相關(guān)操作-創(chuàng)新互聯(lián)
當(dāng)前URL：http://weahome.cn/article/dghdis.html