Embed Size (px)
Citation preview
Arboles
Ing. Andrea Quan
Árboles (Trees) • Una estructura de árbol es una estructura de
datos compuesta por vértices conectados entre si por medio de arcos
Rooted Tree • Un rooted tree es una estructura de árbol en
donde existe un vértice principal al que se le llama raiz (root).
• A los vértices en un rooted tree se les llaman nodos.
Rooted Tree • Un rooted tree, al igual que cualquier estructura
de árbol, es una estructura dinámica. • La única referencia directa que se tiene es a la
raiz.
raiz
Rooted Tree • Un rooted tree se divide en niveles dependiendo
cuantas conecciones existen entre un nodo determinado y la raíz.
• Su altura esta determinada por cuantos niveles tiene
raiz
Level 2
Level 3
Level 1
Height = 3
Rooted Tree padre
hijo
hermanos
Rooted Tree
x
ancestros de x
x
descendientes de x
Rooted Tree
root
Sub - arbol
Rooted Tree
HOJAS
Binary Tree • Un binary tree es un rooted tree en donde cada
nodo solo puede tener cero, uno o dos hijos. • Se puede definir recursivamente como:
Un árbol binario es: un rooted tree compuesto por un nodo raíz el cual tiene un subárbol binario izquierdo, y un subárbol binario derecho.
En Java…
La estructura se divide en dos tipos de objeto: • Nodo
– Referencia al padre (no necesariamente) – Referencia al hijo izquierdo – Referencia al hijo derecho – dato
• BinaryTree – Referencia a raíz
Representación de un BinaryTree RAIZ
Clase BTNode
Clase BinaryTree
Formas de recorrer un Binary Tree
Formas de recorrer un Binary Tree
Existen tres formas de recorrer un Binary Tree. Cada una de ellas se aplica a un árbol binario y funcionan en forma recursiva.
• Preorder
– Visita el root, después aplica preorder al subárbol izquierdo y al subárbol derecho.
• Inorder – Aplica inorder al subarbol izquierdo, después visita al
root, y después aplica inorder al subarbol derecho. • Postorder
– Aplica postorder al subarbol izquierdo, después al subarbol derecho, y después visita al nodo.
Formas de recorrer un Binary Tree
Existen tres formas de recorrer un Binary Tree. Cada una de ellas se aplica a un árbol binario y funcionan en forma recursiva.
• Preorder
– Visita el root, después aplica preorder al subárbol izquierdo y al subárbol derecho.
• Inorder – Aplica inorder al subarbol izquierdo, después visita al
root, y después aplica inorder al subarbol derecho. • Postorder
– Aplica postorder al subarbol izquierdo, después al subarbol derecho, y después visita al nodo.
Formas de recorrer un Binary Tree
Existen tres formas de recorrer un Binary Tree. Cada una de ellas se aplica a un árbol binario y funcionan en forma recursiva.
• Preorder
– Visita el root, después aplica preorder al subárbol izquierdo y al subárbol derecho.
• Inorder – Aplica inorder al subarbol izquierdo, después visita al
root, y después aplica inorder al subarbol derecho. • Postorder
– Aplica postorder al subarbol izquierdo, después al subarbol derecho, y después visita al nodo.
Formas de recorrer un Binary Tree
Existen tres formas de recorrer un Binary Tree. Cada una de ellas se aplica a un árbol binario y funcionan en forma recursiva.
• Preorder
– Visita el root, después aplica preorder al subárbol izquierdo y al subárbol derecho.
• Inorder – Aplica inorder al subarbol izquierdo, después visita al
root, y después aplica inorder al subarbol derecho. • Postorder
– Aplica postorder al subarbol izquierdo, después al subarbol derecho, y después visita al nodo.
Ejemplo 1
2 3
4
6 5
7 8
9
10
11
Preorder 1
2 3
4
6 5
7 8
9
10
11
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2,4
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2,4,5
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2,4,5,6
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2,4,5,6,3
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2,4,5,6,3,7
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2,4,5,6,3,7,9
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2,4,5,6,3,7,9,11
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2,4,5,6,3,7,9,11,8
Preorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 1,2,4,5,6,3,7,9,11,8,10
Inorder 1
2 3
4
6 5
7 8
9
10
11
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5,4
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5,4,6
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5,4,6,1
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5,4,6,1,7
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5,4,6,1,7.11
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5,4,6,1,7,11,9
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5,4,6,1,7,11,9,3
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5,4,6,1,7,11,9,3,10
Inorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 2,5,4,6,1,7,11,9,3,10,8
Postorder 1
2 3
4
6 5
7 8
9
10
11
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6,4
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6,4,2
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6,4,2,11
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6,4,2,11,9
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6,4,2,11,9,7
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6,4,2,11,9,7,10
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6,4,2,11,9,7,10,8
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6,4,2,11,9,7,10,8,3
Postorder 1
2 3
4
6 5
7 8
9
10
11
Recorrido: 5,6,4,2,11,9,7,10,8,3,1
