Binary tree: Difference between revisions
m don't link to "tree" which is too generic (use "tree data structure" instead) |
Restructured, corrected, added notes on the correspondence between ordered trees and binary trees. |
||
| Line 1: | Line 1: | ||
A '''binary tree''' is |
A '''binary tree''' is an [[ordered tree data structure|ordered tree]] [[data structure]] in which each node has at most two [[child node|children]]. Typically the child nodes are called ''left'' and ''right''. One use of binary trees is as [[binary search tree]]s. |
||
There is a one-to-one mapping between general ordered trees and binary trees which [[Lisp]] uses to represent general ordered trees as binary trees. Each node N in the ordered tree corresponds to a node N' in the binary tree; the ''left'' child of N' is the node corresponding to the first child of N, and the ''right'' child of N' is the node corresponding to the N's next sibling --- that is, the next node among N's parent's children. |
|||
One way of thinking about this is that each node's children are in a [[linked list]], chained together with their ''right'' fields, and the node only has a pointer to the beginning of this list. |
|||
See [[binary search tree]] |
|||
Revision as of 17:39, 25 October 2001
A binary tree is an ordered tree data structure in which each node has at most two children. Typically the child nodes are called left and right. One use of binary trees is as binary search trees.
There is a one-to-one mapping between general ordered trees and binary trees which Lisp uses to represent general ordered trees as binary trees. Each node N in the ordered tree corresponds to a node N' in the binary tree; the left child of N' is the node corresponding to the first child of N, and the right child of N' is the node corresponding to the N's next sibling --- that is, the next node among N's parent's children.
One way of thinking about this is that each node's children are in a linked list, chained together with their right fields, and the node only has a pointer to the beginning of this list.