John Mavrick's Garden

Search IconIcon to open search

Last updated April 10, 2022

Status: Tags: #cards/cmpt225/dataStructures/adt/trees Links: Data Structures - Mathematical Induction

Rooted Tree

Principles

Big O Notation

Image from Gyazo

Properties

Property of tree: unique path from root node to any other node Max height of a tree with n nodes is ;; n-1

Minimum height of a tree with n nodes is ;; floor(log2n)

Number of nodes in a h tall binary tree can range from ;; h to $2^h-1$

Nodes

Height of a node v ?

Level of a node v ?

Depth ?

Degree of a node ? Number of edges that touch a node v

Types

Full tree ?

Complete tree ?

Balanced tree ?

Operations

Overview

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

set_left_child(BTnode_t* parent, BTnode_t* left_child): set a node to be the left child of another node
set_right_child(BTnode_t* parent, BTnode_t* right_child): : set a node to be the right child of another node
is_leaf(BTnode_t* root): check if a node is leaf or not
size(BTnode_t* root): returns the number of nodes in the tree
height(BTnode_t* root): returns the height/depth of the tree
print_pre_order(BTnode_t* root): traverses the tree in pre-order way and prints the nodes
print_in_order(BTnode_t* root): traverses the tree in in-order way and prints the nodes
print_post_order(BTnode_t* root): : traverses the tree in post-order way and prints the nodes

count_leaves(BTnode_t* root): Counts the number of leaves in the tree • in_order_to_array(BTnode_t* root): Puts all elements of tree in an array with in-order traversal • are_equal(BTnode_t* root1, BTnode_t* root2): Checks if two nodes of the tree are equal(value and children) • BTnode_t* reconstruct_tree(int* inorder, int* preorder, int n): Reconstructs a tree given the number of nodes, the inorder traversal and the preorder traversal

InsertR

Image from Gyazo

Examples

Implementation

struct BTnode {

int data; //struct BTnode* left; // left child
struct BTnode* right; // right child

struct BTnode* parent;

}

typedef struct BTnode BTnode_t;

struct binary_tree {

struct BTnode* root;

}

Inserting

1
2
3
4
5
6
7
8

if binary search tree empty
	insert new element in root
otherwise
	if new element < element stored in root
		insert new element into left subtree
	else
		insert new element into right subtree
Let’s not forget to elementCount++

Retrieving

1
2
3
4
5
6
7
8
9

if binary search tree empty
	target element not there!
if target element == element stored in root
	return element stored in root
otherwise
	if target element < element stored in root
		search left subtree
	else
		search right subtree

Backlinks

1

list from Rooted Tree AND !outgoing(Rooted Tree)

References:

Created:: 2021-11-04 08:56

Backlinks

Interactive Graph