Data Structures and Algorithms Experiment

Binary Tree Comparison & Huffman Encoding/Decoding

苗夕远 · Data Structures & Algorithms · Experiment 3

1. Experiment Overview

This experiment consists of two independent tasks, both implemented in a single source file main.cpp :

Task	Content	Core Algorithm
Task 1	Determine whether two binary trees are equal	Recursive comparison of binary linked list structures
Task 2	Huffman encoding/decoding	Greedy tree construction + backtracking encoding + traversal decoding

2. Development Environment

Item	Description
Language Standard	C++ 98/03（compatible with all major compilers）
Compiler	g++ (MinGW-w64) 4.9+ / MinGW bundled with Dev-C++ / VS, etc.
Compile Command	`g++ -o main.exe main.cpp`
File Structure	Single-file project, no external dependencies

        Note:The code has been made compatible with Dev-C++ using entirely C++98 syntax, without relying on -std=c++11。
    

3. Task 1: Determine Whether Two Binary Trees Are Equal

3.1 Data Structure

Uses binary linked list to store the binary tree:

struct BiTNode {
    char data;              // Node data
    BiTNode *lchild, *rchild; // left/right child pointers
};
typedef BiTNode* BiTree;

3.2 Tree Construction Method

Creates the binary tree recursively from a preorder traversal string with # representing empty nodes.

Example: The string "AB##C##" corresponds to the following tree structure:

        A
      /   \
     B     C
    / \   / \
   #   # #   #

Recursive tree construction logic:

Read the current character; if it is # or out of bounds → set pointer to NULL, return
Otherwise create a new node and store the character
Recursively create the left subtree
Recursively create the right subtree

3.3 Comparison Algorithm — `CmpTree`

int CmpTree(BiTree T1, BiTree T2)
{
    if (T1 == NULL && T2 == NULL)  return 1;    // Both empty → equal
    if (T1 == NULL || T2 == NULL)  return 0;    // One empty, one not → not equal
    if (T1->data != T2->data)     return 0;    // Root values differ → not equal
    int left  = CmpTree(T1->lchild, T2->lchild);  // Recurse left subtree
    int right = CmpTree(T1->rchild, T2->rchild);  // Recurse right subtree
    return left && right;                          // Equal only if both subtrees are equal
}

Complexity: O(min(N₁, N₂)), where N is the number of nodes. Uses preorder traversal order recursion.

3.4 Test Cases

#	Tree 1	Tree 2	Expected
1	`AB##C##`	`AB##C##`	Equal
2	`AB##C##`	`AD##C##`	Not equal (data differs)
3	`AB##C##`	`ABC###`	Not equal (structure differs)

4. Task 2: Huffman Encoding/Decoding

4.1 Data Structure

Uses sequential storage structure (1D array) to store Huffman tree nodes:

struct HTNode {
    int weight;    // Weight (frequency)
    int parent;    // Parent index (0 = no parent / root)
    int lchild;    // Left child index (0 = no child / leaf)
    int rchild;    // Right child index
    char ch;       // leaf node character
};

Array HT[1..2n-1], indexed from 1 (position 0 is manually zeroed as a sentinel):

HT[1..n] — Leaf node(n = number of distinct character types)
HT[n+1..2n-1] — internal node
HT[2n-1] — root node

4.2 Algorithm Flow

Step 1: Count Frequencies

Traverse the input string using the freq[26] array to count occurrences of characters a~z, converting to lowercase for uppercase input.

Step 2: Select — Pick Two Minimum Weights

void Select(HTNode *HT, int sum, int &s1, int &s2)
{
    // Round 1: find the node index with smallest weight among parent==0 → s1
    // Temporarily set HT[s1].weight to INT_MAX to avoid duplicate selection
    // Round 2: find the node index with smallest weight among parent==0 → s2
    // Restore HT[s1].weight
}

Greedy strategy: each time, select the two nodes with the smallest weights from unselected nodes, merging them into a new internal node.

Step 3: Build the Huffman Tree

for (i = n+1; i <= 2n-1; i++) {
    Select(HT, i-1, s1, s2);             // Select two smallest
    HT[i].weight = HT[s1].weight + HT[s2].weight;
    HT[i].lchild = s1;  HT[i].rchild = s2;
    HT[s1].parent = i;  HT[s2].parent = i;
}

Step 4: Generate Codes (Backtracking)

For each leaf node, backtrack upward to the root:

If the current node is the left child of its parent → prepend '0' to the code
If the current node is the right child of its parent → prepend '1' to the code
When reaching the root, reverse the path to obtain the code

// Example: Leaf node i=3, path 3→5→8(root)
// 3 is left child of 5 → "0"
// 5 is right child of 8 → "10"
// Code = "10"

Step 5: Decode (Traversal Method)

Starting from the root node, read the encoded string bit by bit:

Read '0' → go to left child
Read '1' → go to right child
Reaching a leaf node (lchild==0 && rchild==0) → output that character, return to root

cur = root;                    // Start from root
for each bit in encoded:
    cur = (bit=='0') ? HT[cur].lchild : HT[cur].rchild;
    if (cur is leaf):
        output HT[cur].ch;    // Output character
        cur = root;           // Return to root

Special Case: n=1 (Single Character)

When the input string has only one character (e.g. "aaaa"), n=1, m=1. In this case:

No internal nodes are built; the single node is both root and leaf
The encoding is fixed to "0"
Decoding directly maps each '0' to that character

4.3 Output Format Specification

Each data set outputs 2n+3 lines (n = number of distinct characters):

Line #	Content	Example
1	Character frequencies (ASCII ascending, space-separated)	`a:2 i:2 m:1 n:1 o:1 u:1 x:1 y:1`
2 ~ 2n	Huffman tree node final state (2n-1 lines total)	`2 12 0 0`(weight parent lchild rchild)
2n+1	Huffman code table (ASCII ascending)	`a:110 i:111 m:000 n:001 ...`
2n+2	Encoded binary string	`000111110010100111101011110001`
2n+3	Decoded original string (lowercase)	`miaoxiyuan`

4.4 Complete Example

Input "MiaoXiyuan" output:

a:2 i:2 m:1 n:1 o:1 u:1 x:1 y:1         ← Frequency (n=8)
2 12 0 0                                   ┐
2 12 0 0                                   │
1 9 0 0                                    │
1 9 0 0                                    │
1 10 0 0                                   ├ Tree node final state
1 10 0 0                                   │ (15 lines total = 2n-1)
1 11 0 0                                   │
1 11 0 0                                   │
2 13 3 4                                   │
2 13 5 6                                   │
2 14 7 8                                   │
4 14 1 2                                   │
4 15 9 10                                  │
6 15 11 12                                 ┘
10 0 13 14
a:110 i:111 m:000 n:001 o:010 u:011 x:100 y:101  ← Code table
000111110010100111101011110001                    ← Encoded string
miaoxiyuan                                       ← Decoded string

5. Usage Instructions

5.1 Compilation

Dev-C++: Open main.cpp, click "Compile & Run" (F11).

Command-line method:

# Set g++ path (e.g., MinGW bundled with Dev-C++)
set PATH=%PATH%;C:\Program Files (x86)\Dev-Cpp\MinGW64\bin

# Compile
g++ -o main.exe main.cpp

5.2 Running

Method 1: Direct Run (Interactive input)

.\main.exe
# Task 1: results auto-output
# Task 2: input strings line by line, input "0" to end

Method 2: Piped Input (Batch testing)

echo MiaoXiyuan > input.txt
echo 0 >> input.txt
main.exe < input.txt

5.3 Input Specification

Task 1 requires no input; test results are automatically output
Task 2: one string per line, considering only a~z (uppercase auto-converted to lowercase)
Input "0" terminates the program
Multiple data sets can be input continuously, each output independently

6. Program Structure

main.cpp
│
├── Task 1: Binary Tree Comparison
│   ├── struct BiTNode           — Binary linked list node definition
│   ├── CreateBiTree()           — Preorder tree construction (recursive)
│   ├── CmpTree()                — Recursively compare two trees for equality
│   ├── DestroyBiTree()          — Recursively destroy and free memory
│   └── runTask1()               — Driver: includes 3 test cases
│
├── Task 2: Huffman Coding
│   ├── struct HTNode            — Huffman tree nodes (sequential storage)
│   ├── Select()                 — Greedy selection of two minimum weights
│   ├── processHuffman()         — Core flow:
│   │   ├── Count frequencies
│   │   ├── Build Huffman tree (n→2n-1)
│   │   ├── Generate code table (backtracking)
│   │   ├── Encode string
│   │   └── Decode string
│   └── runTask2()              — Multi-line input loop
│
└── int main()                   — Entry point, executes Task 1 then Task 2

Function Call Graph

main()
├── runTask1()
│   ├── CreateBiTree()          (Build tree 1)
│   ├── CreateBiTree()          (Build tree 2)
│   ├── CmpTree()               (Compare)
│   │   ├── CmpTree()           (Left subtree recursion)
│   │   └── CmpTree()           (Right subtree recursion)
│   └── DestroyBiTree()         (Destroy ×2)
│
└── runTask2()
    └── while(getline)
        └── processHuffman(str)
            ├── Count frequencies
            ├── Select()        (Select two smallest during tree construction, called n-1 times)
            ├── Backtracking encoding
            └── Traversal decoding

7. Detailed Knowledge Points

7.1 Binary Tree Storage Structure — Binary Linked List

Core idea: Each node contains three fields——data field (data), left pointer field (lchild), and right pointer field (rchild)。This representation, also known as a simplified "left-child right-sibling" notation (keeping only children, not siblings), is the most common linked storage method for binary trees.

struct BiTNode {
    char data;                   // Data field
    BiTNode *lchild, *rchild;    // Pointer fields: point to left and right subtrees respectively
    // When no subtree exists, the pointer is NULL
};

Aspect	Binary Linked List	Trinary Linked List	Sequential Storage (Array)
Node structure	data + lchild + rchild	data + lchild + rchild + parent	data only; parent-child implied by index relationships
Space efficiency	2 pointers/node	3 pointers/node	0 pointers, but potential waste
Find parent	Traverse from root	O(1)	O(1)(i/2)
Use case	General binary trees	Frequent parent lookups	Complete/full binary trees

Application in this experiment: Task 1's BiTNode uses binary linked list to store binary trees of arbitrary shape. Since frequent recursive traversal of left/right subtrees is needed without requiring parent lookup, the binary linked list is the optimal choice. Creation and destruction are both implemented recursively, naturally matching the fractal structure of trees.

7.2 Recursive Preorder Traversal and Tree Construction

Definition of preorder traversal: Root node → Left subtree (preorder) → Right subtree (preorder). This is the most intuitive of the three depth-first traversals (preorder/inorder/postorder) and the method chosen for tree construction in this experiment.

Role of the "#" placeholder: A preorder sequence alone cannot uniquely determine a binary tree (e.g. "AB" could be A->left=B or could be A->right=B)。By introducing # to represent empty nodes, the sequence contains complete structural information, allowing unique reconstruction of the entire tree. This notation is also called "extended preorder traversal".

Recursive tree construction process (using "AB##C##" as an example):

Step	Char Read	Operation	Recursion Depth
1	`A`	Create root node A, recursively build left subtree	0→1
2	`B`	Create node B, recursively build left subtree	1→2
3	`#`	B's left child is NULL, return; recursively build B's right subtree	2
4	`#`	B's right child is NULL, return; back to A level	2→1
5	`C`	Create node C as A's right child, recursively build left subtree	1→2
6	`#`	C's left child is NULL, return	2
7	`#`	C's right child is NULL, return; tree construction complete	2→1→0

Time complexity: O(L), where L is the sequence length（each character read once, each node created once）。Space complexity: O(H), where H is the tree height（recursion call stack depth）。

7.3 Recursive Traversal Applied in CmpTree

CmpTree is essentially a "synchronized preorder traversal": it traverses both trees simultaneously, comparing nodes at each corresponding position.

Analysis of the three recursive elements:

Base Case:
- Both nodes empty → subtrees equal (return 1)
- Only one empty → structure differs, not equal (return 0)
- Node values differ → data differs, not equal (return 0)
Recurrence: Two trees are equal iff the roots are equal AND the left subtrees are equal AND the right subtrees are equal
Return value propagation: Bottom-up propagation — leaf-level comparison results are ANDed upward, ultimately converging at the root

Recursion tree diagram (Test 1: two identical trees "AB##C##" vs "AB##C##"):

CmpTree(A1,A2)
├── data 'A'=='A' ✓
├── CmpTree(B1,B2)
│   ├── data 'B'=='B' ✓
│   ├── CmpTree(NULL,NULL) → 1
│   └── CmpTree(NULL,NULL) → 1
│   └── return 1 && 1 = 1
├── CmpTree(C1,C2)
│   ├── data 'C'=='C' ✓
│   ├── CmpTree(NULL,NULL) → 1
│   └── CmpTree(NULL,NULL) → 1
│   └── return 1 && 1 = 1
└── return 1 && 1 = 1  → The two trees are equal

Most important point: This recursion is fundamentally Divide and Conquer——decomposing the problem "are the entire trees equal?" into two sub-problems "is the left subtree equal?" and "is the right subtree equal?", then merging the results.

7.4 Sequential Storage of Binary Trees

Basic principle: Nodes of a binary tree are numbered by level order and stored in an array. For a node numbered k:

Parent: position ⌊k/2⌋
Left child: position 2k
Right child: position 2k+1

Comparison with linked storage:

Property	Sequential Storage	Linked Storage
Find children	O(1) (compute index directly)	O(1) (pointer dereference)
Find parent	O(1) (index ÷ 2)	O(N) (traverse from root)
Space utilization	Efficient only for complete trees; otherwise significant waste	100%, no waste
Insert/delete	Requires shifting many elements	Just modify pointers

Application in this experiment:Task 2's Huffman tree uses a variant of sequential storage — via explicit parent/lchild/rchild fields storing indices rather than relying on the implicit formulas 2k and 2k+1. This is because a Huffman tree is not a complete binary tree, so the formulas cannot be used to fix relationships. This approach combines the advantages of sequential storage (random array access) and linked storage (flexible connections):

parent = 0 indicates the node has no parent (i.e., root)
lchild = 0 / rchild = 0 indicates no left/right child (i.e., leaf)
The array index itself serves as the "node ID"; nodes are referenced by ID, avoiding pointer operations

7.5 Huffman Tree Construction Algorithm

A Huffman tree (optimal binary tree) is a binary tree with the minimum weighted path length (WPL), commonly used in data compression.

Weighted Path Length (WPL) formula:

WPL = Σ (Leaf weight × path length from leaf to root)

Construction algorithm (5-step method):

Initialization: Construct each of the n characters with its weight into a single-node binary tree, forming forest F
Select: From F, pick the two trees with the smallest root weights (the Select operation)
Merge: Use these two trees as left and right subtrees to construct a new tree; the new root weight is the sum of the two subtree weights
Return: Put the new tree back into forest F
Repeat: Repeat steps 2-4 until only one tree remains in F, which is the Huffman tree

Complete construction process using "abc" as example (n=3, m=5):

Round	Trees currently in forest (by weight)	Two smallest selected	After merging
Initial	{a:1}, {b:1}, {c:1}	—	—
Round 1 (i=4)	{a:1}, {b:1}, {c:1}	s1=a(1), s2=b(1)	New T₄ weight=2, children={a,b}. Forest: {c:1}, {T₄:2}
Round 2 (i=5)	{c:1}, {T₄:2}	s1=c(1), s2=T₄(2)	New T₅ weight=3, children={c,T₄}. Forest: {T₅:3} (sole tree, i.e. root)

The final Huffman tree:

         T₅(3)
        /     \
     c(1)     T₄(2)
             /     \
          a(1)    b(1)

Algorithm complexity: Each Select requires scanning O(n) nodes; with n-1 merge operations, total time complexity is O(n²). Using a min-heap (priority queue) to optimize Select reduces this to O(n log n).

Space complexity: Array size is 2n, i.e. O(n).

7.6 Greedy Strategy

Definition of greedy strategy: At each step, make the locally optimal choice, hoping that a series of locally optimal choices leads to a globally optimal solution.

Application in Huffman coding: When building the tree, always select and merge the two nodes with the current smallest weights. Intuitively: characters with larger weights should be closer to the root (shorter codes), saving total bits. Merging the two smallest first causes them to occupy deeper positions (longer codes), while heavier characters remain "light" in subsequent merges and end up closer to the root.

Greedy correctness (intuitive understanding): Suppose an optimal binary tree T exists. Let a,b be the two leaves with the smallest weights. Then there must exist an optimal tree where a,b are siblings at the maximum depth. This is because swapping the deepest-positioned character with a or b cannot increase the WPL (it can only decrease or stay the same). This is the mathematical foundation of Huffman coding optimality.

Greedy vs. Dynamic Programming comparison:

Property	Greedy	Dynamic Programming
Selection strategy	Pick local optimum at each step	Consider all possibilities, choose global optimum
Time complexity	Usually lower	Usually higher
Scope	Must satisfy greedy choice property	Must satisfy optimal substructure
Huffman coding	✓ Greedy choice property holds	Also solvable, but more complex

7.7 Backtracking Method for Huffman Code Generation

Backtracking definition:Starting from the goal state, trace the path backward to the initial state, recording decisions along the way.

Application in Huffman coding (bottom-up):

Starting from a leaf node, backtrack upward along parent pointers to the root
At each step, determine whether the current node is the left or right child of its parent:
- Left child → this step generates '0'
- Right child → this step generates '1'
When reaching the root, the resulting '0'/'1' sequence is the reversed code; reversing it yields the final code

Example of encoding generation for character 'n' in "MiaoXiyuan":

Node n is located at HT[4] (leaf), backtracking process:
HT[4].parent = 9 → HT[4] is the right child of HT[9] → generates '1'
HT[9].parent = 13 → HT[9] is the left child of HT[13] → generates '0'
HT[13].parent = 15 → HT[13] is the left child of HT[15] → generates '0'
Reached root (parent=0), stop
Reversed sequence: '1' → '0' → '0'
After reversal: '0' → '0' → '1' = "001"  ← Final code

The advantage of backtracking is that there is no need to maintain a current path from the root; each leaf independently generates its code, keeping the logic clear.

7.8 Prefix Property of Huffman Codes

Definition of prefix code: In a code set, no character's code is a prefix (i.e., leading part) of another character's code.

Why Huffman codes are naturally prefix codes:

In a Huffman tree, all characters are stored in leaf nodes
internal nodes do not store any characters; they only serve as path branching points
Therefore, the path from the root to any leaf node cannot pass "through" another leaf
In other words, no root-to-leaf path is a prefix of another path

Key significance of the prefix property — guaranteed unique decoding:

During decoding, start from the root and follow bits 0/1 downward; when reaching a leaf, output the character and return to the root. Due to the prefix property, it is impossible to still be "halfway" through another character's code when reaching a leaf, so the decoding result is unique.

// Example decoding of encoded string "10110" for "abc":
// Code table: a=10, b=11, c=0

Starting from root T₅:
  '1' → go to T₄
  '0' → reached leaf a, output 'a', return to root T₅ ✓
       (at this point it is impossible to be halfway through another code, because a's code is not a prefix of any other code)

Continue from root T₅:
  '1' → go to T₄
  '1' → reached leaf b, output 'b', return to root T₅ ✓

Continue from root T₅:
  '0' → reached leaf c, output 'c', return to root T₅ ✓

Decoded result: "abc" ✓

Counterexample of non-prefix code: If a's code is "1", b's code is "10", then when reading "10" , it is impossible to determine whether to decode as "b" or first decode "a" (since '1' would already return a). Huffman coding naturally avoids this problem through the design of "all characters at leaves".

7.9 Memory Management — Tree Destruction

DestroyBiTree uses postorder traversal for destruction: First recursively destroy the left subtree, then the right subtree, and finally release the root node. This is necessary — if subtrees are not released before releasing the root, it causes memory leaks (subtree nodes become inaccessible).

void DestroyBiTree(BiTree &T) {
    if (T == NULL) return;          // Empty tree, no destruction needed
    DestroyBiTree(T->lchild);        // First destroy left subtree (recursion)
    DestroyBiTree(T->rchild);        // Then destroy right subtree (recursion)
    delete T;                        // Finally release root node
    T = NULL;                        // Avoid dangling pointer
}

Task 2's Huffman tree uses delete[] HT to release the entire array at once, since all nodes are in contiguous memory and do not need individual release.

8. Detailed Experiment Examples

8.1 Task 1: Binary Tree Comparison — Three Test Cases in Detail

Test 1: Two Identical Trees

Input: Tree 1 = "AB##C##", Tree 2 = "AB##C##"

    Tree 1:                  Tree 2:
       A                       A
      / \                     / \
     B   C                   B   C
    (leaf) (leaf)           (leaf) (leaf)

Comparison process (CmpTree recursion expanded):

CmpTree(A₁, A₂): data 'A'=='A' ✓, recursively compare left and right subtrees
CmpTree(B₁, B₂): data 'B'=='B' ✓, both left and right subtrees are NULL, return 1
CmpTree(C₁, C₂): data 'C'=='C' ✓, both left and right subtrees are NULL, return 1
Root level: left=1, right=1, return 1 && 1 = 1 → equal

Program output: Test 1: Preorder sequences "AB##C##" and "AB##C##" -> equal ✓ correct

Test 2: Two Trees with Different Data

Input: Tree 1 = "AB##C##", Tree 2 = "AD##C##"

    Tree 1:                  Tree 2:
       A                       A
      / \                     / \
     B   C                   D   C
    (leaf) (leaf)           (leaf) (leaf)

Comparison process:

CmpTree(A₁, A₂): data 'A'=='A' ✓, recursively compare left and right subtrees
CmpTree(B₁, D₁): "B" ≠ "D", immediately returns 0!
Root level: left=0, return 0 → not equal (data differs)

Key observation: once a node value difference is found, 0 is immediately returned and propagated upward — this is short-circuit evaluation applied in recursion.

Program output: Test 2: Preorder sequences "AB##C##" and "AD##C##" -> not equal ✓ correct

Test 3: Two Trees with Different Structures

Input: Tree 1 = "AB##C##", Tree 2 = "ABC###"

First analyze the shapes of the two trees:

	String	Preorder Reduction Process	Tree Structure
Tree 1	`AB##C##`	A→B(L)→NULL(L of B)→NULL(R of B)→C(R of A)→NULL(L of C)→NULL(R of C)	A has left and right children B and C; B, C are leaves
Tree 2	`ABC###`	A→B(L)→C(L of B)→NULL(L of C)→NULL(R of C)→NULL(R of B)→NULL(R of A)	A→B→C is a left-skewed tree

    Tree 1:                  Tree 2:
       A                       A
      / \                     /
     B   C                   B
    (leaf) (leaf)           /
                           C
                          (leaf)

Comparison process:

CmpTree(A₁, A₂): data 'A'=='A' ✓, recursively compare left and right subtrees
CmpTree(B₁, B₂): data 'B'=='B' ✓, recursively compare B subtree's left and right children
- CmpTree(NULL(B₁ left), C₁): T₁==NULL but T₂!=NULL → return 0!
B level: left=0, return 0 → propagated up to root → not equal (structure differs)

Key observation: B is a leaf in Tree 1 (both children = NULL), but B has left child C in Tree 2. When one side is NULL and the other is not, a structural difference is immediately determined.

Program output: Test 3: Preorder sequences "AB##C##" and "ABC###" -> not equal ✓ correct

8.2 Task 2: Huffman Encoding/Decoding — Complete Examples

Example A: Simple input "abc" (three distinct characters, each appears once)

Input:"abc" → n=3(number of character types)

Step 1: Count character frequencies

Char	a	b	c
Freq	1	1	1

Output line 1: a:1 b:1 c:1

Step 2: Initialize leaf nodes (HT[1..3])

Index	weight	ch	Description
1	1	a	Leaf node
2	1	b	Leaf node
3	1	c	Leaf node

Step 3: Build the Huffman tree (n-1 = 2 merge rounds total)

Round 1 (generate internal node i=4):

Select(HT, 3, s1, s2): Find the two smallest weights among HT[1..3] (parent==0)
min1=1 (index 1→a), min2=1 (index 2→b), choose s1=1, s2=2
Create HT[4]: weight=1+1=2, lchild=1(a), rchild=2(b)
HT[1].parent=4, HT[2].parent=4 (a,b no longer selectable)

Currently selectable nodes: HT[3](c,weight=1), HT[4](internal,weight=2)

Round 2 (generate root node i=5):

Select(HT, 4, s1, s2): HT[3](1) and HT[4](2) have parent==0
min1=1 (index 3→c), min2=2 (index 4), choose s1=3, s2=4
Create HT[5]: weight=1+2=3, lchild=3(c), rchild=4(internal)
HT[3].parent=5, HT[4].parent=5
HT[5].parent=0 → this is the root node!

Huffman tree visualization:

           [5] w=3 (root)
           /      \
       [3]c(1)   [4] w=2
                /      \
            [1]a(1)  [2]b(1)

Step 4: Output tree node final state (HT[1..5], 2n-1=5 lines, lines 2~6)

Index  weight parent lchild rchild   ← Format
 1      1      4      0      0        a: leaf, weight=1, parent=4
 2      1      4      0      0        b: leaf, weight=1, parent=4
 3      1      5      0      0        c: leaf, weight=1, parent=5
 4      2      5      1      2        internal node, weight=2, children=a(1) and b(2)
 5      3      0      3      4        root node, weight=3, children=c(3) and internal(4)

Step 5: Generate code table (backtracking, line 7 output)

Char	Leaf Index	Backtrack Path	Code	Verify
a	1	1→4(L/0)→5(R/1)→root Reverse: 1→0 = "10"	`10`	2 bits
b	2	2→4(R/1)→5(R/1)→root Reverse: 1→1 = "11"	`11`	2 bits
c	3	3→5(L/0)→root Reverse: 0 = "0"	`0`	1 bit

Output: a:10 b:11 c:0

Step 6: Encode the original string (line 8 output)

"abc" → a(10) + b(11) + c(0) = 10110

Step 7: Decode verification (line 9 output)

Decoding "10110":
'1'→[4] '0'→[1]=a (output a,back to root)
'1'→[4] '1'→[2]=b (output b,back to root)
'0'→[3]=c          (output c,back to root)
Result: "abc" ✓

Complete output (2n+3 = 2×3+3 = 9 lines):

a:1 b:1 c:1           ← Line 1: Character frequencies
1 4 0 0              ← Line 2: HT[1] (a)
1 4 0 0              ← Line 3: HT[2] (b)
1 5 0 0              ← Line 4: HT[3] (c)
2 5 1 2              ← Line 5: HT[4] (internal node)
3 0 3 4              ← Line 6: HT[5] (root)
a:10 b:11 c:0        ← Line 7: Code table
10110                ← Line 8: Encoded string
abc                  ← Line 9: Decoded restoration

Example B: Single-character input "aaaa"

This is a boundary case: all characters are the same, n=1, m=1 (no internal nodes).

Output (2×1+3 = 5 lines):

a:4                  ← Frequency: a appears 4 times
4 0 0 0              ← The only tree node: weight=4, root (parent=0), leaf (lchild=rchild=0)
a:0                  ← Code: fixed as  "0"
0000                 ← Encoded string: 4 zeros for 4 a's
aaaa                 ← Decoded restoration

Key code logic: When n=1, the merge loop is not executed (n+1 > m), and code generation proceeds directly. During encoding, while(parent != 0) does not execute; code is empty and is specially handled as "0"(line 182). During decoding, m == 1 is detected, and each '0' is directly mapped to the unique character (lines 206-207).

Example C: Complex input "MiaoXiyuan" (mixed case, containing repeated characters)

Input "MiaoXiyuan" demonstrates uppercase auto-conversion to lowercase and the complete encoding process with multiple character types.

Frequency statistics (n=8 character types):

Original input: M i a o X i y u a n
After lowercasing: m i a o x i y u a n

a:2   i:2   m:1   n:1   o:1   u:1   x:1   y:1

Merge process overview (8 leaves → 7 merge rounds → 1 root):

Round 1 (i=9):  Merge m(1)+n(1) → internal node[9]  w=2
Round 2 (i=10): Merge o(1)+u(1) → internal node[10] w=2
Round 3 (i=11): Merge x(1)+y(1) → internal node[11] w=2
Round 4 (i=12): Merge a(2)+i(2) → internal node[12] w=4
Round 5 (i=13): Merge [9](2)+[10](2) → internal node[13] w=4
Round 6 (i=14): Merge [11](2)+[12](4) → internal node[14] w=6
Round 7 (i=15): Merge [13](4)+[14](6) → root node[15] w=10

Final Huffman tree structure:

                         [15] w=10 (root)
                    /                    \
             [13] w=4                  [14] w=6
            /        \                /        \
      [9] w=2      [10] w=2     [11] w=2    [12] w=4
      /    \        /    \       /    \      /    \
   m(1)  n(1)   o(1)  u(1)   x(1)  y(1)  a(2)  i(2)

Character code verification:

Char	Weight	Backtrack path (index→parent)	Reversed code
m	1	[3]→[9](L/0)→[13](L/0)→[15](L/0)	`000`
n	1	[4]→[9](R/1)→[13](L/0)→[15](L/0)	`001`
o	1	[5]→[10](L/0)→[13](R/1)→[15](L/0)	`010`
u	1	[6]→[10](R/1)→[13](R/1)→[15](L/0)	`011`
x	1	[7]→[11](L/0)→[14](L/0)→[15](R/1)	`100`
y	1	[8]→[11](R/1)→[14](L/0)→[15](R/1)	`101`
a	2	[1]→[12](L/0)→[14](R/1)→[15](R/1)	`110`
i	2	[2]→[12](R/1)→[14](R/1)→[15](R/1)	`111`

Encoding result:

"miaoxiyuan"
= m(000) + i(111) + a(110) + o(010) + x(100) + i(111) + y(101) + u(011) + a(110) + n(001)
= 000111110010100111101011110001

Observation: Characters with weight 2 (a, i) get 3-bit codes, and characters with weight 1 (m, n, o, u, x, y) also get 3-bit codes. This is because under this frequency distribution (2×2 + 6×1 = 10), the tree structure ensures all leaves are at depth 3 from the root. This is a special case of Huffman trees — when the frequency distribution is relatively uniform, code lengths also tend to be uniform.

If the input is changed to "aaabc"(a appears 3 times, b and c once each), then a gets a shorter code (e.g., "0"), while b and c get longer codes (e.g., "10" and "11") — this demonstrates the core advantage of Huffman coding: "high frequency = short code, low frequency = long code".

Complete output (2×8+3 = 19 lines):

a:2 i:2 m:1 n:1 o:1 u:1 x:1 y:1           ← Line 1: Frequencies (n=8)
 2 12 0 0                                   ← Line 2: HT[1](a)
 2 12 0 0                                   ← Line 3: HT[2](i)
 1 9 0 0                                    ← Line 4: HT[3](m)
 1 9 0 0                                    ← Line 5: HT[4](n)
 1 10 0 0                                   ← Line 6: HT[5](o)
 1 10 0 0                                   ← Line 7: HT[6](u)
 1 11 0 0                                   ← Line 8: HT[7](x)
 1 11 0 0                                   ← Line 9: HT[8](y)
 2 13 3 4                                   ← Line 10: HT[9]  internal(m+n)
 2 13 5 6                                   ← Line 11: HT[10] internal(o+u)
 2 14 7 8                                   ← Line 12: HT[11] internal(x+y)
 4 14 1 2                                   ← Line 13: HT[12] internal(a+i)
 4 15 9 10                                  ← Line 14: HT[13] internal
 6 15 11 12                                 ← Line 15: HT[14] internal
10 0 13 14                                  ← Line 16: HT[15] root
a:110 i:111 m:000 n:001 o:010 u:011 x:100 y:101  ← Line 17: Code table
000111110010100111101011110001                    ← Line 18: Encoded string
miaoxiyuan                                       ← Line 19: Decoded string

Example D: Equal-frequency input "aabbcc" (multiple characters appear the same number of times)

Input "aabbcc", where a, b, and c each appear 2 times with identical frequencies.

Output:

a:2 b:2 c:2          ← Each appears 2 times, n=3
2 4 0 0              ← HT[1](a)
2 4 0 0              ← HT[2](b)
2 5 0 0              ← HT[3](c)
4 5 1 2              ← HT[4] internal(a+b=4)
6 0 3 4              ← HT[5] root(c+internal=6)
a:10 b:11 c:0        ← Codes: c is shortest (though frequencies are the same, the merge order causes this)
1010111100           ← Encoded string
aabbcc               ← Decoded restoration

Observation: Although a, b, and c all have frequency 2, c gets the shortest code "0" (1 bit), while a and b each get 2-bit codes "10" and "11". This is because the order in which Select picks nodes affects the tree shape — when multiple nodes have equal weights, the specific choice depends on the array traversal order. This does not affect the optimality of the Huffman tree (the WPL is still minimal), but demonstrates that optimal Huffman trees are not unique.

Verify WPL: a(2×2) + b(2×2) + c(2×1) = 4+4+2 = 10. If changed to a=0, b=10, c=11 (arbitrary arrangement), WPL = 2×1 + 2×2 + 2×2 = 10, the same. This shows that differently shaped optimal Huffman trees have equal WPL.

9. Results Interpretation Guide

The following explains the meaning of each line of program output in detail to aid in understanding the experimental results.

9.1 Task 1 Output Interpretation

=== Task 1: Determine Whether Two Binary Trees Are Equal ===
Test 1: Preorder sequences  "AB##C##" and "AB##C##" -> equal ✓ correct
Test 2: Preorder sequences "AB##C##" and "AD##C##" -> not equal ✓ correct
Test 3: Preorder sequences "AB##C##" and "ABC###" -> not equal ✓ correct

Output Field	Meaning	Basis
`equal`	CmpTree() returns 1: root values match + left subtree structure/data match + right subtree structure/data match	The preorder sequences of both trees are identical
`not equal`	CmpTree() returns 0: a node value is found to differ, or the structure differs (one side NULL, the other non-NULL)	The preorder sequences differ in at least one place
`✓ correct`	Program output matches the preset expected value	result == tests[i].expected
`✗ Error`	Program output does not match the preset expected value (should not occur normally)	Indicates a bug in the code

9.2 Task 2 Output Line-by-Line Interpretation (using input "abc" as example)

Line 1: Character Frequencies

a:1 b:1 c:1

Format	`char:freq char:freq ...`
Explanation	Counts occurrences of each letter in the input string (only a-z, case-insensitive), output in ascending ASCII order
Method	Traverse the string, `freq[ch-'a']++`, then output non-zero entries in alphabetical order
Purpose	These n frequency values are the initial weights of the Huffman tree leaf nodes, and are the input for subsequent tree construction

Lines 2 ~ 2n: Huffman Tree Node Final State

1 4 0 0    ← HT[1]: weight=1, parent=4, lchild=0(none), rchild=0(none) → leaf a
1 4 0 0    ← HT[2]: weight=1, parent=4, lchild=0(none), rchild=0(none) → leaf b
1 5 0 0    ← HT[3]: weight=1, parent=5, lchild=0(none), rchild=0(none) → leaf c
2 5 1 2    ← HT[4]: weight=2, parent=5, lchild=1(a), rchild=2(b) → internal node
3 0 3 4    ← HT[5]: weight=3, parent=0(root), lchild=3(c), rchild=4(internal) → root

Meaning of each row''s four columns:

Col	Field	Meaning	Meaning of special values
1	weight	The weight of this node	Leaf = character frequency; Internal = sum of child node weights
2	parent	Parent node index	0 = this node is the root (no parent)
3	lchild	Left child index	0 = no left child (i.e., the node is a leaf, or an internal node without a left child)
4	rchild	Right child index	0 = no right child (same reasoning)

How to reconstruct the tree structure from the table:

Find the root: Scan all rows for parent == 0 — that row is the root. For "abc", HT[5] has parent=0, so index 5 is the root.
Identify leaves: If a row has lchild == 0 && rchild == 0, then the node is a leaf storing a character.
Trace parent chain: Following the parent field value (index) upward finds the parent node, used for encoding.
Trace child chain: Following the lchild/rchild field values downward finds children, used for decoding.

For example, reconstructing the "abc" tree from the table:

Root = HT[5] (parent=0)
HT[5]: lchild=3 → HT[3]=c(leaf), rchild=4 → HT[4](internal)
HT[4]: lchild=1 → HT[1]=a(leaf), rchild=2 → HT[2]=b(leaf)

Tree structure:
    [5]w=3
    /    \
 [3]c   [4]w=2
        /    \
     [1]a   [2]b

Line 2n+1: Huffman Code Table

a:10 b:11 c:0

Meaning: Character → corresponding binary code (0/1 string). Examples:

a:10 — Character a's Huffman code is "10"(left-right)
b:11 — Character b's Huffman code is "11"(right-right)
c:0 — Character c's Huffman code is "0"(left)

Note that characters with shorter codes (e.g., c with only "0") are closer to the root in the tree (shorter path).

Line 2n+2: Encoded binary string

This is the result of replacing each character in the input string with its corresponding Huffman code and concatenating them. Example: "abc" → a''s code(10) + b''s code(11) + c''s code(0) = "10110".

Compression analysis (using "MiaoXiyuan" as an example):

Original string: 10 characters × 8 bits/char (ASCII) = 80 bits
After Huffman encoding: 000111110010100111101011110001 = 30 bits
Compression ratio: 30/80 = 37.5% (saving 62.5% of space)

Line 2n+3: Decoded restoration string

abc

This is the original string restored by decoding the binary encoded string from the previous line (converted to lowercase, non-alphabetic characters filtered).

Correctness verification: If this line exactly matches the original input string (after lowercasing and removing non-alphabetic characters), it shows the encoding→decoding process is correct and the Huffman tree code table can losslessly express the original information.

9.3 How to Quickly Verify Results

Check frequencies: The sum of frequencies should equal the number of letters in the original input. For "MiaoXiyuan", after removing non-letters there are 10 letters, and the sum of frequencies = 2+2+1+1+1+1+1+1 = 10 ✓
Check tree node count: The number of tree node final state output lines should be 2n-1. For example, n=8 should yield 15 lines ✓
Check WPL: Weighted Path Length = Σ(frequency × code length). For "MiaoXiyuan": WPL = 2×3 + 2×3 + 1×3 + 1×3 + 1×3 + 1×3 + 1×3 + 1×3 = 30. The encoded string length exactly equals the WPL ✓
Check code prefix property: For any two characters, the shorter code should not be a prefix of the longer one. For example, among m=000, n=001, o=010, 000 is not a prefix of 001 or 010 ✓
Check decoding correctness: The decoded string should equal the original input after lowercasing

10. Implementation Notes

1-based indexing: The Huffman tree array HT[1..m] has 1-based indexing (position 0 is manually zeroed as a sentinel), so that parent==0 indicates no parent/root node, making the code intuitive.
Marking technique in Select using INT_MAX: After finding the first minimum, temporarily set it to INT_MAX to avoid selecting it again in the second round; restore it after the second selection. This is a classic application of the "marking method".
n=1 special handling: For single-character input, the encoding is fixed to "0"; during decoding, directly map all '0's to that character. Without special handling, the backtracking while loop will not execute, code will be empty, and must be manually set to "0".
Case handling: The code uses tolower() converts all input to lowercase for counting, but decoded output directly uses the original leaf node''s ch (assigned lowercase values at lines 136-142), so the output is uniformly lowercase.
Non-alphabetic characters are ignored: Both frequency counting and decoded output skip non-a-z characters, including spaces, punctuation, digits, etc.