Binary tree generation and traversal

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 
using namespace std;

struct Node
{<!-- -->
    Node *parent = NULL;
    Node *leftChild = NULL;
    Node *rightChild = NULL;
    int value = 0;
};

// 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;
}

void firstPrintTree(Node *root)
{<!-- -->
    if (root == NULL)
        return;
    cout << root->value << "\t";
    firstPrintTree(root->leftChild);
    firstPrintTree(root->rightChild);
    return;
}

void middlePrintTree(Node *root)
{<!-- -->
    if (root == NULL)
        return;
    middlePrintTree(root->leftChild);
    cout << root->value << "\t";
    middlePrintTree(root->rightChild);
    return;
}

void lastPrintTree(Node *root)
{<!-- -->
    if (root == NULL)
        return;
    lastPrintTree(root->leftChild);
    lastPrintTree(root->rightChild);
    cout << root->value << "\t";
    return;
}

// Binary tree breadth-first traversal
void bfsTree(Node *root, vector & tree)
{
    queue 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;
}

// 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;
}

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;
}

// Count the number of leaf nodes in a binary tree
void nodeNum(Node *root, int & num)
{
    if (root == NULL)
    {
        return;
    }
    if (root->leftChild == NULL & amp; & amp; root->rightChild == NULL)
    {
        num + = 1;
    }
    nodeNum(root->leftChild, num);
    nodeNum(root->rightChild, num);
}

int main()
{
    vector s;
    srand((unsigned int)time(NULL));
    cout << "generate node" << endl;
    for (int i = 0; i < 10; i ++ )
    {
        int v = rand() % 10;
        cout << v << "\t";
        s.push_back(v);
    }
    cout << endl;
    Node *root = generateTree(s);
    cout << "Preorder traversal" << endl;
    firstPrintTree(root);
    cout << endl;
    cout << "Inorder traversal" << endl;
    middlePrintTree(root);
    cout << endl;
    cout << "post-order traversal" << endl;
    lastPrintTree(root);
    cout << endl;
    cout << "breadth-first traversal" << endl;
    vector vbfs;
    bfsTree(root, vbfs);
    for (vector::iterator it = vbfs. begin(); it != vbfs. end(); it ++ )
    {
        cout << *it << "\t";
    }
    cout << endl;
    cout << "depth-first traversal" << endl;
    vector vdfs;
    dfsTree(root, vdfs);
    for (vector::iterator it = vdfs. begin(); it != vdfs. end(); it ++ )
    {
        cout << *it << "\t";
    }
    cout << endl;
    // Count the number of leaf nodes in the binary tree
    int num = 0;
    nodeNum(root, num);
    cout << "The number of leaf nodes: " << num << endl;
    // Release the heap memory occupied by the binary tree
    destroyTree(root);
    system("pause");
    return 0;
}