Trees Flashcards
In what way is a tree hierarchical?
More general things are at the top and more specific things are at the bottom.
In any type of tree, are children of one node independent of children of another node?
Yes.
In any type of tree, are leaf nodes unique?
Yes, no leaf node should be accessible from more than one parent node.
What is an edge?
A connection between two nodes, showing a relationship between them.
How many incoming edges are connected to any one node in a tree (not including the root node)?
Exactly one incoming edge from another node.
How many outgoing edges are connected to any one node in a tree?
Each node may have several outgoing edges.
What is the level of a node within a tree?
The level of a node ‘n’ is the number of edges on the path from the root node to ‘n’.
What is the level of the root node of a tree?
0.
What is the height of a tree?
The height of a tree is equal to the maximum level of any node in the tree.
What property defines a binary tree?
If each node in the tree has a maximum of two children, we say that the tree is a binary tree.
Name the three commonly used tree traversal patterns.
Preorder; inorder; and postorder.
How is preorder tree traversal carried out?
The root node is visited first, then recursively preorder traverse the left subtree, followed by recursively preorder traversing the right subtree.
How is inorder tree traversal carried out?
Recursively do an inorder traversal of the left subtree, visit the root node, and finally recursively do an inorder traversal of the right subtree?
How is postorder tree traversal carried out?
Recursively do a postorder traversal of the left subtree and right subtree followed by a visit to the root node.
What is the heap order property?
In a heap, for every node X with parent P, the key in P is smaller than or equal to the key in X.
