C++数据结构：二叉排序树实现及相关操作-创新互联
BSTree.h
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
#include
using namespace std;
template
struct BSTreeNode
{
BSTreeNode
BSTreeNode
K _key;
BSTreeNode(const K& key)
:_left(nullptr)
, _right(nullptr)
, _key(key)
{}
};
template
class BSTree
{
typedef BSTreeNode
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
{
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()
{
stack
vector
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()
{
vector
BSTree
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元起，快前往官网查看详情吧
本文名称：C++数据结构：二叉排序树实现及相关操作-创新互联
网站网址：http://myzitong.com/article/dghdis.html