Fichas
Trees
Fichas del conjunto (14)
- 1define linear vs non-linear collectionslists are linear, there is a perv and next
rooted trees are non-linear - 2define: rooted tree nodes/vertices & edges siblings leaf internal path & length of a path depth of a node & height of a node height of a tree ancestor & descendent subtreeset of nodes and edges which are ordered pairs
edge(v1,v2) goes from vertex 1 to 2
have the same parent
node with no children (external node)
node with a child (not a leaf)
sequence of nodes; vi is parent of vi+1
length: number of edges
also called level, length of unique path from root to node
max length of path from node to leaf
height of root node
if there is a path from v to w, v ancestor of w, w descendent of v
subset of nodes and edges which is itself a tree - 3recursive def of a rooted treeA rooted tree T either has no nodes (empty tree), or it consists of a root node r together with a set of zero or more non-root nodes, and these non-root nodes are partitioned into non-empty subtrees T1; ...; Tk whose roots are the children of r.
Note the word 'partition' here, which means that the subtrees are disjoint (they don't share any nodes). - 4depth alg
- 5height alg
- 6Tree implementation in Javadefine children with array list
or linked list
- 7first child, next sibling imprementationdefines a singly linked list for the siblings, where the head is the firstChild and the next is the nextSibling. It is simpler than the arraylist implementation since it uses just two xed references at each node (or 3, if one also has a parent link)
- 8rooted tree implementationThe root here serves the same role as the head held in our implementation of SLinkedList. It gives you access to the nodes of the tree. The TreeNode class would then be defined as an inner class inside this Tree class.
- 9representing trees using lists
- 10name the 3 kind of traversalsdepth first using recursion (pre-order/post-order)
depth first without recursion
breadth first - 11depth first recursion pre-ordervisit node then all its children.
- 12depth first recursion post-ordervisit the children of the node and their children recursively, then the node.
- 13depth first without recursionAvoid recursion using a stack.
- 14breadth first traversalvisits all the nodes at each depth before proceeding to the next depth.
Información
- Descripción
- Computer Science Fichas sobre Trees, creado por Virginie Gagné el 15/04/2022.
- Creado por
- Virginie Gagné
- Visitas
- 0
- Valoración