📄 binary trees.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0038)http://www.allisons.org/ll/AlgDS/Tree/ -->
<HTML><HEAD><TITLE>Binary Trees, Data Structures and Algorithms</TITLE>
<META content="Binary Trees" name=description>
<META content="Binary Trees Tree traversal prefix infix postfix breadth-first"
name=keywords><!-- DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN" --><!-- GENERATOR = vi (Linux + Solaris) -->
<META content="MSHTML 6.00.2800.1605" name=GENERATOR>
<SCRIPT language=JavaScript>var REMOTE_HOST='(none)';</SCRIPT>
<SCRIPT language=JavaScript><!--REMOTE_HOST='77.200.166.218.in-addr.arpa domain name pointer 218-166-200-77.dynamic.hinet.net.';// --></SCRIPT>
<!-- Lloyd ALLISON, Victoria, Australia --><!-- Content-Type = text/html; charset=iso-8859-1 -->
<META http-equiv=Content-Type content="text/html; charset=utf-8"></HEAD>
<BODY text=#000000 vLink=#400090 link=#0000ff bgColor=#eeeeee
onload=if(top!=self)top.location=self.location;>
<TABLE cellSpacing=0 cellPadding=2 width="100%" border=0>
<TBODY>
<TR>
<TD align=middle><!-- BGCOLOR="#EEFFEE" -->
<H2>Binary Trees</H2></TD></TR></TBODY></TABLE>
<TABLE cellSpacing=0 cellPadding=2 width="100%" border=0>
<TBODY>
<TR>
<TD vAlign=top align=middle width="10%">
<TABLE cellSpacing=0 cellPadding=1 border=1><!-- left column -->
<TBODY>
<TR>
<TD><A href="http://www.allisons.org/ll/"
target=_top>LA home</A><BR><A
href="http://www.allisons.org/ll/Computing/"
target=_top>Computing</A><BR><!-- Left extras for children NB. relative to children --><A
href="http://www.allisons.org/ll/AlgDS/">Algorithms</A><BR> <A
href="http://www.allisons.org/ll/AlgDS/Glossary/">glossary</A><BR> <B>Binary Trees</B><BR><!-- Left Extras Here --> <A
href="http://www.allisons.org/ll/AlgDS/Tree/#search"
target=_top><FONT
size=-1>#Search T'</FONT></A><BR> <A
href="http://www.allisons.org/ll/AlgDS/Tree/#AVL" target=_top><FONT
size=-1>#AVL T'</FONT></A><BR> <FONT
size=-1><A href="http://www.allisons.org/ll/AlgDS/Tree/Search/"
target=_top>Search+AVL</A></FONT><BR> <A
href="http://www.allisons.org/ll/AlgDS/Tree/Trie/"
target=_top>Tries</A><BR> <A
href="http://www.allisons.org/ll/AlgDS/Tree/PATRICIA/"
target=_top>PATRICIA</A><BR> <A
href="http://www.allisons.org/ll/AlgDS/Tree/Suffix/"
target=_top>Suffix T'</A><BR><!-- Lloyd Allison --></TD></TR></TBODY></TABLE></TD>
<TD vAlign=top align=left width="80%">
<P>Trees are natural structures for representing certain kinds of
hierarchical data. A (rooted) tree consists of a set of <EM>nodes</EM> (or
vertices) and a set of <EM>arcs</EM> (or edges). Each arc links a parent
node to one of the parent's children. A special <EM>root</EM> node has no
parent. Every other node has exactly one parent. It is possible to reach
any node by following a unique path of arcs from the root. If arcs are
considered bidirectional, there is a unique path between any two nodes.
The simplest kind of tree is a binary tree where each parent has at most
two children.<BR><FONT size=-1>(We consider <EM>unrooted</EM> trees
elsewhere, e.g. in [<A
href="http://www.allisons.org/ll/AlgDS/Graph/Undirected/">minimum spanning
trees</A>].)</FONT> </P>
<P>A way to think of a <EM>binary tree</EM> is that it is either empty
(<TT>emptyTree</TT>) or it is a <TT>fork</TT> which contains an element
and two subtrees which are themselves binary trees. </P>
<DL>
<DD><PRE>Types:
type tree e = emptyTree | fork e × (tree e) × (tree e)
Operations:
empty: tree e -> boolean
leaf : tree e -> boolean
fork : e × tree e × tree e -> tree e
left : tree e -> tree e
right: tree e -> tree e
contents: tree e -> e
Rules:
empty(emptyTree) = true
empty(fork(x, T, T'))= false
leaf(fork(x, emptyTree, emptyTree)) = true
leaf(fork(x, T, T'))
= false, if not empty(T) or not empty(T')
leaf(emptyTree) = error
left(fork(x, T, T')) = T
left(emptyTree) = error
right(fork(x, T, T')) = T'
right(emptyTree) = error
contents(fork(x, T, T')) = x
contents(emptyTree) = error
<STRONG>The Tree Abstract Data Type.</STRONG>
</PRE></DD></DL>
<P>(It is also common to use curried versions of constructors and
functions, such as <TT>fork</TT>, especially in functional languages.)
</P>
<P>Many operations can be defined on trees. For example: </P>
<DL>
<DD><PRE>
height(emptyTree) = 0 |
height(fork(e,T,T')) = 1+max(height(T), height(T'))
weight(emptyTree) = 0 |
weight(fork(e,T,T')) = 1+weight(T)+weight(T')
</PRE></DD></DL>
<P>Note that these functions are binary-recursive as is the definition of
the tree type. <FONT size=-1>(<I>Also note that a tree consisting of a
single <EM>leaf</EM> is sometimes defined to be of height zero, rather
than 1, as here.</I>)</FONT> </P>
<P>Trees have many uses in computing. For example a <EM>parse-tree</EM>
can represent the structure of an expression: </P>
<DL>
<DD><PRE>
input: a+b*c
----------> +
. .
. .
a *
. .
. .
b c
</PRE></DD></DL>
<P>Multiplication has a higher <EM>priority</EM> then addition and binds
more tightly. This tree shows that a+b*c is interpreted as a+(b*c) rather
than as (a+b)*c. Such trees are used in compilers and other programs. </P>
<H3>Implementation of Binary Trees by Pointers and Records</H3>
<P>A tree data type can be implemented as a collection of records and
pointers. </P>
<DL>
<DD><PRE>[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/Tree.h" target=codewindow>Tree.h</A>]
[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/TreeElement.h" target=codewindow>TreeElement.h</A>]
</PRE></DD></DL>
<P>The basic operations can create new records and manipulate pointers.
</P>
<DL>
<DD><PRE>[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/Ops.c" target=codewindow>Ops.c</A>]
</PRE></DD></DL>
<P>Not surprisingly this tree implementation is similar to the
implementation of <A
href="http://www.allisons.org/ll/AlgDS/List/Lisp/">hierarchical lists</A>.
</P>
<P>An output routine for trees is a virtual necessity. A tree can be
printed in a style like that used for lists but a graphical
two-dimensional layout is more informative. It is difficult to print trees
down the page, because they quickly grow too wide, but it is relatively
easy to print them across the page so that the root is at the left and the
tree grows to the right. </P>
<DL>
<DD><PRE>[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/Write.c" target=codewindow>Write.c</A>]
</PRE></DD></DL>
<P>For an example of tree output, see later sections. </P>
<H3>Example: Parse Trees</H3>
<P>Parsing an input language according to a grammar is frequently
necessary in computing. Here we consider a language of simple arithmetic
expressions. A grammar written in Backus Naur form (BNF) is given below.
</P>
<DL>
<DD><PRE>
<exp> ::= <exp> + <term> | <term>
<term ::= <term> * <operand> | <operand>
<operand> ::= <identifier> | ( <exp> )
<identifier> ::= <letter> <identifier> | <letter>
<letter> ::= "a" | "b" | ... | "z"
<STRONG>Grammar for Simple Expression.</STRONG>
</PRE></DD></DL>
<P>The grammar can be read as a definition of the syntactic structure of
expressions, <exp>. The symbol `::=' can be read as `is' or `can be
replaced by'. The symbol `|' can be read as `or'. The names in angle
brackets, such as '<exp>', are variables for parts of the language.
The string <exp>+1 is not a legal expression but it stands for many
legal expressions such as x+1, y+1 and (x+y*z)+1. The first line of the
grammar can be read as: an <exp> is an <exp> plus <term>
or a <term>. An expression is either an expression plus a term or
just a term. Note that the syntax rules are recursive. A little thought
shows that an expression is a sequence of terms separated by plus signs.
Similarly, a term is a sequence of operands separated by multiplication
signs. An operand is either an identifier or a bracketed subexpression. An
identifier is a sequence of letters. </P>
<P>A parser can be written using the <EM>recursive-descent</EM> technique.
A procedure is written to recognise each class of object in the grammar -
exp, term, operand. These routines are recursive, as is the grammar, and
call each other to implement the grammar rules. For example, the routine
for expression calls the routine for term. The repetitive nature of
expressions and terms is coded by the use of a loops. A bracketed
subexpression is inherently recursive and so is the parser at that point.
The complete parser is given below. It is moderately long but not complex,
especially if read with the grammar in mind. A <EM>lexical</EM> routine,
insymbol, skips white space and packages input letters into identifiers
and other kinds of symbol. It is followed by the parser proper consisting
of the routines Operand, Term and Exp. </P>
<DL>
<DD><PRE>[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/Parser.h" target=codewindow>Parser.h</A>]
[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/Parser.c" target=codewindow>Parser.c</A>]
</PRE></DD></DL>
<P>Note the use of mutual recursion. Various errors may be detected during
parsing. If the expression is syntactically correct, the tree representing
its structure is finally printed. </P>
<DL>
<DD><PRE>
input: a + b*(c+d)
Parse Tree:
| | |d---------|
| |+---------|
| | |c---------|
|*---------|
| |b---------|
+---------|
|a---------|
</PRE></DD></DL>
<P></P>
<H3>Recursive Tree Traversal</H3>
<P>There are three classic ways of recursively <EM>traversing</EM> a tree
or of visiting every one of its nodes once. In each of these, the left and
right subtrees are visited recursively and the distinguishing feature is
when the element in the root is visited or processed. </P>
<P>In a <EM>preorder</EM> or <EM>prefix</EM> traversal the root is visited
first (pre) and then the left and right subtrees are traversed. </P>
<DL>
<DD><PRE>[<A href="http://www.allisons.org/ll/ProgLang/C/Tree/" target=codewindow>C/Tree</A>/<A href="http://www.allisons.org/ll/ProgLang/C/Tree/Prefix.c" target=codewindow>Prefix.c</A>]
</PRE></DD></DL>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -