Contains the definition of our n-ary Tree. More...

#include <stdio.h>
#include "vector.h"

Include dependency graph for tree.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	Tree
	Defines the n-ary tree. More...

Macros
#define	max(a, b) ((a) > (b) ? (a) : (b))
	Computes the maximum of a and b.

Typedefs
typedef struct Tree	Tree
	Defines the n-ary tree.

Functions
Tree *	createLeaf (int id, char *str)
	Create a new leaf. More...

Tree *	createNode (int id, char str, Tree child)
	Create a new node. More...

Tree *	addChild (Tree node, Tree child)
	Add a child to a node. More...

int	isLeaf (Tree *t)
	Check whether the tree is a leaf or not. More...

int	height (Tree *t)
	Get the height of a tree. More...

int	depth (Tree *root, int id)
	Get the depth of a node in the tree. More...

Tree *	LCA (Tree *root, int id1, int id2)
	Find the lowest common ancestor We traverse from root to leaf. When we find a node matching at least one value, we pass it to its parent. The parent tests whether a child contains the value or not. If yes, the parent is the LCA, otherwise, we pass its parent, up to root. What is passed is the lower node or NULL. More...

void	freeTree (Tree *t)
	Free the tree. More...

int	isNodeDepthSameOrSmaller (Tree *t, int node1, int node2)
	Is node1 have same or smaller depth that node2? More...

Detailed Description

Contains the definition of our n-ary Tree.

Author: Bastien Philip (ebatsin); Gaël Foppolo (gaelfoppolo)

Function Documentation

Tree* addChild	(	Tree *	node,
		Tree *	child
	)

Add a child to a node.

Parameters

node	The node to which to add the child
child	The child to add to our node

Returns: The modified node (same as given as parameter)

Here is the caller graph for this function:

Tree* createLeaf	(	int	id,
		char *	str
	)

Create a new leaf.

Parameters

id	The value to store in the leaf
str	String that represents the real name of what is stored

Returns: A new leaf

Here is the caller graph for this function:

Tree* createNode	(	int	id,
		char *	str,
		Tree *	child
	)

Create a new node.

Parameters

id	The value to store in the node
str	String that represents the real name of what is stored
child	The child to add to our new node

Returns: A new node

int depth	(	Tree *	root,
		int	id
	)

Get the depth of a node in the tree.

Parameters

root	The root of the tree
id	The id of the node of which the depth is needed

Returns: The depth of the node in the tree

Here is the caller graph for this function:

void freeTree ( Tree * t )

Free the tree.

Parameters

t	Pointer to the tree

Here is the caller graph for this function:

int height ( Tree * t )

Get the height of a tree.

Parameters

t	The tree of which the height is needed

Returns: The height of the tree

Here is the call graph for this function:

int isLeaf ( Tree * t )

Check whether the tree is a leaf or not.

Parameters

t	The tree to check

Returns: 1, if the parameter is a leaf, 0 otherwise

Here is the caller graph for this function:

int isNodeDepthSameOrSmaller	(	Tree *	t,
		int	node1,
		int	node2
	)

Is node1 have same or smaller depth that node2?

Parameters

t	Pointer to Tree
node1	First node
node2	Second node

Returns: 1, if node1 have same or smaller depth, 0 otherwise

Here is the call graph for this function:

Here is the caller graph for this function:

Tree* LCA	(	Tree *	root,
		int	id1,
		int	id2
	)

Find the lowest common ancestor We traverse from root to leaf. When we find a node matching at least one value, we pass it to its parent. The parent tests whether a child contains the value or not. If yes, the parent is the LCA, otherwise, we pass its parent, up to root. What is passed is the lower node or NULL.

Parameters

root	The root of the tree
id1	The first value
id2	The second value

Returns: The lowest common ancestor (node or leaf)

Here is the caller graph for this function:

Data Structures

Macros

Typedefs

Functions

Detailed Description

Function Documentation