?? trees part 2 - binary trees.html
字號:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>GameDev.net - Trees Part 2: Binary Trees</TITLE>
<META http-equiv=Content-Type content="text/html; charset=windows-1252">
<META content="MSHTML 6.00.2600.0" name=GENERATOR><LINK
href="Trees Part 2 - Binary Trees_files/reference.css" type=text/css
rel=STYLESHEET><LINK href="/pics/gdicon.png" type=image/png rel=icon>
<META DESCRIPTION=""></HEAD>
<BODY text=#000000 vLink=#666699 aLink=#000000 link=#666699 bgColor=#ffffff>
<TABLE cellSpacing=0 cellPadding=5 width="100%" border=0>
<TBODY>
<TR>
<TD class=tblhdr>Trees Part 2: Binary Trees</TD>
<TD class=tblhdr align=right><IMG height=16
src="Trees Part 2 - Binary Trees_files/littleg.gif" width=16
align=absBottom> <A href="http://www.gamedev.net/"><SPAN
style="COLOR: white; TEXT-DECORATION: none">GameDev.net</A></SPAN></TD></TR>
<TR>
</TR></TBODY></TABLE>
<P align=center><SPAN class=title>Trees Part 2: Binary Trees</SPAN> <BR><SPAN
class=author>by <A href="mailto:RonPenton@hotmail.com">Ron Penton</A></SPAN></P>
<P><A
href="Trees Part 2.zip">Click
here</A> to get the demo program and code samples.
<P>I was talking to some people about ideas for this article, and when I
proposed that it be about simple binary trees, someone said that games have no
need for these, and that I should do something closer to game programming, such
as BSP trees. I beg to differ here, actually. While the beginner may think that
game programming is all about graphics, they are leaving out a critical part of
the equation. Games these days are becoming incredibly large, and long dead are
the days when a single hacker can throw together a game. It takes engineering
skills and discipline, and most of all, an understanding in the basic concepts
of data structures. Without knowing what data structures exist, and what they
can do, how can anyone ever hope to make a large complex world that doesn抰
choke the current line of computers? I feel that leaning about the basic data
structures that have been developed and tested ever since computers were
invented is an essential part of game programming. Indeed, what good is a
carpenter who does not know how to use his tools? And now, without further ado,
I give you part II of the Tree抯 series.</P>
<P>Last time, we discussed recursion and the basic structure of trees. Now, I
would like to get into an important sub-section of hierarchal data structures:
Binary Trees. We all (hopefully) know that computers are binary machines, so it
makes quite a bit of sense that the most frequently used kind of tree in
computer programming is a binary tree. A Binary Tree is simply a tree in which
every node has a maximum two children. Binary trees can be used for many things,
such as efficient searching, arithmetic expression parsing, and data
compression, etc. Before we get into the details, there are a few terms and
definitions that need to be explained.</P>
<H1>Algorithm Analysis and Big-O Notation</H1>
<P>It is important to understand a little bit about how algorithms are rated for
efficiency. Michael Abrash has said that "<I>Without good design, good
algorithms, and complete understanding of the program抯 operation, your
carefully optimized code will amount to one of mankinds least fruitful creations
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -