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

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''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.

Навигация