|
1
|
|
|
2
|
- A tree consists of a collection of elements or nodes, with each node
linked to its successors
- The node at the top of a tree is called its root
- The links from a node to its successors are called branches
- The successors of a node are called its children
- The predecessor of a node is called its parent
|
|
3
|
- Each node in a tree has exactly one parent except for the root node,
which has no parent
- Nodes that have the same parent are siblings
- A node that has no children is called a leaf node
- A generalization of the parent-child relationship is the
ancestor-descendent relationship
|
|
4
|
- A subtree of a node is a tree whose root is a child of that node
- The level of a node is a measure of its distance from the root
|
|
5
|
- In a binary tree, each node has at most two subtrees
- A set of nodes T is a binary tree if either of the following is true=
- T is empty
- Its root node has two subtrees, TL and TR, such that TL and TR are
binary trees
|
|
6
|
- Expression tree
- Each node contains an operator or an operand
- Huffman tree
- My book it’s page 402, your’s might be different depend=
ing
on what version you have.
- Binary search trees
- All elements in the left subtree precede those in the right subtree=
|
|
7
|
|
|
8
|
- Trees grow from the top down
- Each new value is inserted in a new leaf node
- A binary tree is full if every node has two children except for the
leaves
|
|
9
|
- Go over the Self-Check Exercises for 8.1
|
|
10
|
- Often we want to determine the nodes of a tree and their relationshi=
p
- Can do this by walking through the tree in a prescribed order and
visiting the nodes as they are encountered
- This process is called tree traversal
- Three kinds of tree traversal
- Inorder
- Preorder
- Postorder
|
|
11
|
- Preorder: Visit root node, traverse TL, traverse TR
- Inorder: Traverse TL, visit root node, traverse TR
- Postorder: Traverse TL, Traverse TR, visit root node
|
|
12
|
- An inorder traversal of a binary search tree results in the nodes be=
ing
visited in sequence by increasing data value
- An inorder traversal of an expression tree inserts parenthesis where
they belong (infix form)
- A postorder traversal of an expression tree results in postfix form<=
/li>
|
|
13
|
- Go over the Self-Check Exercises for 8.2
|
|
14
|
|
|
15
|
- Binary search tree definition
- A set of nodes T is a binary search tree if either of the following=
is
true
- T is empty
- Its root has two subtrees such that each is a binary search tree a=
nd
the value in the root is greater than all values of the left subtr=
ee
but less than all values in the right subtree
|
|
16
|
|
|
17
|
|
|
18
|
|
|
19
|
|
|
20
|
|
|
21
|
- Go over the Self-Check Exercises for 8.4
|