Binary tree: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''Binary tree''' --- бинарное дерево. An '''<math>n</math>-node binary tree''' is defined to be a rooted tree where each of the <math>n</math> nodes…»)
 
Нет описания правки
 
Строка 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.

Текущая версия от 16:31, 23 октября 2018

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.

Литература

  • Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.