Trees ( other than Binary trees)

[adam2016]

Hi guys,

so I've come across binary trees and ternary trees plenty of times, and I've heard trees been talked about but I've never come across code that works for a general tree structure

I'm talking about a tree that obviously has one root node, and it's children can have as many nodes as possible for example the root node may have 3 children and one of those children may have 5 children of its own.

I've tried doing a search on this to see if I could find any code but to no avail.

could someone point me in the right direction, maybe the name of the tree I'm talking about or some links to code examples or better yet ones own information with an example.

Thanks!

[dutch]

You're not very good at googling.
https://www.google.com/search?q=programming+general+tree

[adam2016]

https://www.geeksforgeeks.org/generic-tree-level-order-traversal/

this link is one of the only code examples I could find

anyway this seems quite ugly especially when adding a new node

class Node{

public:
    int element;
    Node* right;
    Node* left;
};

    Node* addNode(Node* tree,int el){

       if(tree == NULL){

         Node* newNode = new Node;
         newNode->element = el;
         newNode->left = NULL;
         newNode->right = NULL;
         return newNode;
       }
       if(el < tree->element)
        tree->left = addNode(tree->left,el);
       else
        tree->right = addNode(tree->right,el);

       return tree;
    }

as above with a binary tree all you need to do now to add a new node to the tree is call the addNode function

Node* tree = NULL;
    BST bst;
    tree = bst.addNode(tree,20);
    bst.addNode(tree,15);
    bst.addNode(tree,10);

but with the general tree in the link's example it gets quite messy when trying to add a node to the tree

Node *root = newNode(10); 
    (root->child).push_back(newNode(2)); 
    (root->child).push_back(newNode(34)); 
    (root->child).push_back(newNode(56)); 
    (root->child).push_back(newNode(100)); 
    (root->child[0]->child).push_back(newNode(77)); 
    (root->child[0]->child).push_back(newNode(88)); 
    (root->child[2]->child).push_back(newNode(1)); 
    (root->child[3]->child).push_back(newNode(7)); 

surely there is a better and possibly recursive way of adding a node to the tree much like the BST?

[ne555]

> bst.addNode(tree,15);
¿why do you even bother to pass the `tree' parameter?
that should be contained in your BST class


> surely there is a better and possibly recursive way of adding a node to the tree much like the BST?
in a BST it holds that
left_tree < root < right_tree
and you don't actually care about its topology (who is child of who)

[dutch]

surely there is a better and possibly recursive way of adding a node to the tree much like the BST?

Nope. And don't call me Shirley.

But seriously, it depends on what your general tree is for. The BST can add things recursively because there is a way to determine where to add things. How do you do that for a general tree? It depends on exactly what the use case is. The example you show is building the tree in the most naive way, surely, but that's just an example.

You haven't given any use case you're interested in, like a parse tree, where the structure is determined by the language structure.

Here's an example I pulled from my butt. It's pretty ugly too, I guess, and I wrote it in a hurry so it can surely be improved. Suppose you want to represent sections and subsections of a book, which is a totally general, free-form tree.

0 MyBook
  1 A
    1.1 AA
    1.2 AB
  2 B
  3 C
    3.1 CA
    3.2 CB
      3.2.1 CBA
      3.2.2 CBB
    3.3 CC
    3.4 CD
      3.4.1 CDA

#include <iostream>
#include <iomanip>
#include <vector>

struct Node {
    std::string title;
    std::vector<Node*> children;

    Node(std::string title) : title(title) {}
};

class Tree {
    Node* root;

    static void clear(Node *node) {
        if (!node) return;
        for (size_t i = 0; i < node->children.size(); ++i)
            clear(node->children[i]);
        delete node;
    }
    static void print(Node* node, int indent=1) {
        if (!node) return;
        std::cout << std::setw(indent * 4) << ""
                  << node->title << '\n';
        for (size_t i = 0; i < node->children.size(); ++i)
            print(node->children[i], indent + 1);
    }
public:

    Tree(std::string title) : root{new Node(title)} {}

    ~Tree() { clear(root); }

    void insert(std::string title, const std::vector<size_t>& v) {
        if (v.size() == 0) return;
        Node *pos = root;
        for (size_t i = 0; i < v.size() - 1; ++i) {
            if (pos->children.size() < v[i]) {
                std::cerr << "path doesn't exist\n";
                return;
            }
            pos = pos->children[v[i] - 1];
            if (!pos) {
                std::cerr << "path doesn't exist\n";
                return;
            }
        }
        size_t n = v.back();
        if (pos->children.size() < n)
            pos->children.resize(n);
        auto& node = pos->children[n - 1];
        if (node) {
            std::cerr << "subsection already used\n";
            return;
        }
        node = new Node(title);
    }

    void print() const {
        std::cout << root->title << '\n';
        for (size_t i = 0; i < root->children.size(); ++i)
            print(root->children[i]);
    }
};

int main() {
    Tree t("MyBook");
    t.insert("A",       {1});
    t.insert(  "AA",    {1,1});
    t.insert(  "AB",    {1,2});
    t.insert("B",       {2});
    t.insert("C",       {3});
    t.insert(  "CA",    {3,1});
    t.insert(  "CB",    {3,2});
    t.insert(    "CBA", {3,2,1});
    t.insert(    "CBB", {3,2,2});
    t.insert(  "CC",    {3,3});
    t.insert(  "CD",    {3,4});
    t.insert(    "CDA", {3,4,1});

    t.print();
}

Note that you need to tell it exactly where to add the nodes since the tree is totally general and there is no pre-determined structure.

[adam2016]

Thanks Dutch that makes sense

and yeah I probably could have just put the pointer to a node as a member of the BST class again probably would have made more sense

[jonnin]

if you don't have a rule that gives you something akin to BST behaviors, a generic tree becomes just a special graph and while it has a few properties you may be able to exploit, you may end up having to graph-like activities on them instead of bst-like activities. I don't know of a lot of middle ground; either you have insert/fetch rules that make it like a bst (even if not binary) or you don't ...

so maybe what you can google is how to add a node to a graph, which in short is largely tied to the data ... it lands where it does because of what connects to it and what it connects to. A general tree is going to be much like that except it only has one way in.

an example where it might be BST-like would be if you stored words based off the depthish letter. That is, say the word 'word' would go to root (which may be empty / special) then to the 'w' leg, and from the w leg to the 'o' leg, and from that o leg to the r leg, and finally down the d-leg and say into the data portion of that node (its the only node that can have the word word in it, if it had more letters, it would go down more, if it had other letters, it would not be here). You can search/fetch on that much like a BST, see?

[dutch]

a generic tree becomes just a special graph

Good point.
https://en.wikipedia.org/wiki/Tree_(graph_theory)
https://en.wikipedia.org/wiki/Tree_(data_structure)