# C++ implementation of binary tree basic operation details

• 2020-06-01 10:31:25
• OfStack

Tree is an important nonlinear data structure, and two-fork tree is an important type of tree structure. This academic year's paper introduces the definition of two-fork tree, the storage structure of two-fork tree, and the related terms of two-fork tree, so as to introduce the concept of two-fork tree and lay a theoretical foundation for the basic operation of two-fork tree. The basic operation of two-fork tree mainly includes the following modules: the traversal method of two-fork tree, the calculation of the number of nodes of two-fork tree, the calculation of the number of leaf nodes of two-fork tree, and the solution of the depth of two-fork tree.

Preorder traversal (recursion & Non-recursive)

Accessing the root node The preorder accesses the left subtree The preorder accesses the right subtree
``````
// Preorder non-recursive
void PrevOrder()
{
stack<Node*> s;
Node *cur = _root;

while (cur || !s.empty())
{
while (cur)
{
cout << cur->_data << " ";
s.push(cur);
cur = cur->_left;
}
// At this point, the left subtree of the current node has been traversed
Node *tmp = s.top();
s.pop();
cur = tmp->_right;
}
cout << endl;
}

// First order recursive
void PrevOrderR()
{
_PrevOrder(_root);

cout << endl;
}

void _PrevOrder(Node *root)
{
if (root == NULL) // There must be a recursive exit!!
return;

cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}

``````

Middle order traversal (recursion & Non-recursive)

The middle order accesses the left subtree Accessing the root node The middle order accesses the right subtree
``````
// Middle order is not recursive
void InOrder()
{
stack<Node*> s;
Node *cur = _root;

while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
// At this point, the left subtree of the current node has been traversed
Node *tmp = s.top();
cout << tmp->_data << " ";
s.pop();
cur = tmp->_right;
}
cout << endl;
}

// Sequence of recursion
void InOrderR()
{
_InOrder(_root);

cout << endl;
}

void _InOrder(Node *root)
{
if (root == NULL)
return;

_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}

``````

Sequential traversal (recursion & Non-recursive)

``````
// Postorder is not recursive
// Postorder traversal can be a dead loop, so record the front 1 The number of visited nodes
void PostOrder()
{
stack<Node*> s;
Node *cur = _root;
Node *prev = NULL;

while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node *tmp = s.top();
if (tmp->_right && tmp->_right != prev)
{
cur = tmp->_right;
}
else
{
cout << tmp->_data << " ";
prev = tmp;
s.pop();
}
}
cout << endl;
}

// After the sequence of recursion
void PostOrderR()
{
_PostOrder(_root);

cout << endl;
}

void _PostOrder(Node *root)
{
if (root == NULL)
return;

_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}

``````

Sequence traversal

Start at the root node and visit each layer in turn.
Take advantage of the first-in, first-out nature of queues to queue each layer from left to right.

``````
void LevelOrder() // Use the queue!!
{
queue<Node*> q;
Node *front = NULL;

//1.push The root node
if (_root)
{
q.push(_root);
}
//2. Traversing the current node, push The left and right children of the current node, pop The current node
//3. Walk through the left child of the current node, walk through the right child again, and loop until the queue is empty
while (!q.empty())
{

front = q.front();
cout << front->_data << " ";

if (front->_left)
q.push(front->_left);
if (front->_right)
q.push(front->_right);

q.pop();
}

cout << endl;
}

``````

Find the height of the two trees

``````
size_t Depth()
{
return _Depth(_root);
}

size_t _Depth(Node *root)
{
if (root == NULL)
return 0;
else if (root->_left == NULL && root->_right == NULL)
return 1;
else
{
size_t leftDepth = _Depth(root->_left) + 1;
size_t rightDepth = _Depth(root->_right) + 1;
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
}

``````

Find the number of leaf nodes

``````
size_t LeafSize()
{
return _LeafSize(_root);
}

size_t _LeafSize(Node *root)
{
if (root == NULL)
return 0;
else if (root->_left == NULL && root->_right == NULL)
return 1;
else
return _LeafSize(root->_left) + _LeafSize(root->_right);
}

``````

Find the number of nodes in the k layer of the two-fork tree

``````
size_t GetKLevel(int k)
{
return _GetKLevel(_root, k);
}

size_t _GetKLevel(Node *root, int k)
{
if (root == NULL)
return 0;
else if (k == 1)
return 1;
else
return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
}

``````

The complete code is as follows:

``````
template<class T>
struct BinaryTreeNode
{
T _data;
BinaryTreeNode *_left;
BinaryTreeNode *_right;

BinaryTreeNode(const T& d)
:_data(d)
, _left(NULL)
, _right(NULL)
{}
};

template<class T>
class BinaryTree
{
public:
typedef BinaryTreeNode<T> Node;

BinaryTree()
:_root(NULL)
{}

BinaryTree(T *arr, size_t n, const T& invalid)
{
size_t index = 0;
_root = _CreateBinaryTree(arr, n, invalid, index);
}

BinaryTree(const BinaryTree<T>& t)
:_root(NULL)
{
_root = _CopyTree(t._root);
}

BinaryTree<T>& operator=(const BinaryTree<T>& t)
{
if (this != t)
{
Node *tmp = new Node(t._root);
if (tmp != NULL)
{
delete _root;
_root = tmp;
}
}
return *this;
}

~BinaryTree()
{
_DestroyTree(_root);
cout << endl;
}

// Preorder non-recursive
void PrevOrder()
{
stack<Node*> s;
Node *cur = _root;

while (cur || !s.empty())
{
while (cur)
{
cout << cur->_data << " ";
s.push(cur);
cur = cur->_left;
}
// At this point, the left subtree of the current node has been traversed
Node *tmp = s.top();
s.pop();
cur = tmp->_right;
}
cout << endl;
}

// First order recursive
void PrevOrderR()
{
_PrevOrder(_root);

cout << endl;
}

// Middle order is not recursive
void InOrder()
{
stack<Node*> s;
Node *cur = _root;

while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
// At this point, the left subtree of the current node has been traversed
Node *tmp = s.top();
cout << tmp->_data << " ";
s.pop();
cur = tmp->_right;
}
cout << endl;
}

// Sequence of recursion
void InOrderR()
{
_InOrder(_root);

cout << endl;
}

// Postorder is not recursive
// Postorder traversal can be a dead loop, so record the front 1 The number of visited nodes
void PostOrder()
{
stack<Node*> s;
Node *cur = _root;
Node *prev = NULL;

while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node *tmp = s.top();
if (tmp->_right && tmp->_right != prev)
{
cur = tmp->_right;
}
else
{
cout << tmp->_data << " ";
prev = tmp;
s.pop();
}
}
cout << endl;
}

// After the sequence of recursion
void PostOrderR()
{
_PostOrder(_root);

cout << endl;
}

void LevelOrder() // Use the queue!!
{
queue<Node*> q;
Node *front = NULL;

//1.push The root node
if (_root)
{
q.push(_root);
}
//2. Traversing the current node, push The left and right children of the current node, pop The current node
//3. Walk through the left child of the current node, walk through the right child again, and loop until the queue is empty
while (!q.empty())
{

front = q.front();
cout << front->_data << " ";

if (front->_left)
q.push(front->_left);
if (front->_right)
q.push(front->_right);

q.pop();
}

cout << endl;
}

size_t Size()
{
return _Size(_root);
}

size_t LeafSize()
{
return _LeafSize(_root);
}

size_t GetKLevel(int k)
{
return _GetKLevel(_root, k);
}

size_t Depth()
{
return _Depth(_root);
}

Node* Find(const T& d)
{
return _Find(_root, d);
}

protected:
Node* _CreateBinaryTree(T *arr, size_t n, const T& invalid, size_t& index)
{
Node *root = NULL;
if (index < n && arr[index] != invalid)
{
root = new Node(arr[index]);
index++;
root->_left = _CreateBinaryTree(arr, n, invalid, index);
index++;
root->_right = _CreateBinaryTree(arr, n, invalid, index);
}
return root;
}

Node* _CopyTree(Node *root)
{
Node *newRoot = NULL;

if (root)
{
newRoot = new Node(root->_data);
newRoot->_left = _CopyTree(root->_left);
newRoot->_right = _CopyTree(root->_right);
}

return newRoot;
}

void _DestroyTree(Node *root)
{
if (root)
{
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
}

void _PrevOrder(Node *root)
{
if (root == NULL) // There must be a recursive exit!!
return;

cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}

void _InOrder(Node *root)
{
if (root == NULL)
return;

_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}

void _PostOrder(Node *root)
{
if (root == NULL)
return;

_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}

size_t _Size(Node *root)
{
if (root == NULL)
return 0;
else
return _Size(root->_left) + _Size(root->_right) + 1;
}

size_t _LeafSize(Node *root)
{
if (root == NULL)
return 0;
else if (root->_left == NULL && root->_right == NULL)
return 1;
else
return _LeafSize(root->_left) + _LeafSize(root->_right);
}

size_t _GetKLevel(Node *root, int k)
{
if (root == NULL)
return 0;
else if (k == 1)
return 1;
else
return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
}

size_t _Depth(Node *root)
{
if (root == NULL)
return 0;
else if (root->_left == NULL && root->_right == NULL)
return 1;
else
{
size_t leftDepth = _Depth(root->_left) + 1;
size_t rightDepth = _Depth(root->_right) + 1;
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
}

Node* _Find(Node *root, const T& d)
{
if (root == NULL)
return NULL;
else if (root->_data == d)
return root;
else if (Node *ret = _Find(root->_left, d))
return ret;
else
_Find(root->_right, d);
}

protected:
Node *_root;
};

``````

Related articles: