Ternary Tree construct

closed account (ShqoT05o)
I have been suffering for three days trying to figure this out and start my code.

Class Methods Description: An instance of the object TTree T is initially empty. The flowing class member functions will act on this instance as illustrated below.

construct tree(V)
- Takes a vector of characters as an input argument. First element in vector V is
the root node. All other elements in V are placed recursively inside the tree according to the set of rules
specified above. Use the STL (library) for the vector. Do not write your own vector version.

traverse LMWR()
- Traverses an instance of the object TTree recursively. The recursion rules LMWR
stand for: traverse left, traverse middle, write node value to screen, traverse right.

ternary tree rules:

first element of V becomes the root
• any subsequent character element of V is alphabetically compared to its root node and then placed
– to the left of the root node if it alphabetically comes before the root node
– to the center of the root root node if it is equal to the root node
– to the right of the root node if it alphabetically comes after the root node
An illustration of the ternary tree for a vector of characters V = {’e’,’a’,’f’,’h’,’b’,’g’,’b’,’a’,’h’,’i’,’e’} is
1
2
3
4
5
6
7
8
  
                       e 
                    /  |  \ 
                   a   e    f
                  / \        \
                 a   b        h
                      |      / | \
                      b     g  h  i


what I have so far

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <vector>

using namespace std;

struct Node {
    char data;
    Node *left;
    Node *right;
    Node *middle;
    
};

class TTree {
private:
    Node *root; 
    void insert_r(char, Node *);
    
public:
    
    
    
    
    
};
 int main(){
    
    vector<char> V = {'e','a','f','h','b','g','b','a','h','i','e'};
    TTree T;
    T.construct_tree(V);
    T.Traveser_LMWR();
return 0
}
Last edited on
Do the same as you would for a binary tree, but do the extra test for equality.
Topic archived. No new replies allowed.