This article details the implementation of a C++ program designed too construct a binary tree from a preorder traversal string and subsequently calculate its depth. The program utilizes a pointer-based representation for the binary tree.

The input is a preorder traversal string where the '#' character signifies a null node (an empty subtree). For example, the string ABC##DE#G##F### represents a binary tree.

1. Data Structure Definition

• BiTNode: Represents a node in the binary tree. It contains a data field (TElemType, a character in this case) and two pointers, lchild and rchild, to its left and right children, respectively.
• BiTree: A type alias for a pointer to a BiTNode, representing the binary tree itself.

2. Binary Tree Construction (CreateBiTree function)

This function recursively builds a binary tree based on the preorder traversal input. It reads characters one by one:

• If the character read is '#', it signifies a null node, and the current subtree pointer is set to NULL.
• Otherwise, a new node is created, the character is assigned to its data field, and the function recursively calls itself to construct the left and right subtrees.

The input reading is designed to handle multiple test cases. If reading fails (e.g., end-of-file), the program exits.

void CreateBiTree(BiTree &T) {
    TElemType ch;
    if (!(cin >> ch)) { // Exit if input fails (EOF)
        exit(0);
    }
    if (ch == '#') {
        T = NULL; // '#' represents a null node
    } else {
        T = new BiTNode; // Allocate memory for the new node
        T->data = ch;
        CreateBiTree(T->lchild); // Recursively build the left subtree
        CreateBiTree(T->rchild); // Recursively build the right subtree
    }
}

3. Depth Calculation (Depth function)

This function computes the depth of the binary tree. The depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

• If the tree is empty (T is NULL), its depth is 0.
• Otherwise, it recursively calculates the depth of the left and right subtrees. The depth of the current tree is 1 (for the current node) plus the maximum of the depths of its left and right subtrees.

int Depth(BiTree T) {
    if (T == NULL) {
        return 0; // Depth of an empty tree is 0
    } else {
        int leftDepth = Depth(T->lchild);
        int rightDepth = Depth(T->rchild);
        // Return 1 + the maximum depth of the subtrees
        return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
    }
}

4. Tree Destruction (DestroyBitree function)

This function is responsible for dealllocating the memory occupied by the binary tree to prevent memory leaks. It uses a post-order traversal approach:

• If the current node T is not NULL:
  • Recursively call DestroyBitree on the left child.
  • Recursively call DestroyBitree on the right child.
  • Free the memory allocated for the current node.
  • Set the pointer T to NULL to indicate it's no longer valid.

void DestroyBitree(BiTree& T) {
    if (T) {
        DestroyBitree(T->lchild); // Destroy left subtree
        DestroyBitree(T->rchild); // Destroy right subtree
        delete T; // Free the current node
        T = NULL; // Set pointer to NULL
    }
}

5. Main Function (main)

The main function orchestrates the process. It continuously loops:

• In each iteration, it calls CreateBiTree to build a tree from user input.
• Then, it calls Depth to calculate the tree's depth and prints the result.
• Finally, it calls DestroyBitree to clean up the memory before the next iteration.

int main() {
    BiTree tree = NULL; // Initialize tree pointer
    while (1) { // Loop indefinitely for multiple test cases
        CreateBiTree(tree);
        cout << Depth(tree) << endl;
        DestroyBitree(tree);
    }
    return 0;
}

Example Usage:

Input:

a#b#cdef#####
a##

Output:

6
1