4624
правки
Binary tree: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''Binary tree''' --- бинарное дерево. An '''<math>n</math>-node binary tree''' is defined to be a rooted tree where each of the <math>n</math> nodes…») |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Binary tree''' | '''Binary tree''' — ''[[бинарное дерево]].'' | ||
An '''<math>n</math>-node binary tree''' is defined to be a rooted tree where | An '''<math>n</math>-node binary tree''' is defined to be a [[root|rooted]] tree where | ||
each of the <math>n</math> nodes has zero, one or two ''descendants'', and a | each of the <math>n</math> [[node|nodes]] has zero, one or two ''[[descendant|descendants]]'', and a | ||
distinction is made between the left and right subtrees. | distinction is made between the left and right [[subtree|subtrees]]. | ||
One class of operation which may be performed on binary trees is that | One class of operation which may be performed on binary trees is that | ||
of traversing the whole tree: each node in the tree is "visited", or | of traversing the whole tree: each node in the tree is "visited", or | ||
"processed", exactly once in some predefined order. The three most | "processed", exactly once in some predefined order. The three most | ||
natural traversal orders are known as '' preorder, inorder and postorder'' (Knuth, 1975). Preorder and postorder traversals are also | natural traversal orders are known as ''[[preorder]], [[inorder traversal|inorder]] and postorder'' (Knuth, 1975). Preorder and postorder traversals are also | ||
commonly called ''depth-first'' and ''bottom-up traversals'', | commonly called ''[[depth-first search (DFS)|depth-first]]'' and ''bottom-up traversals'', | ||
respectively, though these latter terms are normally used in | respectively, though these latter terms are normally used in | ||
connection with more general types of trees. | connection with more general types of trees. | ||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||