Tree Data Structures

Tree data structures are recursive

Tree is a nonlinear data structure

Definitions of Tree Terminology

Tree rooted tree stored information in nodes. Edges ina tree represnt the parent-child relationship between nodes.

degree of a node is defined as its number of children.

leaf nodes are nodes with degree 0, i.e. $deg(l)=0$

path is a sequence of nodes such as $<a_0, a_1, a_2, .. a_n>$ where $a_{k+1}$ is a child of $a_k$. The length of this path is $n$.

In a rooted tree, there is always a unique path from root to any node.

depth of a node is the length of th path from root to that node.

height of a tree is the maximum depth of any node within the tree.

ancestor and descendant: node $a$ is called to be ancestor of $b$ if there is a path from $a$ to $b$. Then, $b$ is called a descendent of $a$.

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 Simple_tree {
    private:
        Type element;
        Simple_tree *parent_node;
        Single_list<Siple_tree *> children;

    public:
        Simple_tree(Type const & = Type(), 
};

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 [ ]: