二叉树是每个结点最多有两个子树的树结构,即结点的度最大为2。通常子树被称作”左子树”和”右子树”。二叉树是一个连通的无环图。
二叉树是递归定义的,其结点有左右子树之分,逻辑上二叉树有五种基本形态:(1)、空二叉树;(2)、只有一个根结点的二叉树;(3)、只有左子树;(4)、只有右子树;(5)、完全二叉树。
二叉树类型:
(1)、满二叉树:深度(层数)为k,且有2^k-1个结点的二叉树。这种树的特点是每一层上的结点数都是最大结点数。即除了叶结点外每一个结点都有左右子树且叶节点都处在最低层。
(2)、完全二叉树:除最后一层外,其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,即叶子结点都是从左到右依次排布。具有n个节点的完全二叉树的深度为floor(log(2n))+1。深度为k的完全二叉树,至少有2^(k-1)个结点,至多有(2^k)-1个结点。
(3)、平衡二叉树:又被称为AVL树,它是一颗二叉排序树,且具有以下性质:它是一颗空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一颗平衡二叉树。
(4)、斜树:所有的结点都只有左子树(左斜树),或者只有右子树(右斜树)。
(5)、二叉搜素树(或二叉排序树):特殊的二叉树,每个结点都不比它左子树的任意元素小,而且不比它的右子树的任意元素大。二叉搜索树的左右子树也都是二叉搜索树。按中序遍历,则会得到按升序排列的有序数据集。
二叉树不是树的一种特殊情形。
遍历二叉树:按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。对一颗二叉树的遍历有四种情况:先序遍历、中序遍历、后序遍历、按层遍历。
(1)、先序遍历:先访问根结点,再先序遍历左子树,最后再先序遍历右子树,即先访问根结点-------左子树------右子树。
(2)、中序遍历:先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树,即先访问左子树------根结点------右子树。
(3)、后序遍历:先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点,即先访问左子树------右子树------根结点。
(4)、按层遍历:从上到下,从左到右依次访问结点。
下面代码是二叉搜索树的实现,主要包括树的创建、插入、删除、查找、遍历、保存、载入。
binary_search_tree.hpp:
#ifndef FBC_CPPBASE_TEST_BINARY_SEARCH_TREE_HPP_
#define FBC_CPPBASE_TEST_BINARY_SEARCH_TREE_HPP_
#include <vector>
#include <fstream>
#include <string>
namespace binary_search_tree_ {
typedef struct info {
int id; // suppose id is unique
std::string name;
int age;
std::string addr;
} info;
typedef struct node {
info data;
node* left = nullptr;
node* right = nullptr;
} node;
class BinarySearchTree {
public:
BinarySearchTree() = default;
~BinarySearchTree() { DeleteTree(tree); }
typedef std::tuple<int, int, std::string, int, std::string> row; // flag(-1: no node, 0: have a node), id, name, age, addr
int Init(const std::vector<info>& infos); // create binary search tree
bool Search(int id, info& data) const;
int Insert(const info& data);
int Delete(int id); // delete a node
int Traversal(int type) const; // 0: pre-order, 1: in-order, 2: post-order, 3: level
int GetMaxDepth() const; // get tree max depth
int GetMinDepth() const; // get tree min depth
int GetNodesCount() const; // get tree node count
bool IsBinarySearchTree() const; // whether or not is a binary search tree
//bool IsBinaryBalanceTree() const; // whether ot not is a binary balance tree
int GetMinValue(info& data) const;
int GetMaxValue(info& data) const;
int SaveTree(const char* name) const; // tree write in txt file
int LoadTree(const char* name);
protected:
void PreorderTraversal(const node* ptr) const;
void InorderTraversal(const node* ptr) const;
void PostorderTraversal(const node* ptr) const;
void LevelTraversal(const node* ptr) const;
void LevelTraversal(const node* ptr, int level) const;
void DeleteTree(node* ptr);
void Insert(node* ptr, const info& data);
const node* Search(const node* ptr, int id) const;
void IsBinarySearchTree(const node* ptr, bool is_bst) const;
int GetNodesCount(const node* ptr) const;
int GetMaxDepth(const node* ptr) const;
int GetMinDepth(const node* ptr) const;
//bool IsBinaryBalanceTree(const node* ptr) const;
node* Delete(node* ptr, int id); // return new root
node* GetMinValue(node* ptr);
void NodeToRow(const node* ptr, std::vector<row>& rows, int pos) const;
void RowToNode(node* ptr, const std::vector<row>& rows, int n, int pos);
private:
node* tree = nullptr;
bool flag;
};
int test_binary_search_tree();
} // namespace binary_search_tree_
#endif // FBC_CPPBASE_TEST_BINARY_SEARCH_TREE_HPP_
binary_search_tree.cpp:
#include "binary_search_tree.hpp"
#include <set>
#include <iostream>
#include <limits>
#include <tuple>
#include <string>
#include <sstream>
#include <string.h>
#include <algorithm>
namespace binary_search_tree_ {
int BinarySearchTree::Init(const std::vector<info>& infos)
{
std::vector<int> ids;
for (const auto& info : infos) {
ids.emplace_back(info.id);
}
std::set<int> id_set(ids.cbegin(), ids.cend());
if (id_set.size() != ids.size()) {
fprintf(stderr, "id must be unique\n");
return -1;
}
for (const auto& info : infos) {
Insert(info);
}
return 0;
}
bool BinarySearchTree::Search(int id, info& data) const
{
const node* root = tree;
const node* tmp = Search(root, id);
if (tmp) {
data = tmp->data;
return true;
} else {
return false;
}
}
const node* BinarySearchTree::Search(const node* ptr, int id) const
{
if (ptr) {
if (ptr->data.id == id) {
return ptr;
} else if (ptr->data.id > id) {
return Search(ptr->left, id);
} else {
return Search(ptr->right, id);
}
} else {
return nullptr;
}
}
int BinarySearchTree::Insert(const info& data)
{
flag = true;
if (tree) {
Insert(tree, data);
} else {
tree = new node;
tree->data = data;
tree->left = nullptr;
tree->right = nullptr;
}
return (int)flag;
}
void BinarySearchTree::Insert(node* ptr, const info& data)
{
if (ptr->data.id == data.id) {
flag = false;
return;
}
if (ptr->data.id < data.id) {
if (ptr->right) {
Insert(ptr->right, data);
} else {
ptr->right = new node;
ptr->right->data = data;
ptr->right->left = nullptr;
ptr->right->right = nullptr;
}
} else {
if (ptr->left) {
Insert(ptr->left, data);
} else {
ptr->left = new node;
ptr->left->data = data;
ptr->left->left = nullptr;
ptr->left->right = nullptr;
}
}
}
bool BinarySearchTree::IsBinarySearchTree() const
{
bool is_bst = true;
const node* root = tree;
IsBinarySearchTree(root, is_bst);
return is_bst;
}
void BinarySearchTree::IsBinarySearchTree(const node* ptr, bool is_bst) const
{
static int last_data = std::numeric_limits<int>::min();
if (!ptr) return;
IsBinarySearchTree(ptr->left, is_bst);
if (last_data < ptr->data.id) last_data = ptr->data.id;
else {
is_bst = false;
return;
}
IsBinarySearchTree(ptr->right, is_bst);
}
int BinarySearchTree::Traversal(int type) const
{
if (!tree) {
fprintf(stderr, "Error: it is an empty tree\n");
return -1;
}
const node* root = tree;
if (type == 0)
PreorderTraversal(root);
else if (type == 1)
InorderTraversal(root);
else if (type == 2)
PostorderTraversal(root);
else if (type == 3)
LevelTraversal(root);
else {
fprintf(stderr, "Error: don't suppot traversal type, type only support: 0: pre-order, 1: in-order, 2: post-order\n");
return -1;
}
return 0;
}
void BinarySearchTree::PreorderTraversal(const node* ptr) const
{
if (ptr) {
fprintf(stdout, "Info: id: %d, name: %s, age: %d, addr: %s\n",
ptr->data.id, ptr->data.name.c_str(), ptr->data.age, ptr->data.addr.c_str());
PreorderTraversal(ptr->left);
PreorderTraversal(ptr->right);
}
}
void BinarySearchTree::InorderTraversal(const node* ptr) const
{
if (ptr) {
InorderTraversal(ptr->left);
fprintf(stdout, "Info: id: %d, name: %s, age: %d, addr: %s\n",
ptr->data.id, ptr->data.name.c_str(), ptr->data.age, ptr->data.addr.c_str());
InorderTraversal(ptr->right);
}
}
void BinarySearchTree::PostorderTraversal(const node* ptr) const
{
if (ptr) {
PostorderTraversal(ptr->left);
PostorderTraversal(ptr->right);
fprintf(stdout, "Info: id: %d, name: %s, age: %d, addr: %s\n",
ptr->data.id, ptr->data.name.c_str(), ptr->data.age, ptr->data.addr.c_str());
}
}
void BinarySearchTree::LevelTraversal(const node* ptr) const
{
int h = GetMaxDepth();
for (int i = 1; i <= h; ++i)
LevelTraversal(ptr, i);
}
void BinarySearchTree::LevelTraversal(const node* ptr, int level) const
{
if (!ptr) return;
if (level == 1)
fprintf(stdout, "Info: id: %d, name: %s, age: %d, addr: %s\n",
ptr->data.id, ptr->data.name.c_str(), ptr->data.age, ptr->data.addr.c_str());
else if (level > 1) {
LevelTraversal(ptr->left, level-1);
LevelTraversal(ptr->right, level-1);
}
}
void BinarySearchTree::DeleteTree(node* ptr)
{
if (ptr) {
DeleteTree(ptr->left);
DeleteTree(ptr->right);
delete ptr;
}
}
int BinarySearchTree::GetNodesCount() const
{
const node* root = tree;
return GetNodesCount(root);
}
int BinarySearchTree::GetNodesCount(const node* ptr) const
{
if (!ptr) return 0;
else return GetNodesCount(ptr->left) + 1 + GetNodesCount(ptr->right);
}
int BinarySearchTree::GetMaxDepth() const
{
const node* root = tree;
return GetMaxDepth(root);
}
int BinarySearchTree::GetMaxDepth(const node* ptr) const
{
if (!ptr) return 0;
int left_depth = GetMaxDepth(ptr->left);
int right_depth = GetMaxDepth(ptr->right);
return std::max(left_depth, right_depth) + 1;
}
int BinarySearchTree::GetMinDepth() const
{
const node* root = tree;
return GetMinDepth(root);
}
int BinarySearchTree::GetMinDepth(const node* ptr) const
{
if (!ptr) return 0;
int left_depth = GetMaxDepth(ptr->left);
int right_depth = GetMaxDepth(ptr->right);
return std::min(left_depth, right_depth) + 1;
}
/*bool BinarySearchTree::IsBinaryBalanceTree() const
{
const node* root = tree;
return IsBinaryBalanceTree(root);
}
bool BinarySearchTree::IsBinaryBalanceTree(const node* ptr) const
{
// TODO: code need to modify
if (GetMaxDepth(ptr) - GetMinDepth(ptr) <= 1) return true;
else return false;
}*/
int BinarySearchTree::GetMinValue(info& data) const
{
if (!tree) {
fprintf(stderr, "Error: it is a empty tree\n");
return -1;
}
const node* root = tree;
while (root->left) root = root->left;
data = root->data;
return 0;
}
int BinarySearchTree::GetMaxValue(info& data) const
{
if (!tree) {
fprintf(stderr, "Error: it is a empty tree\n");
return -1;
}
const node* root = tree;
while (root->right) root = root->right;
data = root->data;
return 0;
}
int BinarySearchTree::Delete(int id)
{
if (!tree) {
fprintf(stderr, "Error: it is a empty tree\n");
return -1;
}
const node* root = tree;
const node* ret = Search(root, id);
if (!ret) {
fprintf(stdout, "Warning: this id don't exist in the tree: %d", id);
return 0;
}
tree = Delete(tree, id);
return 0;
}
node* BinarySearchTree::GetMinValue(node* ptr)
{
node* tmp = ptr;
while (tmp->left) tmp = tmp->left;
return tmp;
}
node* BinarySearchTree::Delete(node* ptr, int id)
{
if (!ptr) return ptr;
if (id < ptr->data.id)
ptr->left = Delete(ptr->left, id);
else if (id > ptr->data.id)
ptr->right = Delete(ptr->right, id);
else {
if (!ptr->left) {
node* tmp = ptr->right;
delete ptr;
return tmp;
} else if (!ptr->right) {
node* tmp = ptr->left;
delete ptr;
return tmp;
}
node* tmp = GetMinValue(ptr->right);
ptr->data = tmp->data;
ptr->right = Delete(ptr->right, tmp->data.id);
}
return ptr;
}
int BinarySearchTree::SaveTree(const char* name) const
{
std::ofstream file(name, std::ios::out);
if (!file.is_open()) {
fprintf(stderr, "Error: open file fail: %s\n", name);
return -1;
}
const node* root = tree;
int max_depth = GetMaxDepth(root);
int max_nodes = (1 << max_depth) -1;
root = tree;
int nodes_count = GetNodesCount(root);
//fprintf(stdout, "max_depth: %d, max nodes: %d\n", max_depth, max_nodes);
file<<nodes_count<<","<<max_depth<<std::endl;
std::vector<row> vec(max_nodes, std::make_tuple(-1, -1, " ", -1, " "));
root = tree;
NodeToRow(root, vec, 0);
for (const auto& v : vec) {
file << std::get<0>(v)<<","<<std::get<1>(v)<<","<<std::get<2>(v)<<","<<std::get<3>(v)<<","<<std::get<4>(v)<<std::endl;
}
file.close();
return 0;
}
void BinarySearchTree::NodeToRow(const node* ptr, std::vector<row>& rows, int pos) const
{
if (!ptr) return;
rows[pos] = std::make_tuple(0, ptr->data.id, ptr->data.name, ptr->data.age, ptr->data.addr);
if (ptr->left) NodeToRow(ptr->left, rows, 2 * pos + 1);
if (ptr->right) NodeToRow(ptr->right, rows, 2 * pos + 2);
}
int BinarySearchTree::LoadTree(const char* name)
{
std::ifstream file(name, std::ios::in);
if (!file.is_open()) {
fprintf(stderr, "Error: open file fail: %s\n", name);
return -1;
}
std::string line, cell;
std::getline(file, line);
std::stringstream line_stream(line);
std::vector<int> vec;
while (std::getline(line_stream, cell, ',')) {
vec.emplace_back(std::stoi(cell));
}
if (vec.size() != 2) {
fprintf(stderr, "Error: parse txt file fail\n");
return -1;
}
fprintf(stdout, "nodes count: %d, max depth: %d\n", vec[0], vec[1]);
int max_nodes = (1 << vec[1]) - 1;
std::vector<row> rows;
while (std::getline(file, line)) {
std::stringstream line_stream2(line);
std::vector<std::string> strs;
while (std::getline(line_stream2, cell, ',')) {
strs.emplace_back(cell);
}
if (strs.size() != 5) {
fprintf(stderr, "Error: parse line fail\n");
return -1;
}
row tmp = std::make_tuple(std::stoi(strs[0]), std::stoi(strs[1]), strs[2], std::stoi(strs[3]), strs[4]);
rows.emplace_back(tmp);
}
if (rows.size() != max_nodes || std::get<0>(rows[0]) == -1) {
fprintf(stderr, "Error: parse txt file line fail\n");
return -1;
}
node* root = new node;
root->data = {std::get<1>(rows[0]), std::get<2>(rows[0]), std::get<3>(rows[0]), std::get<4>(rows[0])};
root->left = nullptr;
root->right = nullptr;
tree = root;
RowToNode(root, rows, max_nodes, 0);
file.close();
return 0;
}
void BinarySearchTree::RowToNode(node* ptr, const std::vector<row>& rows, int n, int pos)
{
if (!ptr || n == 0) return;
int new_pos = 2 * pos + 1;
if (new_pos < n && std::get<0>(rows[new_pos]) != -1) {
ptr->left = new node;
ptr->left->data = {std::get<1>(rows[new_pos]), std::get<2>(rows[new_pos]), std::get<3>(rows[new_pos]), std::get<4>(rows[new_pos])};
ptr->left->left = nullptr;
ptr->left->right = nullptr;
RowToNode(ptr->left, rows, n, new_pos);
}
new_pos = 2 * pos + 2;
if (new_pos < n && std::get<0>(rows[new_pos]) != -1) {
ptr->right = new node;
ptr->right->data = {std::get<1>(rows[new_pos]), std::get<2>(rows[new_pos]), std::get<3>(rows[new_pos]), std::get<4>(rows[new_pos])};
ptr->right->left = nullptr;
ptr->right->right = nullptr;
RowToNode(ptr->right, rows, n, new_pos);
}
}
int test_binary_search_tree()
{
fprintf(stdout, "create binary search tree:\n");
std::vector<info> infos{{1004, "Tom", 8, "Beijing"}, {1005, "Jack", 9, "Tianjin"}, {1003, "Mark", 6, "Hebei"}, {1009, "Lisa", 11, "Beijiing"}, {1007, "Piter", 4, "Hebei"}, {1001, "Viner", 6, "Beijing"}};
BinarySearchTree bstree;
bstree.Init(infos);
fprintf(stdout, "\ninsert operation:\n");
std::vector<info> infos2{{1007, "xxx", 11, "yyy"}, {1008, "Lorena", 22, "Hebie"}, {1002, "Eillen", 14, "Shanxi"}};
for (const auto& info : infos2) {
int flag = bstree.Insert(info);
if (flag) fprintf(stdout, "insert success\n");
else fprintf(stdout, "Warning: id %d already exists, no need to insert\n", info.id);
}
fprintf(stdout, "\ntraversal operation:\n");
fprintf(stdout, "pre-order traversal:\n");
bstree.Traversal(0);
fprintf(stdout, "in-order traversal:\n");
bstree.Traversal(1);
fprintf(stdout, "post-order traversal:\n");
bstree.Traversal(2);
fprintf(stdout, "level traversal:\n");
bstree.Traversal(3);
fprintf(stdout, "\nsearch operation:\n");
std::vector<int> ids {1009, 2000};
for (auto id : ids) {
info ret;
bool flag = bstree.Search(id, ret);
if (flag)
fprintf(stdout, "found: info: %d, %s, %d, %s\n", ret.id, ret.name.c_str(), ret.age, ret.addr.c_str());
else
fprintf(stdout, "no find: no id info: %d\n", id);
}
fprintf(stdout, "\nwhether or not is a binary search tree operation:\n");
bool flag2 = bstree.IsBinarySearchTree();
if (flag2) fprintf(stdout, "it is a binary search tree\n");
else fprintf(stdout, "it is not a binary search tree\n");
fprintf(stdout, "\ncalculate node count operation:\n");
int count = bstree.GetNodesCount();
fprintf(stdout, "tree node count: %d\n", count);
fprintf(stdout, "\ncalculate tree depth operation:\n");
int max_depth = bstree.GetMaxDepth();
int min_depth = bstree.GetMinDepth();
fprintf(stdout, "tree max depth: %d, min depth: %d\n", max_depth, min_depth);
/*fprintf(stdout, "\nwhether or not is a binary balance tree operation:\n");
flag2 = bstree.IsBinaryBalanceTree();
if (flag2) fprintf(stdout, "it is a binary balance tree\n");
else fprintf(stdout, "it is not a binary balance tree\n");*/
fprintf(stdout, "\nget min and max value(id):\n");
info value;
bstree.GetMinValue(value);
fprintf(stdout, "tree min value: id: %d\n", value.id);
bstree.GetMaxValue(value);
fprintf(stdout, "tree max value: id: %d\n", value.id);
fprintf(stdout, "\ndelete node operation:\n");
bstree.Delete(1005);
bstree.Traversal(1);
fprintf(stdout, "\nsave tree operation:\n");
#ifdef _MSC_VER
char* name = "E:/GitCode/Messy_Test/testdata/binary_search_tree.model";
#else
char* name = "testdata/binary_search_tree.model";
#endif
bstree.SaveTree(name);
fprintf(stdout, "\nload tree operation:\n");
BinarySearchTree bstree2;
bstree2.LoadTree(name);
int count2 = bstree2.GetNodesCount();
int max_depth2 = bstree2.GetMaxDepth();
int min_depth2 = bstree2.GetMinDepth();
fprintf(stdout, "tree node count: %d, tree max depth: %d, min depth: %d\n", count2, max_depth2, min_depth2);
bstree2.Traversal(1);
return 0;
}
} // namespace binary_search_tree_
支持Linux和Windows直接编译,Windows通过VS,linux下执行prj/linux_cmake_CppBaseTest/build.sh脚本。执行结果如下:
保存的binary_search_tree.model结果如下:
7,4
0,1004,Tom,8,Beijing
0,1003,Mark,6,Hebei
0,1009,Lisa,11,Beijiing
0,1001,Viner,6,Beijing
-1,-1, ,-1,
0,1007,Piter,4,Hebei
-1,-1, ,-1,
-1,-1, ,-1,
0,1002,Eillen,14,Shanxi
-1,-1, ,-1,
-1,-1, ,-1,
-1,-1, ,-1,
0,1008,Lorena,22,Hebie
-1,-1, ,-1,
-1,-1, ,-1,