CLASS 15

TREES

REVIEW, RESEARCH AND DISCUSS

• HOME

Whats a Tree?

• A tree is a data structure where a node can have zero or more children. Each node contains a value. Like graphs, the connection between nodes is called edges. A tree is a type of graph, but not all graphs are trees .

• These data structures are called “trees” because the data structure resembles a tree. It starts with a root node and branch off with its descendants, and finally, there are leaves.

TERMS:

root

• The root is the node at the beginning of the tree.

left

• A reference to one child node, in a binary tree.

right

• A reference to the other child node, in a binary tree.

edge

• The edge in a tree is the link between a parent and child node.

leaf

• A leaf is a node that does not have any children.

height

• The height of a tree is the number of edges from the root to the furthest leaf.

node

• A Tree node is a component which may contain it’s own values, and references to other nodes

K

• Is a number that specifies the maximum number of children any node may have in a k-ary tree.

There are two catagories of traversing of a tree:

• depth first

• Depth first traversal is where we prioritize going through the depth (height) of the tree first.

• depth first traversal methods:

• pre-order

• in-order

• post-order

• breadth first

• Breadth first traversal iterates through the tree by going through each level of the tree node-by-node.

binary trees

• on Binary tree the number of children is restricted to two with out specific sorting order.

k-ary trees

• on k-ary trees the number of children is more than two.

Binary search trees

• A Binary Search Tree is a type of tree that does have some structure attached to it. In a binary search tree, nodes are organized in a manner where all values that are smaller than the root are placed to the left, and all values that are larger than the root are placed to the right.

codefellows

HOME