Topic 5-1:
Introduction to Tree and Binary Tree
Data Structures
Copyright By PowCoder代写 加微信 powcoder
Linear Data Structures
The data element are visited sequentially where only a single element can be directly reached:
Properties, Operations, Complexity Analysis, Application
How about non-linear data structures?
Tree, Graph.
A non-linear data structure is a data structure in which a data item is connected to several other data items. So that a given data item has the possibility to reach one-or-more data items.
What is a Tree
Binary Tree
Binary Search Tree
ADT, implementation, application, complexity analysis
Why should you care?
So pay attention!
And because you’ll be asked about them in job interviews and on exams.
Trees are used to organize data in many software applications, including:
Databases (B-TREES)
Data Compression ( )
Bitcoin ( )
Medical Diagnosis (Decision Trees)
A Tree is a special linked data structure
that has many uses in Computer Science:
To organize hierarchical data
A Family Tree
A Tree is a special linked data structure
that has many uses in Computer Science:
To organize hierarchical data
To make information easily
searchable
A Binary Search Tree
A Tree is a special linked data structure
that has many uses in Computer Science:
To organize hierarchical data
To make information easily
searchable
To simplify the evaluation of
mathematical expressions
An Expression Tree
A Tree is a special linked data structure
that has many uses in Computer Science:
To organize hierarchical data
To make information easily
searchable
To simplify the evaluation of
mathematical expressions
To make decisions
have a fever?
Does he/she
have spots on
his/her face?
Does he/she
have a sore
A Decision Tree
Edge and Path in Tree
An edge is a line between two nodes, or a node and a leaf.
A path starts from a node and ends at another node or a leaf:
When we talk about a path, it includes all nodes and all edges along the path, not just edges.
The direction of a path is strictly from top to bottom and cannot be changed in middle.
In the diagram, we can’t really talk about a path from B to F although B is above F.
Height of Node
Height of node – The height of a node is the number of edges on the longest downward path between that node and a leaf.
Every node has height. So B can have height, so does A, C and D.
Leaf cannot have height (height of 0) as there will be no path starting from a leaf.
It is the longest path from the node to a leaf.
Question: So A’s height ?
The height of the root is ?.
is the number of edges of the path to E, NOT to G. And its height is 3.
Height of Tree
Height of tree –The height of a tree is the number of edges on the longest downward path between the root and a leaf.
So the height of a tree is the height of its root.
The height of the root is 3
The height of the root is 1
Depth of Node
Depth –The depth of a node is the number of edges from the node to the tree’s root node.
the depth of the root is 0
Question: depth of B?
Depth of D?
Level of Node
Level – The level of a node is defined by 1 + the number of connections between the node and the root.
Simply, level is (depth + 1).
Basic Tree Facts
Trees are made of nodes (just like linked list nodes).
2. The top node of a tree
is called its “root” node.
3. Every node may have zero
or more “children” nodes.
4. A node with 0 children is
called a “leaf” node.
5. A tree with no nodes is
called an “empty tree.”
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
2 children
0 children
Empty tree
Tree Nodes Can Have Many Children
A tree node can have more than just two children:
class Node:
def __init__(self, data):
self.child1 = None
self.child2 = None
self.child3 = None
self.data = data
class Node:
def __init__(self, data):
self.children = []
self.data = data
Binary Trees
A binary tree is a special form of tree. In a binary tree, every node has at most two children nodes:
A left child and a right child.
class BTNode:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
A Binary Tree
Binary Trees
An arithmetic expression can be represented by a binary tree whose leaves are associated with variables or constants, and whose internal nodes are associated with one of the operators +, −, ×, and /.
((((3 +1)×3)/((9 −5)+2))−((3×(7−4)) +6))
Binary Tree Subtrees
We can pick any node in the tree…
like this node…
And then focus on its “subtree” – which includes it and all of nodes below it.
This subtree includes four different nodes…
It has the “leon” node
as its root.
If we pick a node from our tree…
Carey’s left subtree
Carey’s right subtree
like this node…
we can also identify its left and right sub-trees.
Binary Tree Subtrees
A Recursive Binary Tree Definition
Valid Tree?
There is a single unique path along the edges from the root to any particular node.
Full vs. Complete Binary Trees
Definition of Full Binary Tree:
A binary tree is full if each node is either a leaf or possesses exactly two child nodes.
=> every node has 0 or 2 children
Is it full?
Is it full?
Definition of Complete Binary Tree: A binary tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.
Is it complete?
Is it complete?
Full vs. Complete Binary Trees(con’t)
Definition of Full Binary Tree:
=> every node has 0 or 2 children
Definition of Complete Binary Tree: A binary tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.
Full vs. Complete Binary Trees(con’t)
Types of Binary Trees
Full and complete
Complete but not Full
Full but not complete
Neither complete nor full.
Full & Complete
Neither complete nor full
Complete but not Fall
Full but not complete
Operations on Binary Trees
traverse all the items
searching for an item
adding a new item at a certain position on the tree
deleting an item
deleting the entire tree (destruction)
removing a whole section of a tree (called pruning)
adding a whole section to a tree (called grafting)
The following are common operations that we might perform on a Binary Tree:
A Simple Tree Example
class BTNode:
def __init__(self, data):
self.left = None
self.right = None
self.value = data
Def main():
BTNode temp
pRoot = new BTNode(5)
temp = new BTNode(7)
pRoot.left = temp
temp = new BTNode（-3）
pRoot.right = temp
As with linked lists, we use dynamic memory to allocate our nodes.
Binary Tree Traversals
When we iterate through all the nodes in a tree, it’s called a traversal.
Each technique differs in the order that each node is visited during the traversal:
1. Pre-order traversal
2. In-order traversal
3. Post-order traversal
4. Level-order traversal -next lecture
Any time we traverse through a tree, we always start with the root node.
There are four common ways to traverse a tree.
The Preorder Traversal
1. Process the current node.
2. Process the nodes in the left
3. Process the nodes in the right
By “process the current node” we typically mean one of the following:
Print the current node’s value out.
Search the current node to see if its value matches the one you’re searching for.
Add the current node’s value to a total for the tree
PreOrder(Node cur):
if cur == None： // if empty, return…
print (cur.value) // Process the current node.
PreOrder(cur.left) // Process nodes in left sub-tree.
PreOrder(cur.right) // Process nodes in right sub-tree.
The Pre-order Traversal
PreOrder(root)
PreOrder(Node cur):
if cur == None : // if empty, return…
print (cur.value) // Process the current node.
PreOrder(cur.left) // Process nodes in left sub-tree.
PreOrder(cur.right) // Process nodes in right sub-tree.
PreOrder(Node cur):
if cur == None: // if empty, return…
print (cur.value) // Process the current node.
PreOrder(cur.left) // Process nodes in left sub-tree.
PreOrder(cur.right) // Process nodes in right sub-tree.
The In-order Traversal
Process the nodes in the left sub-tree.
Process the current node.
Process the nodes in the right sub-tree.
InOrder(Node cur) :
if cur == None: // if empty, return…
InOrder(cur.left) // Process nodes in left sub-tree.
print(cur.value) // Process the current node.
InOrder(cur.right) // Process nodes in right sub-tree.
The Post-order Traversal
Process the nodes in the left sub-tree.
Process the nodes in the right sub-tree.
Process the current node.
PostOrder(cur):
if (cur == None) // if empty, return…
PostOrder(cur->left); // Process nodes in left sub-tree.
PostOrder(cur-> right); // Process nodes in right sub-tree.
print(cur.value); // Process the current node.
An Easy Way to Remember the Order of Pre/In/Post Traversals
Starting just above-left of the root node, draw a loop counter-clockwise around all of the nodes.
Pre-order Traversal: Dot on the LEFT
Pre-order:
F B A D C E G I H
To determine the order of nodes visited in a pre-order traversal…
Draw a dot next to each node as you pass by its left side.
The order you draw the dots is the order of the pre-order traversal!
Draw a dot next to each node as you pass by its under-side.
A B C D E F G H I
The order you draw the dots is the order of the in-order traversal!
In-order Traversal: Dot UNDER the node
To determine the order of nodes visited in a in-order traversal…
To determine the order of nodes visited in a post-order traversal…
Draw a dot next to each node as you pass by its right side.
Post-order:
A C E D B H I G F
The order you draw the dots is the order of the post-order traversal!
Post-order Traversal: Dot on the RIGHT
Level of Node
Level – The level of a node is defined by 1 + the number of connections between the node and the root.
Simply, level is (depth + 1).
To determine the order of nodes visited in a level-order traversal…
Start at the top node and draw a horizontal line left-to-right through all nodes on that row.
Level-order:
F B G A D I C E H
The order you draw the lines is the order of the level-order traversal!
Level-order Traversal: Level-by-level
Repeat for all remaining rows.
In a level order traversal we visit each level’s nodes, from left to right, before visiting nodes in the next level
Pre-order:
F B A D C E G I H
A B C D E F G H I
Post-order:
A C E D B H I G F
The Level Order Traversal
How to implement?
Can we recursively process subtree?
METHOD 1 (Use function to print a given level)
printLevelorder(tree)
for d = 1 to height(tree)+1
printGivenLevel(tree, d);
/*Function to print all nodes at a given level*/
printGivenLevel(tree, level)
When to process current node?
What if level=1?
What if level>1?
else if level greater than 1, then printGivenLevel(tree->left, level-1); printGivenLevel(tree->right, level-1);
Using Queue
Use a temp variable and a queue
Insert the root node into the queue.
While the queue is not empty:
Dequeue the top node and put it in temp.
Process the node.
Enqueue the node’s children to queue if they are not None.
Big-O of Traversals
Question: What’re the big-Os of each of our traversals?
Answer: Well, since a traversal must visit each node
exactly once…
and since there are n nodes in a tree…
the big-oh for any of the traversals is…
PreOrder(Node cur):
if (cur == None)
print(cur.value)
PostOrder(cur.left)
PostOrder(cur.right)
Saving and Restoring Binary Trees
i.e., Serialize and Deserialize a Binary Tree
Converting a data structure or object into a sequence of bits
so that it can be stored in a file or memory buffer,
or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Saving and Restoring Binary Trees
The content of the tree must be stored in a file if we want to recover and se it at a later time
The stored information must enable reconstruction of an exact copy of the original tree.
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
Saving and Restoring Binary Trees
How about saving trees using traversals?
Pre-order?
Saving and Restoring Binary Trees
Save/reconstruct using pre-order traversal + additional info
O(content inside node) +
D(whether the node has left, right, both/neither subtrees)
(A,2) (E,0) (D,2) (B,0) (C,R) (F,0)
(A,2) (E,2) (D,0) (B,0) (C,R) (F,0)
Saving and Restoring Binary Trees
How about reconstruction?
(A,2) (E,0) (D,2) (B,0) (C,R) (F,0)
rebuildTree():
/*read next (O,D) pair from the file */
t = new Tree(O)
If ((D==2)||(D==L)):
t.attachL(rebuildTree())
If ((D==2)||(D==R)):
t.attachR(rebuildTree())
Note: not a complete code!
Restoring Expression Tree
An arithmetic expression can be represented by a binary tree whose leaves are associated with variables or constants, and whose internal nodes are associated with one of the operators +, −, ×, and /.
((((3 +1)×3)/((9 −5)+2))−((3×(7−4)) +6))
Application: Expression Evaluation
We can evaluate arithmetic expressions using a stack.
4 5 6 * + => 4+5*6 =34
Expression Evaluation
We can represent arithmetic expressions using a binary tree.
For example, the tree on the left represents the expression: (5+6)*(3-1)
Once you have an expression in a tree, its easy to evaluate it and get the result.
Let’s see how!
What’s the benefit?
Expression Evaluation
If the current node is a number, return its value.
Recursively evaluate the left subtree and get the result.
Recursively evaluate the right subtree and get the result.
Apply the operator in the current node to the left and right results return the result.
(5+6)*(3-1)
Here’s our evaluation function. We start from the root.
If the current node is a number, return its value.
Recursively evaluate the left subtree and get the result.
Recursively evaluate the right subtree and get the result.
Apply the operator in the current node to the left and right results return the result.
If the current node is a number, return its value.
Recursively evaluate the left subtree and get the result.
Recursively evaluate the right subtree and get the result.
Apply the operator in the current node to the left and right results return the result.
Expression Evaluation
If the current node is a number, return its value.
Recursively evaluate the left subtree and get the result.
Recursively evaluate the right subtree and get the result.
Apply the operator in the current node to the left and right results return the result.
(5+6)*(3-1)
Here’s our evaluation function. We start from the root.
If the current node is a number, return its value.
Recursively evaluate the left subtree and get the result.
Recursively evaluate the right subtree and get the result.
Apply the operator in the current node to the left and right results return the result.
Result = 5
If the current node is a number, return its value.
Recursively evaluate the left subtree and get the result.
Recursively evaluate the right subtree and get the result.
Apply the operator in the current node to the left and right results return the result.
Expression Evaluation
If the current node is a number, return its value.
Recursively evaluate the left subtree and get the result.
Recursively evaluate the right subtree and get the result.
Apply the operator in the current node to the left and right results return the result.
(5+6)*(3-1)
Here’s our evaluation function. We start from the root.
If the current node is a number, return its value.
Recursively evaluate the left subtree and get the result.
Recursively evaluate the right subtree and get the result.
Apply the operator in the current node to the left and right results return the result.
Result = 5
Result = 6
Expression Evaluation
If the current node is a number, return its value.
Recursively evaluate the left subtree and get the result.
Recursively evaluate the right subtree and get the result.
Apply the operator in the current node to the left and right results return the result.
(5+6)*(3-1)
Here’s our evaluation function. We start from the root.
Result = 11
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com