Structure definition
struct Node
{<!-- -->
Node *parent = NULL;
Node *leftChild = NULL;
Node *rightChild = NULL;
int value = 0;
};
Generation of binary tree
// Generate a tree based on the input order of the data in the vector container
Node *generateTree(const vector<int> s)
{<!-- -->
int n = s. size();
if (n == 0)
return NULL;
// Initialize the root node
Node *root = new Node();
root->value = s[0];
for (int i = 1; i < n; i ++ )
{<!-- -->
int v = s[i];
Node *currentNode = root;
while (true)
{<!-- -->
if (v <= currentNode->value)
{<!-- -->
if (currentNode->leftChild == NULL)
{<!-- -->
Node *newNode = new Node();
newNode->parent = currentNode;
newNode->value = v;
currentNode->leftChild = newNode;
break;
}
else
{<!-- -->
currentNode = currentNode->leftChild;
}
}
else
{<!-- -->
if (currentNode->rightChild == NULL)
{<!-- -->
Node *newNode = new Node();
newNode->parent = currentNode;
newNode->value = v;
currentNode->rightChild = newNode;
break;
}
else
{<!-- -->
currentNode = currentNode->rightChild;
}
}
}
}
return root;
}
Binary tree traversal
Preorder traversal
void firstPrintTree(Node *root)
{<!-- -->
if (root == NULL)
return;
cout << root->value << "\t";
firstPrintTree(root->leftChild);
firstPrintTree(root->rightChild);
return;
}
Subsequent traversal
void lastPrintTree(Node *root)
{<!-- -->
if (root == NULL)
return;
lastPrintTree(root->leftChild);
lastPrintTree(root->rightChild);
cout << root->value << "\t";
return;
}
Inorder traversal
void middlePrintTree(Node *root)
{<!-- -->
if (root == NULL)
return;
middlePrintTree(root->leftChild);
cout << root->value << "\t";
middlePrintTree(root->rightChild);
return;
}
Depth first
// Binary tree depth-first traversal
void dfsTree(Node *root, vector<int> & tree)
{<!-- -->
stack<Node *> s;
s.push(root);
tree.push_back(root->value);
map<Node *, int> seen;
while (s. size())
{<!-- -->
Node *node = s.top();
if (node->leftChild & amp; & amp; seen.find(node->leftChild) == seen.end())
{<!-- -->
s.push(node->leftChild);
tree.push_back(node->leftChild->value);
seen.insert(make_pair(node->leftChild, node->leftChild->value));
continue;
}
if (node->rightChild & amp; & amp; seen.find(node->rightChild) == seen.end())
{<!-- -->
s.push(node->rightChild);
tree.push_back(node->rightChild->value);
seen.insert(make_pair(node->rightChild, node->rightChild->value));
continue;
}
s. pop();
}
return;
}
Breadth first
void bfsTree(Node *root, vector<int> &tree)
{<!-- -->
queue<Node *> q;
q. push(root);
tree.push_back(root->value);
while (q. size())
{<!-- -->
Node *node = q. front();
if (node->leftChild)
{<!-- -->
q.push(node->leftChild);
tree.push_back(node->leftChild->value);
}
if (node->rightChild)
{<!-- -->
q.push(node->rightChild);
tree.push_back(node->rightChild->value);
}
q. pop();
}
return;
}
Statistics of the number of leaf nodes
void nodeNum(Node *root, int & amp;num)
{<!-- -->
if (root == NULL)
{<!-- -->
return;
}
if (root->leftChild == NULL & amp; & amp; root->rightChild == NULL)
{<!-- -->
num + = 1;
}
nodeNum(root->leftChild, num);
nodeNum(root->rightChild, num);
}
Destroy the tree to release memory space
void destroyTree(Node *root)
{<!-- -->
// The leaf node must be released first and then the root node, so follow-up traversal is used
if (root == NULL)
return;
destroyTree(root->leftChild);
destroyTree(root->rightChild);
delete root;
return;
}
Example code
#include
#include
#include
#include
#include
#include