notebook.community

Tree Data Structures

Tree data structures are recursive

Tree is a nonlinear data structure

Definitions of Tree Terminology

Node

Root

Edge

Descendants

Anscestors

HTML and CSS

<html>
 <head>

 </head>

 <body>
   <h1> This is a <u> Heading </u>  </h1>
   <p>  This is a paragraph with some <u> underlined </u> text.  </p>
 </body>

</html>

CSS

<style type="text/css">
    h1 { color:blue; }
    u  { color:red; }
</style>

General Tree

Implementation using linked-list

class Tree {

    public:
};

Height of a tree

template <typename Type>
int Simple_tree<Type>::size() const {
    int s = 1;

    for (
        Single_node<Simple_tree *> *ptr = children.head();
        ptr != nullptr;
        ptr -> next();
    ) {
        h = std::max(h, 1+ptr->retrieve()->height());
    }
}

Tree Traversal

Pre-order depth-first traversal the root is visited first
Post-order depth-first traversal the root is visited last (return a node if all its children are already visited)
In-order traversal

We can use stacks for depth-first traversal.

template <typename Type>

void Simple_tree<Type>::depth_first_traversal() const {
    std::cout << element << " ";

    for (
    ) {
        ptr->
    }
};

Print the hierarchy tree

template 

void Simple_tree<Type>::print(int depth) const {

};



In [ ]: