tree.c File Reference

Contains definitions of routines supported by tree. More...

#include "tree.h"
#include "stack.h"
#include "queue.h"

Go to the source code of this file.

Functions
void	tree_insert_node_bst (t_gen d, t_gen data)
	Add element to a bst tree More...
t_gen	tree_delete_node_bst (t_gen d, t_gen data)
	Delete a node in a bst tree More...
int	tree_height_bst (t_gen n)
	get height of bst More...
t_gen	tree_find_node (t_gen d, t_gen data)
	find an element in tree More...
t_gen	tree_node_predecessor (t_gen d, t_gen data)
	find the predecessor of a given node in tree More...
t_gen	tree_node_successor (t_gen d, t_gen data)
	find the successor of a given node in tree More...
t_gen	tree_get_min (t_gen root)
	get min node in tree More...
t_gen	tree_get_max (t_gen root)
	get max node in tree More...
void	tree_inorder (t_gen d)
	inorder traverse tree More...
void	tree_preorder (t_gen d)
	preorder traverse tree More...
void	tree_postorder (t_gen d)
	postorder traverse tree More...
void	print_tree (t_gen d)
	print tree info level by level More...
int	tree_node_count (t_gen d)
	get_num_nodes in tree; More...
void	tree_insert_node_avl (t_gen d, t_gen data)
	Add element to an avl tree More...
t_gen	tree_delete_node_avl (t_gen d, t_gen data)
	Delete a node in an avl tree More...
int	tree_height_avl (t_gen n)
	get height of avl subtree More...
void	destroy_tree (t_gen d)
	Destroy the instance of the tree More...
t_gen	create_tree (char *name, e_treetype ttype, t_dparams *prm)
	Create an instance of tree More...
t_gen	tree_get_min_rcrs (t_gen root)
	get min node in tree recursively More...
t_gen	tree_get_max_rcrs (t_gen root)
	get max node in tree recursively More...
int	tree_slope (t_gen n)
	get slope of node subtree More...
void	tree_rotate_right (t_gen n)
	rotate subtree right More...
void	tree_rotate_left (t_gen n)
	rotate subtree left More...
void	tree_rebalance (t_gen n)
	rebalance subtree More...

Variables
f_ins	tree_insert [] = {tree_insert_node_bst,tree_insert_node_avl}
	Look Up function ptrs for inserting elem to tree. More...
f_del	tree_del [] = {tree_delete_node_bst,tree_delete_node_avl}
	Look Up function ptrs for deleting elem to tree. More...
f_len	tree_height [] = {tree_height_bst, tree_height_avl}
	Look Up function ptrs for getting height of tree. More...

Detailed Description

Contains definitions of routines supported by tree.

Definition in file tree.c.

Function Documentation

create_tree()

t_gen create_tree	(	char *	name,
		e_treetype	ttype,
		t_dparams *	prm
	)

Create an instance of tree

tree interface API

Parameters

name	- Name of tree instance
ttype	- Type of tree to be created
prm	- Data type specific parameters

Returns

- Pointer to instance of tree

Definition at line 45 of file tree.c.

destroy_tree()

void destroy_tree

(

t_gen

d

)

Destroy the instance of the tree

Parameters

d	- Pointer to instance of tree

Returns

- NA

Definition at line 515 of file tree.c.

print_tree()

void print_tree

(

t_gen

d

)

print tree info level by level

Parameters

d	- Pointer to instance of tree

Returns

- NA

Definition at line 706 of file tree.c.

tree_delete_node_avl()

t_gen tree_delete_node_avl	(	t_gen	d,
		t_gen	data
	)

Delete a node in an avl tree

Parameters

d	- Pointer to instance of tree
data	- Pointer to the data to be deleted

Returns

- Null if data not present else data pointer

Definition at line 962 of file tree.c.

tree_delete_node_bst()

t_gen tree_delete_node_bst	(	t_gen	d,
		t_gen	data
	)

Delete a node in a bst tree

Parameters

d	- Pointer to instance of tree
data	- Pointer to data of node to delete

Returns

- NULL of data not present else data pointer

Definition at line 375 of file tree.c.

tree_find_node()

t_gen tree_find_node	(	t_gen	d,
		t_gen	data
	)

find an element in tree

Parameters

d	- Pointer instance of tree
data	- Pointer data

Returns

- NULL if data absent else node pointer

Definition at line 155 of file tree.c.

tree_get_max()

t_gen tree_get_max

(

t_gen

root

)

get max node in tree

Parameters

root	- Pointer to root

Returns

- max node

Definition at line 208 of file tree.c.

tree_get_max_rcrs()

t_gen tree_get_max_rcrs

(

t_gen

root

)

get max node in tree recursively

Parameters

root	- Pointer to root

Returns

- max node

Definition at line 252 of file tree.c.

tree_get_min()

t_gen tree_get_min

(

t_gen

root

)

get min node in tree

Parameters

root	- Pointer to root

Returns

- min node

Definition at line 186 of file tree.c.

tree_get_min_rcrs()

t_gen tree_get_min_rcrs

(

t_gen

root

)

get min node in tree recursively

Parameters

root	- Pointer to root

Returns

- min node

Definition at line 230 of file tree.c.

tree_height_avl()

int tree_height_avl

(

t_gen

n

)

get height of avl subtree

Parameters

n	- Pointer to node

Returns

- height of given subtree

Definition at line 767 of file tree.c.

tree_height_bst()

int tree_height_bst

(

t_gen

n

)

get height of bst

Parameters

d	- Pointer to node

Returns

- height of tree from given node

Definition at line 465 of file tree.c.

tree_inorder()

void tree_inorder

(

t_gen

d

)

inorder traverse tree

Parameters

d	- Pointer to instance of tree

Returns

- NA

Definition at line 664 of file tree.c.

tree_insert_node_avl()

void tree_insert_node_avl	(	t_gen	d,
		t_gen	data
	)

Add element to an avl tree

Parameters

d	- Pointer to instance of tree
data	- Pointer to the data to be inserted

Returns

- NA

Definition at line 884 of file tree.c.

tree_insert_node_bst()

void tree_insert_node_bst	(	t_gen	d,
		t_gen	data
	)

Add element to a bst tree

Parameters

d	- Pointer instance of tree
data	- Pointer data

Returns

- NA

Definition at line 98 of file tree.c.

tree_node_count()

int tree_node_count

(

t_gen

d

)

get_num_nodes in tree;

Parameters

d	- Pointer instance of tree

Returns

- count of nodes

Definition at line 86 of file tree.c.

tree_node_predecessor()

t_gen tree_node_predecessor	(	t_gen	d,
		t_gen	data
	)

find the predecessor of a given node in tree

Parameters

d	- Pointer to instance of tree
data	- Pointer to data

Returns

- predcessor node pointer

Definition at line 275 of file tree.c.

tree_node_successor()

t_gen tree_node_successor	(	t_gen	d,
		t_gen	data
	)

find the successor of a given node in tree

Parameters

d	- Pointer to instance of tree
data	- Pointer to data

Returns

- successor node pointer

Definition at line 325 of file tree.c.

tree_postorder()

void tree_postorder

(

t_gen

d

)

postorder traverse tree

Parameters

d	- Pointer to instance of tree

Returns

- NA

Definition at line 561 of file tree.c.

tree_preorder()

void tree_preorder

(

t_gen

d

)

preorder traverse tree

Parameters

d	- Pointer to instance of tree

Returns

- NA

Definition at line 621 of file tree.c.

tree_rebalance()

void tree_rebalance

(

t_gen

n

)

rebalance subtree

Parameters

n	- Pointer to node

Returns

- NA

Definition at line 858 of file tree.c.

tree_rotate_left()

void tree_rotate_left

(

t_gen

n

)

rotate subtree left

Parameters

n	- Pointer to node

Returns

- NA

Definition at line 831 of file tree.c.

tree_rotate_right()

void tree_rotate_right

(

t_gen

n

)

rotate subtree right

Parameters

n	- Pointer to node

Returns

- NA

Definition at line 803 of file tree.c.

tree_slope()

int tree_slope

(

t_gen

n

)

get slope of node subtree

Parameters

n	- Pointer to node

Returns

- slope of given subtree

Definition at line 787 of file tree.c.

Variable Documentation

tree_del

f_del tree_del[] = {tree_delete_node_bst,tree_delete_node_avl}

Look Up function ptrs for deleting elem to tree.

Definition at line 33 of file tree.c.

tree_height

f_len tree_height[] = {tree_height_bst, tree_height_avl}

Look Up function ptrs for getting height of tree.

Definition at line 36 of file tree.c.

tree_insert

f_ins tree_insert[] = {tree_insert_node_bst,tree_insert_node_avl}

Look Up function ptrs for inserting elem to tree.

Definition at line 30 of file tree.c.