二叉树搜索树基本操作
作者：Lew's Personal Blog 发布于：2020-3-21 15:07 Saturday 分类：Data structure
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
template<typename T>
class binary_tree_node
{
public:
T _data;
binary_tree_node<T>* _left;
binary_tree_node<T>* _right;
binary_tree_node(const T& x) //构造函数
: _data(x)
, _left(NULL)
, _right(NULL)
{}
};
template<class T>
class binary_tree
{
typedef binary_tree_node<T> node;//define a node
public:
binary_tree(T* a, size_t n)
{
size_t index = 0;
_root = _create_searchtree(a, n, index);
}
~binary_tree()
{
destory(_root);
_root = NULL;
}
void destory(node* root)
{
if(root == NULL)
return;
destory(root->_left);
destory(root->_right);
delete root;
}
//创建一棵二叉搜索树
node* _create_searchtree(T* a, size_t n, size_t& index)
{
node* root = NULL;
root = new node(a[index]); //index 标识
_root = root;
while(index < n - 1)
{
insert(a[++index]);
}
return _root;
}
//创建一棵二叉树
node* _create_tree(T *a, size_t n, const T& invalid, size_t& index)
{
node* root = NULL;
if(a[index] != invalid)
{
root = new node(a[index]);
root->_left = _create_tree(a, n, invalid, ++index);
root->_right = _create_tree(a, n, invalid, ++index);
}
return root;
}
void prev_order() //配置接口
{
_prev_order(_root);
cout << endl;
}
//递归形式
void _prev_order(node* root)
{
if(root == NULL)
return;
cout << root->_data << " ";
_prev_order(root->_left);
_prev_order(root->_right);
}
//非递归的前序遍历
void prev_order_no_r()
{
node* cur = _root;
stack<node*> s;
while(cur || !s.empty())
{
while(cur)
{
cout << cur->_data << " ";
s.push(cur);
cur = cur->_left;
}
node* top = s.top;
s.pop();
cur = top->_right;
}
cout << endl;
}
//中序遍历
void in_order()
{
_in_order(_root);
cout << endl;
}
void _in_order(node* root)
{
if(root == NULL)
return;
_in_order(root->_left);
cout << root->_data << " ";
_in_order(root->_right);
}
//非递归的中序遍历
void in_order_no_r()
{
node* cur = _root;
stack<node*> s;
while(cur || !s.empty())
{
while(cur)
{
s.push(cur);
cur = cur->_left;
}
node* top = s.top();
cout << top->_data << " ";
s.pop();
cur = top->_right;
}
cout << endl;
}
//非递归的后序遍历
void post_order_no_r()
{
node* cur = _root;
node* prev = NULL;
stack<node*> s;
while(cur || !s.empty())
{
while(cur)
{
s.push(cur);
cur = cur->_left;
}
node* top = s.top();
if(top->_right == NULL || top->_right == prev)
{
cout << top->_data << " ";
s.pop();
prev = top;
}
else
{
cur = top->_right;
}
}
cout << endl;
}
//节点个数
int size()
{
size_t size = 0;
_size(_root, size);
return size;
}
void _size(node* root, size_t &size)
{
if(root == NULL)
return;
_size(root->_left, size);
++size;
_size(root->_right, size);
}
size_t leaf_size()
{
return _leaf_size(_root);
}
size_t _leaf_size(node *root)
{
//二叉树维空的时候
if(root == NULL)
return 0;
if(root->_left == NULL && root->_right == NULL)
return 1;
return _leaf_size(root->_left) + _leaf_size(root->_right);
}
//求二叉树的高度
size_t height()
{
return _height(_root);
}
size_t _height(node *root)
{
if(root == NULL)
return 0;
size_t left_height = _height(root->_left);
size_t right_height = _height(root->_right);
return left_height > right_height? left_height + 1 : right_height + 1;
}
size_t get_k_level(size_t k)
{
return _get_k_level(_root, k);
}
//求第k层的节点个数
size_t _get_k_level(node* root, size_t k)
{
//空树返回0
if(root == NULL)
return 0;
//第一层只有一个节点
if(k == 1)
return 1;
return _get_k_level(root->_left, k - 1) + _get_k_level(root->_right, k - 1);
}
//层序遍历
void level_order()
{
queue<node *> q; //利用队列实现
if(_root)
q.push(_root);
while(!q.empty())
{
node* front = q.front();
cout << front->_data << " ";
q.pop();
if(front->_left)
q.push(front->_left);
if(front->_right)
q.push(front->_right);
}
cout << endl;
}
//判断二叉树是否为完全二叉树
bool is_complete_tree()
{
queue<node *> q;
if(_root)
q.push(_root);
bool flag = true;
while(!q.empty())
{
node *front = q.front();
q.pop();
if(front->_left)
{
if(flag == false)
return false;
q.push(front->_left);
}
else
{
flag = false;
}
if(front->_right)
{
if(flag == false)
return false;
q.push(front->_right);
}
else
flag = false;
}
return true;
}
//查找一个节点是否在一棵二叉树中，递归实现
node* find(const T &x)
{
return _find(_root, x);
}
node* _find(node* root, const T& x)
{
if(root == NULL)
return root;
if(x == root->_data)
{
cout << "find" << endl;
return root;
}
if(x < root->_data)
return _find(root->_left, x);
else
return _find(root->_right, x);
}
//查找(迭代实现)
//输入：待查找的关键字x
//输出：指向关键字为x 的指针(若存在， 否则输出ULL)
node* iterative_Tree_Search(const T& x)
{
return _iterative_Tree_Search(_root, x);
}
node* _iterative_Tree_Search(node* root, const T& x)
{
while(root != NULL)
{
if(x == root->_data)
{
cout << "find" << endl;
break;
}
else if(x < root->_data)
root = root->_left;
else
root = root->_right;
}
return root;
}
//二叉树的插入
void insert(const T &x)
{
bool found = false;
node *p = _root, *q;
while((p) && (!found))//找到了就不进入循环
{
q = p;
if(x == p->_data)
found = true;
else if(x < p->_data)
p = p->_left;
else
{
p = p->_right;
}
}
//插入操作
if(!found)
{
p = new node(x);
p->_left = NULL;
p->_right = NULL;
p->_data = x;
if(_root)
{
if(x < (q->_data))
q->_left = p;
else
q->_right = p;
}
else
{
_root = p;
}
}
}
//二叉树的翻转
node* revBiTree()
{
return _revBiTree(_root);
}
node* _revBiTree(node *pRoot)
{
if(pRoot == NULL)
{
return NULL;
}
node* leftp = _revBiTree(pRoot->_left);
node* rightp = _revBiTree(pRoot->_right);
pRoot->_left = rightp;
pRoot->_right = leftp;
return pRoot;
}
//找到最小的节点
node* FindMin(node* root)
{
while(root->_left != NULL)
root = root->_left;
return root;
}
//节点删除
node* Delete(int data)
{
return _Delete(_root, data);
}
node* _Delete(node* root, int data)
{
if(root == nullptr)
return root;
else if(data < root->_data)
{
root->_left = _Delete(root->_left, data);
}
else if(data > root->_data)
{
root->_right = _Delete(root->_right, data);
}
else
{
//case 1: No child
if(root->_left == NULL && root->_right == NULL)
{
delete root;
root = NULL;
}
//case 2: One child
else if(root->_left == NULL)
{
node* temp = root;
root = root->_right;
delete temp;
}
else if(root->_right == NULL)
{
node* temp = root;
root = root->_left;
delete temp;
}
//case 3: two children
else
{
node *temp = FindMin(root->_right);
root->_data = temp->_data;
root->_right = _Delete(root->_right, temp->_data);
}
}
return root;
}
protected:
node *_root;
};
//测试部分
void test_binary_tree()
{
int array[] = {15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};
binary_tree<int> t(array, sizeof(array) / sizeof(int));
t.prev_order();
t.prev_order_no_r();
t.in_order();
t.in_order_no_r();
t.post_order_no_r();
t.level_order();
cout << endl;
cout << "size:" << t.size() << endl;
cout << "left_size:" << t.leaf_size() << endl;
cout << "height:" << t.height() << endl;
cout << "is_complete_tree:" << t.is_complete_tree() << endl;
cout << "k_level_size:" << t.get_k_level(4) << endl;
binary_tree<int> t1(t);
t1.insert(12);
t1.Delete(13);
t1.prev_order();
t1.revBiTree();
t1.prev_order();
}
int main(int argc, char** argv)
{
test_binary_tree();
system("pause");
return 0;
}
标签： 二叉搜索树
« 上一篇 unordered_map | 队列 下一篇»