C++ binary tree (create, destroy, pre-middle and post-order traversal and hierarchical traversal, find parent nodes, etc.)

(1)Structure and class definition

struct BTreeNode {
T data;
BTreeNode* left, * right;
BTreeNode() : data(0), left(nullptr), right(nullptr) {}
BTreeNode(T val, BTreeNode<T>* leftChild = nullptr, BTreeNode<T>* rightChild = nullptr)
:data(val), left(leftChild), right(rightChild) {}

};

template<class T>
class BTree {
public:
BTree() :root(nullptr) {} // constructor
BTree(string str); // overload

void createTree(BTreeNode<T>* & amp; bt, string str); // create secondary tree
~BTree(); // destructor
bool IsEmpty(); // Judge whether the binary tree is empty?
int Size(BTreeNode<T>* cur); // Calculate the number of nodes
int getSize(); // Get the number of nodes
BTreeNode<T>* getData(T & amp; item, BTreeNode<T>* cur); // get node data
bool Find(T & amp; item); // Determine whether the item is in the tree
int Height(BTreeNode<T>* bt); // find tree height
int getHeight(); // get tree height
BTreeNode<T>* getRoot(); // get the root

void preOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec); // Preorder traversal
void inOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec); // in-order traversal
void postOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec); // post-order traversal
void levelOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec); // Level order traversal

vector<T> preOrder(); // Call preorder traversal and return vector
vector<T> inOrder(); // Call in-order traversal and return vector
vector<T> postOrder(); // Call post-order traversal and return vector
vector<T> levelOrder(); // Call level order traversal and return vector

void CopyTree(BTreeNode<T>* root, BTreeNode<T>* & amp; copyRoot); // Binary tree copy
void Copy(BTreeNode<T>* & amp; copyRoot); // Call binary tree copy
void destroyCopyTree(BTreeNode<T>* & amp; copyRoot); // Destroy the copied binary tree


BTreeNode<T>* FindParent(BTreeNode<T>* root, BTreeNode<T>* node); // Find parents
BTreeNode<T>* LeftChild(BTreeNode<T>* node) { //Find the left child of node node
return (node != nullptr) ? node->left : nullptr;
}
BTreeNode<T>* RightChild(BTreeNode<T>* node) { //Find the right child of node node
return (node != nullptr) ? node->right : nullptr;
}

protected:
BTreeNode<T>* root;
void destroyTree(BTreeNode<T>* node); // Destroy the binary tree
};

(2) Create a binary tree

template<class T>
BTree<T>::BTree(string str) {
createTree(root, str);
cout << "Report: Create a binary tree, completed!!!" << endl;
}

template<class T>
void BTree<T>::createTree(BTreeNode<T>* & bt, string str) {
static int i = 0;
char ch = ' ';
ch = str[i + + ];

if (ch == '#') bt = nullptr;
else {
bt = new BTreeNode<T>(ch);
createTree(bt->left, str);
createTree(bt->right, str);
}
};

(3) Front-middle-back order traversal and layer order traversal

// Preorder traversal
template<class T>
void BTree<T>::preOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec) {
if (cur == nullptr)
return;
vec.push_back(cur->data); // Medium
preOrderTraversal(cur->left, vec); // left
preOrderTraversal(cur->right, vec); // right
}

// call preorder traversal, return vector
template<class T>
vector<T> BTree<T>::preOrder() {
cout << "Get preorder traversal array...." << endl;
cout << ">>>>";
vector<T> resVec;
preOrderTraversal(root, resVec);
return resVec;
}

// inorder traversal
template<class T>
void BTree<T>::inOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec) {
if (cur == nullptr)
return;
inOrderTraversal(cur->left, vec); // left
vec.push_back(cur->data); // Medium
inOrderTraversal(cur->right, vec); // right
}

// Call in-order traversal and return vector
template<class T>
vector<T> BTree<T>::inOrder() {
cout << "Get the in-order traversal array...." << endl;
cout << ">>>>";
vector<T> resVec;
inOrderTraversal(root, resVec);
return resVec;
}

// Post-order traversal
template<class T>
void BTree<T>::postOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec) {
if (cur == nullptr)
return;
postOrderTraversal(cur->left, vec); // left
postOrderTraversal(cur->right, vec); // right
vec.push_back(cur->data); // Medium
}

// Call post-order traversal and return vector
template<class T>
vector<T> BTree<T>::postOrder() {
cout << "Get the post-order traversal array...." << endl;
cout << ">>>>";
vector<T> resVec;
postOrderTraversal(root, resVec);
return resVec;
}

//Level-order traversal
template<class T>
void BTree<T>::levelOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec) {
if (cur == nullptr) return;
queue<BTreeNode<T>*> Queue;
BTreeNode<T>* p;
Queue.push(cur); // root node into the queue
while (!Queue. empty()) {
p = Queue.front();
//cout << p->data << " ";//Output the data of the dequeue node
vec.push_back(p->data);
Queue.pop();
if (p->left != nullptr) {
Queue.push(p->left);
}
if (p->right != nullptr) {
Queue.push(p->right);
}
}
}

// Call layer sequence traversal, return vector
template<class T>
vector<T> BTree<T>::levelOrder() {
cout << "Get layer sequence traversal array...." << endl;
cout << ">>>>";
vector<T> resVec;
levelOrderTraversal(root, resVec);
return resVec;
}

(4) Copy binary tree

template<class T>
void BTree<T>::CopyTree(BTreeNode<T>* root, BTreeNode<T>* & amp; copyRoot) {
if (!root) {
copyRoot = nullptr;
}
else {
copyRoot = new BTreeNode<T>;
copyRoot->data = root->data; //Copy the root node
CopyTree(root->left, copyRoot->left); //Recursively copy the left subtree
CopyTree(root->right, copyRoot->right);//Recursively copy the left subtree
}
}

template<class T>
void BTree<T>::Copy(BTreeNode<T>* & amp; copyRoot) {
CopyTree(root, copyRoot);
}

(5) Destroy binary tree

template<class T>
void BTree<T>::destroyCopyTree(BTreeNode<T>* & amp; copyRoot) {
destroyTree(copyRoot);
cout << "Report that the copied binary tree has been destroyed!!!" << endl;
}

// Destroy the binary tree
template<class T>
void BTree<T>::destroyTree(BTreeNode<T>* bt) {
// Post-order traversal deletes the subtree whose root is subTree;
if (bt != nullptr) {
destroyTree(bt->left); //Delete left subtree
destroyTree(bt->right); //Delete the right subtree
delete bt; //Delete the root node
}
}

(6) Destructor

// destructor
template<class T>
BTree<T>::~BTree<T>() {
//cout << "Call destructor" << endl;
destroyTree(root);
cout << "Report, this tree has been destroyed!!!" << endl;
}

(7) Find the height of the tree

// Find the height of the tree
template<class T>
int BTree<T>::Height(BTreeNode<T>* bt) {
if (bt == nullptr) return 0;
else {
int leftH = Height(bt->left);
int rightH = Height(bt->right);
return (leftH > rightH) ? leftH + 1 : rightH + 1;
}
}

// Get the tree height
template<class T>
int BTree<T>::getHeight() {
return Height(root);
}

(8) Get the node and determine whether it is in the binary tree

//Get node data
template<class T>
BTreeNode<T>* BTree<T>::getData(T & amp; item, BTreeNode<T>* cur) {
if (cur == nullptr) return nullptr;
if (cur->data == item) return cur;
return getData(item, cur->left) != nullptr ? getData(item, cur->left) : getData(item, cur->right);
}

// Determine whether the item is in the tree
template<class T>
bool BTree<T>::Find(T & amp; item) {
if (this->getData(item, root) == nullptr) return false;
else return true;

(9) Calculate the number of nodes and obtain the number of nodes

// Calculate the number of nodes
template<class T>
int BTree<T>::Size(BTreeNode<T>* cur) {
if (cur == nullptr)
return 0;
else
return 1 + Size(cur->left) + Size(cur->right);
}

// Get the number of nodes
template<class T>
int BTree<T>::getSize() {
return Size(root);
}

(10) Binary tree empty judgment

//Check whether the binary tree is empty?
template<class T>
bool BTree<T>::IsEmpty() {
return (root == nullptr) ? true : false;
}

(11) Get the root node

// Get the root
template<class T>
BTreeNode<T>* BTree<T>::getRoot() {
if (!root) return nullptr;
else {
return this->root;
}
}

Source code:

btree.h

#pragma once
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

template<class T>
struct BTreeNode {
T data;
BTreeNode* left, * right;
BTreeNode() :data(0), left(nullptr), right(nullptr) {}
BTreeNode(T val, BTreeNode<T>* leftChild = nullptr, BTreeNode<T>* rightChild = nullptr)
:data(val), left(leftChild), right(rightChild) {}

};

template<class T>
class BTree {
public:
BTree() :root(nullptr) {} // Constructor
BTree(string str); // Overload

void createTree(BTreeNode<T>* & amp; bt, string str); // Create a quadratic tree
~BTree(); // destructor
bool IsEmpty(); // Is the binary tree empty?
int Size(BTreeNode<T>* cur); // Calculate the number of nodes
int getSize(); // Get the number of nodes
BTreeNode<T>* getData(T & amp; item, BTreeNode<T>* cur); // Get node data
bool Find(T & amp; item); // Determine whether item is in the tree
int Height(BTreeNode<T>* bt); // Find the tree height
int getHeight(); // get tree height
BTreeNode<T>* getRoot(); // get the root

void preOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec); // preorder traversal
void inOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec); // in-order traversal
void postOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec); // post-order traversal
void levelOrderTraversal(BTreeNode<T>* cur, vector<int> & amp; vec); // level order traversal

vector<T> preOrder(); // call preorder traversal, return vector
vector<T> inOrder(); // call inorder traversal, return vector
vector<T> postOrder(); // call post-order traversal, return vector
vector<T> levelOrder(); // call level order traversal, return vector

void CopyTree(BTreeNode<T>* root, BTreeNode<T>* & amp; copyRoot); // binary tree copy
void Copy(BTreeNode<T>* & amp; copyRoot); // call binary tree copy
void destroyCopyTree(BTreeNode<T>* & amp; copyRoot); // destroy copy binary tree


BTreeNode<T>* FindParent(BTreeNode<T>* root, BTreeNode<T>* node); // find parents
BTreeNode<T>* LeftChild(BTreeNode<T>* node) { // Find the left child of node node
return (node != nullptr) ? node->left : nullptr;
}
BTreeNode<T>* RightChild(BTreeNode<T>* node) { // Find the right child of node node
return (node != nullptr) ? node->right : nullptr;
}

protected:
BTreeNode<T>* root;
void destroyTree(BTreeNode<T>* node); // destroy binary tree
};

btree.cpp

// Every time you write recursion, write according to these three elements, which can ensure that everyone writes the correct recursive algorithm!
// 1. Determine the return value of the parameter of the recursive function
// 2. Determine the termination conditions
// 3. Determine the logic of single-level recursion

#include "btree.h"

template
BTree::BTree(string str) {
createTree(root, str);
cout << "Report: Create a binary tree, complete!!!" << endl;
}

template
void BTree::createTree(BTreeNode* & bt, string str) {
static int i = 0;
char ch = ' ';
ch = str[i + + ];

if (ch == '#') bt = nullptr;
else {
bt = new BTreeNode(ch);
createTree(bt->left, str);
createTree(bt->right, str);
}
};

// Check whether the binary tree is empty?
template
bool BTree::IsEmpty() {
return (root == nullptr) ? true : false;
}

// Calculate the number of nodes
template<class T>
int BTree<T>::Size(BTreeNode<T>* cur) {
if (cur == nullptr)
return 0;
else
return 1 + Size(cur->left) + Size(cur->right);
}

// Get the number of nodes
template<class T>
int BTree<T>::getSize() {
return Size(root);
}

//Get node data
template<class T>
BTreeNode<T>* BTree<T>::getData(T & amp; item, BTreeNode<T>* cur) {
if (cur == nullptr) return nullptr;
if (cur->data == item) return cur;
return getData(item, cur->left) != nullptr ? getData(item, cur->left) : getData(item, cur->right);
}

// Determine whether the item is in the tree
template<class T>
bool BTree<T>::Find(T & amp; item) {
if (this->getData(item, root) == nullptr) return false;
else return true;
}

// Find the height of the tree
template
int BTree::Height(BTreeNode* bt) {
if (bt == nullptr) return 0;
else {
int leftH = Height(bt->left);
int rightH = Height(bt->right);
return (leftH > rightH) ? leftH + 1 : rightH + 1;
}
}

// get tree height
template
int BTree::getHeight() {
return Height(root);
}

// Get the root
template<class T>
BTreeNode<T>* BTree<T>::getRoot() {
if (!root) return nullptr;
else {
return this->root;
}
}

// destructor
template
BTree::~BTree() {
//cout << "Call destructor" << endl;
destroyTree(root);
cout << "Report, the tree has been destroyed!!!" << endl;
}

// destroy the binary tree
template
void BTree::destroyTree(BTreeNode* bt) {
// Post-order traversal deletes the subtree whose root is subTree;
if (bt != nullptr) {
destroyTree(bt->left); //Delete left subtree
destroyTree(bt->right); //Delete the right subtree
delete bt; //Delete the root node
}
}

// preorder traversal
template
void BTree::preOrderTraversal(BTreeNode* cur, vector & amp; vec) {
if (cur == nullptr)
return;
vec.push_back(cur->data); // Medium
preOrderTraversal(cur->left, vec); // left
preOrderTraversal(cur->right, vec); // right
}

//Call preorder traversal and return vector
template
vector BTree::preOrder() {
cout << "Get the preorder traversal array...." << endl;
cout << ">>>>";
vector resVec;
preOrderTraversal(root, resVec);
return resVec;
}

// inorder traversal
template
void BTree::inOrderTraversal(BTreeNode* cur, vector & amp; vec) {
if (cur == nullptr)
return;
inOrderTraversal(cur->left, vec); // left
vec.push_back(cur->data); // Medium
inOrderTraversal(cur->right, vec); // right
}

// Call in-order traversal and return vector
template
vector BTree::inOrder() {
cout << "Get the in-order traversal array...." << endl;
cout << ">>>>";
vector resVec;
inOrderTraversal(root, resVec);
return resVec;
}

// Post-order traversal
template
void BTree::postOrderTraversal(BTreeNode* cur, vector & amp; vec) {
if (cur == nullptr)
return;
postOrderTraversal(cur->left, vec); // left
postOrderTraversal(cur->right, vec); // right
vec.push_back(cur->data); // Medium
}

// call post-order traversal, return vector
template
vector BTree::postOrder() {
cout << "Get post-order traversal array...." << endl;
cout << ">>>>";
vector resVec;
postOrderTraversal(root, resVec);
return resVec;
}

//Level-order traversal
template
void BTree::levelOrderTraversal(BTreeNode* cur, vector & amp; vec) {
if (cur == nullptr) return;
queue*> Queue;
BTreeNode* p;
Queue.push(cur); // root node into the queue
while (!Queue. empty()) {
p = Queue.front();
//cout << p->data << " ";//Output the data of the dequeue node
vec.push_back(p->data);
Queue.pop();
if (p->left != nullptr) {
Queue.push(p->left);
}
if (p->right != nullptr) {
Queue.push(p->right);
}
}
}

// Call layer sequence traversal, return vector
template
vector BTree::levelOrder() {
cout << "Get layer sequence traversal array...." << endl;
cout << ">>>>";
vector resVec;
levelOrderTraversal(root, resVec);
return resVec;
}

template<class T>
void BTree<T>::CopyTree(BTreeNode<T>* root, BTreeNode<T>* & amp; copyRoot) {
if (!root) {
copyRoot = nullptr;
}
else {
copyRoot = new BTreeNode<T>;
copyRoot->data = root->data; //Copy the root node
CopyTree(root->left, copyRoot->left); //Recursively copy the left subtree
CopyTree(root->right, copyRoot->right);//Recursively copy the left subtree
}
}

template<class T>
void BTree<T>::Copy(BTreeNode<T>* & amp; copyRoot) {
CopyTree(root, copyRoot);
}

template
void BTree::destroyCopyTree(BTreeNode* & amp; copyRoot) {
destroyTree(copyRoot);
cout << "Report that the copied binary tree has been destroyed!!!" << endl;
}

template
BTreeNode* BTree::FindParent(BTreeNode* root, BTreeNode* node) {

if (root == nullptr) return nullptr;
if (root->left == node || root->right == node)
return root; //Find, return the parent node address
BTreeNode* p;
if ((p = FindParent(root->left, node)) != nullptr)
return p; //Recursively search in the left subtree
else return FindParent(root->right, node);
}

test.cpp

#include "btree.h"
#include "btree.cpp"
//#include <iostream>
//using namespace std;
int main() {
cout << "-------------------------Start------------------- ------" << endl;
cout << "---------------------Create the original binary tree ---------------------" << endl;
string str = "ABD#G##E##CF###";
BTree<int>* T = new BTree<int>(str);
BTreeNode<int>* root = T->getRoot();
cout << "This tree has " << T->getSize() << " nodes" << endl;

int Zifu = 'G';
if (T->Find(zifu)) {
cout << "This tree has " << (char)zifu << " nodes" << endl;
}
else {
cout << "This tree has no " << (char)zifu << "Node" << endl;
}
BTreeNode<int>* node = T->getData(zifu, root);
if (node) {
cout << (char)node->data << endl;
BTreeNode<int>* nodeParent = T->FindParent(root, node);
if (!nodeParent) {
cout << "Father node not found" << endl;
}
else {
cout << "node " << (char)zifu << " the parent node is: " << (char)nodeParent->data << " node" << endl;
if (nodeParent->left) cout << "My left child is: " << (char)nodeParent->left->data << endl;
else cout << "I have no left child..." << endl;
if (nodeParent->right) cout << "My right child is: " << (char)nodeParent->right->data << endl;
else cout << "I have no right child..." << endl;
}
}
cout << "The height of this tree is: " << T->getHeight() << endl;

vector<int> vec = T->preOrder();
for (auto i : vec) {
cout << (char)i;
}
cout << endl;

vec. clear();
vec = T->inOrder();
for (auto i : vec) {
cout << (char)i;
}
cout << endl;

vec. clear();
vec = T->postOrder();
for (auto i : vec) {
cout << (char)i;
}
cout << endl;

vec. clear();
vec = T->levelOrder();
for (auto i : vec) {
cout << (char)i;
}
cout << endl;


cout << "----------------------- Copy binary tree --------------------- --" << endl;
// Copy the binary tree
//vector<int> vec;
//BTreeNode<int>* root = T->getRoot();
BTreeNode<int>* copyRoot = new BTreeNode<int>;
//T->Copy(copyRoot); // Method 1
T->CopyTree(root, copyRoot); // Method 2

vec.clear();
cout << "Get the preorder traversal array...." << endl;
cout << ">>>>";
T->preOrderTraversal(copyRoot, vec);
for (auto i : vec) {
cout << (char)i;
}
cout << endl;

vec.clear();
cout << "Get the in-order traversal array...." << endl;
cout << ">>>>";
T->inOrderTraversal(copyRoot, vec);
for (auto i : vec) {
cout << (char)i;
}
cout << endl;

vec.clear();
cout << "Get the post-order traversal array...." << endl;
cout << ">>>>";
T->postOrderTraversal(copyRoot, vec);
for (auto i : vec) {
cout << (char)i;
}
cout << endl;

vec.clear();
cout << "Get the level order traversal array...." << endl;
cout << ">>>>";
T->levelOrderTraversal(copyRoot, vec);
for (auto i : vec) {
cout << (char)i;
}
cout << endl;
cout << "---------------------Destroy copy binary tree---------------------" << endl;
T->destroyCopyTree(copyRoot);
cout << "---------------------Destroy the original binary tree---------------------" << endl;
T->~BTree();
cout << "-------------------------End------------------- --------" << endl;
return 0;
}

>>Test results

-------------------------Start--------------------- -----
--------------------- Create the original binary tree ---------------------
Report: Create a binary tree, done! ! !
This tree has 7 nodes
This tree has G nodes
G
The parent node of node G is: node D
I don't have any left children...
My right child is: G
The height of this tree is: 4
Get preorder traversal of array....
>>>>ABDGECF
Get inorder traversal of array....
>>>>DGBEAFC
Get postorder traversal of array....
>>>>GDEBFCA
Get the level-order traversal array....
>>>>ABCDEFG
--------------------Copy Binary Tree-----------------------
Get preorder traversal of array....
>>>>ABDGECF
Get inorder traversal of array....
>>>>DGBEAFC
Get postorder traversal of array....
>>>>GDEBFCA
Get the level-order traversal array....
>>>>ABCDEFG
---------------------Destroy Copy Binary Tree---------------------
Report that the copied binary tree has been destroyed!!!
--------------------- Destroy the original binary tree ---------------------
Report that this tree has been destroyed!!!
--------------------------End----------------------- ----