Tree part 1
.pdfДвумерный массив
int T[n][4];
T[ i ][0] is data T[ i ][1] is left T[ i ][2] is right
T[ i ][3] is parent
11
Массив структур
struct TREE { type data;
int |
left; |
int |
right; |
int |
parent; |
int |
brother; |
};
TREE tree [n];
12
Структура узла с указателями
Структура узла бинарного дерева: struct TREE // NODE !
{ int data; // полезные данные, key TREE *left, *right, *parent;
//ссылки на левого и правого сыновей
};
Структура узла любого (не бинарного) дерева: struct TREE
{ int data; // полезные данные, key TREE **child, *parent;
//ссылки на всех сыновей
};
13
Height Tree
int HeightTree(TREE *p) { int left, right;
if(!p) return -1; left=HeightTree(p->left); right=HeightTree(p->right); if(left>right) return left+1; else return right+1;
} // HeightTree
14
Count & Depth Tree
int CountTree(TREE *p) { int left, right;
if(!p) return 0;
return CountTree(p->left) + CountTree(p->right) + 1; } // CountTree
int DepthTree(TREE *tree) // Current Level { int i; TREE *p=r; if( !p ) return 0;
for(i=0; p->parent; i++) p=p->parent;
return i;
} // DepthTree
15
Обход деревьев - перечисление и обработка
всех узлов в определённом порядке
Вглубину
1.Прямой r a b или r b a
2.Обратный a b r или b a r
r
3. Симметричный a r b или b r a
a b
В ширину r ; a b
16
Прямой обход дерева r a b
int TraversePre(TREE *p, int eval (TREE *p)) // PreOrder
{ if(!p) return 0; |
a |
|
|
|
eval(p); |
|
|
|
|
|
|
|
TraversePre(p->left, eval); |
|
|
|
TraversePre(p->right, eval); b |
|
c |
|
return 1; |
|
|
} |
d |
e |
f |
|
|||
g h j
a b d c e g f h j
17
Обратный обход дерева a b r
int TraversePost(TREE *p, int eval (TREE *p)) // PostOrder
{if(!p) return 0; TraversePost(p->left, eval );
TraversePost(p->right, eval );
a
eval(p); return 1;
}
b c
d |
e |
f |
g h j
d b g e h j f c a
18
Симметричный обход дерева a r b
int TraverseSym(TREE *p, int eval(TREE *p)) // InOrder
{ if(!p) return 0; |
a |
|
|
|
TraverseSym (p->left, eval); |
|
|
|
|
|
|
|
eval(p); |
|
|
|
TraverseSym(p->right, eval); b |
|
c |
|
return 1; |
|
|
} |
d |
e |
f |
|
|||
g h j
d b a e g c h f j
19
|
Прямой нерекурсивный |
|
|
|
обход дерева |
|
|
|
int WalkPre(TREE *tree, int eval(TREE *p) ) / / прямой |
|
|
{ |
if(!tree) return 0; int count; TREE *p=r; |
|
|
|
STACK Stack; Stack.top = 0; |
|
|
|
Push(Stack, p); |
|
|
|
while ( Stack.top >0 ) |
|
|
|
{ Pop(Stack, p); |
|
|
|
eval (p); |
|
|
|
if(p->right) Push(Stack, p->right); |
|
|
|
if(p->left) Push(Stack, p->left); |
|
|
|
count++; |
|
|
} // while |
|
|
|
|
return count; |
|
|
} |
// WalkPre |
20 |
|
|
|
||
|
|
|
|