Tree ++++
.pdf
Обход дерева в ширину
int WalkWidth (TREE *tree, int eval (TREE p)) |
|
{ TREE *p=r,*q[n]; int head=0, free=0, i; |
a |
if(!p) return i; |
q[free++]=p;
while ( head != free ) b { p = q [ head++ ];
eval (p);
if( p->left) q[ free++ ] =p->left; d if(p->right) q[ free+ +]=p->right;
} // while return i;
} // WalkWidth
c
e f
g h j
в очереди: 
a b c d e f g h j
результат: a b c d e f g h j |
21 |
|
Tree в одну строчку
a
b c
d |
e |
f |
g h j
r a b: (a,(b, d),(c,(e, ,g),(f, h, j)))
22
Двоичные деревья поиска
Binary Search Tree BST
Ключ – это характеристика узла, по которой выполняется поиск (чаще всего – одно из полей структуры).
Закономерность узлов |
13 15 4 9 7 21 3 |
||
Слева от каждого узла находятся |
|
|
13 |
узлы с меньшими ключами, а справа |
|
|
|
– с бóльшими. |
|
4 |
15 |
|
|
|
|
Как искать ключ, равный key: |
3 |
9 |
21 |
1) если дерево пустое, ключ не найден; |
|
7 |
|
|
|
|
|
2)если ключ узла равен key, то стоп.
3)если ключ узла меньше key , то искать x в левом поддереве;
4)если ключ узла больше key, то искать x в правом
поддереве. |
23 |
|
Двоичные деревья поиска
Поиск в неотсортированном массиве: N
Поиск в сортированном массиве: log N
Поиск по дереву:
|
|
13 |
При каждом сравнении |
|
|
|
|
|
4 |
15 |
отбрасывается половина |
|
оставшихся элементов. |
||
|
|
|
|
3 |
9 |
21 |
Высота дерева ~ log2N. |
|
|
|
Число сравнений ~ log2N. |
|
7 |
|
|
1)нужно заранее построить дерево
2)дерево должно быть минимальной высоты
3) много включений и исключений |
24 |
|
Прохождение BST
|
|
13 |
|
4 |
15 |
3 |
9 |
21 |
7
1) |
В ширину: |
13 |
4 |
15 3 |
9 21 7 |
2)Прямой : |
13 |
4 |
3 9 |
7 15 21 |
|
3) |
Обратный: |
3 |
7 |
9 4 |
21 15 13 |
4) |
Симметричный: 3 |
4 |
7 9 13 15 21 |
||
25
Insert Node to Tree
TREE *TreeInsert(TREE *&tree, TREE *&node)
{TREE *q=tree, *p; if(!tree)
{tree=node; tree->parent=0;
tree->left=0; tree->right=0; return tree; } while(q)
{ p=q;
if(node->key < p->key)
{ q=p->left; if(!q) {p->left=node; node->parent=p;}} else
{ q=p->right; if(!q) {p->right=node; node->parent=p;} }
}
return p;
26
} // TreeInsert
Tree Search
TREE *TreeSearchRec(TREE *tree, int key) { if(!tree || key== tree->key) return tree;
if(key < tree->key) return TreeSearchRec (tree->left, key); else return TreeSearchRec (tree->right, key);
} // TreeSearchRec
TREE *TreeSearchIter (TREE *tree, int key) { if(!tree || key==tree->key) return tree;
while(tree && key!=tree->key)
{ if(key < tree->key) tree=tree->left; else tree=tree->right;
}
return tree;
} // TreeSearchIter |
27 |
|
Tree Min
TREE *TreeMin (TREE *tree) { TREE *p=tree;
while(p->left) p=p->left; return p;
} // TreeMin
TREE *TreeMinRec(TREE *tree) { TREE *p=tree;
if(p->left==0) return p; return TreeMin (p->left);
} // TreeMinRec
28
Tree Max
TREE *TreeMax(TREE * tree) { TREE *p= tree;
while(p->right) p=p->right; return p;
} // TreeMax
TREE *TreeMaxRec(TREE *tree) { TREE *p= tree;
if(p->right==0) return p; return TreeMax(p->right);
} // TreeMaxRec
29
Delete Node from BST
a |
20 |
b |
|
|
|
|
12 |
|
|
31 |
|
|
|
|
|
|
|
|
4 |
|
15 |
|
23 |
|
64 |
|
|
|
|
|
||
3 |
9 |
|
|
25 |
50 |
76 |
|
19 |
21 |
|
|
||
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
10 |
|
|
|
|
30