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: | ||
'''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. | ||
Версия от 17:20, 21 февраля 2012
Binary tree — бинарное дерево.
An [math]\displaystyle{ n }[/math]-node binary tree is defined to be a rooted tree where each of the [math]\displaystyle{ n }[/math] nodes has zero, one or two descendants, and a distinction is made between the left and right subtrees.
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 "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 commonly called depth-first and bottom-up traversals, respectively, though these latter terms are normally used in connection with more general types of trees.