Tree data structures are recursive
Tree is a nonlinear data structure
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$.
class Simple_tree {
private:
Type element;
Simple_tree *parent_node;
Single_list<Siple_tree *> children;
public:
Simple_tree(Type const & = Type(),
};
template <typename Type>
void Simple_tree<Type>::depth_first_traversal() const {
std::cout << element << " ";
for (
) {
ptr->
}
};
In [ ]: