Arbol Binario

Binary Trees

Page: 1

Binary Trees

by Nick Parlante

This article introduces the basic concepts of binary trees, and then works through a series of practice problems with solution code in C/C++ and Java. Binary trees have an elegant recursive pointer structure, so they are a good way to learn recursive pointer algorithms.

Contents

Section 1. Binary Tree Structure -- a quick introduction to binary trees and the code that operates on them Section 2. Binary Tree Problems -- practice problems in increasing order of difficulty

Section 3. C Solutions -- solution code to the problems for C and C++ programmers

Section 4. Java versions -- how binary trees work in Java, with solution code

Stanford CS Education Library -- #110

This is article #110 in the Stanford CS Education Library. This and other free CS materials are available at the library (http://cslibrary.stanford.edu/). That people seeking education should have the opportunity to find it. This article may be used, reproduced, excerpted, or sold so long as this paragraph is clearly reproduced. Copyright 2000-2001, Nick Parlante, nick.parlante@cs.stanford.edu.

Related CSLibrary Articles

Linked List Problems (http://cslibrary.stanford.edu/105/) -- a large collection of linked list problems using various pointer techniques (while this binary tree article concentrates on recursion)

Pointer and Memory (http://cslibrary.stanford.edu/102/) -- basic concepts of pointers and memory The Great Tree-List Problem (http://cslibrary.stanford.edu/109/) -- a great pointer recursion problem that uses both trees and lists

Section 1 -- Introduction To Binary Trees

A binary tree is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. The "root" pointer points to the topmost node in the tree. The left and right pointers recursively point to smaller "subtrees" on either side. A null pointer represents a binary tree with no elements -- the empty tree. The formal recursive definition is: a binary tree is either empty (represented by a null pointer), or is made of a single node, where the left and right pointers (recursive definition ahead) each point to a binary tree.

http://cslibrary.stanford.edu/110/ BinaryTrees.html

Binary Trees Page: 2

A "binary search tree" (BST) or "ordered binary tree" is a type of binary tree where the nodes are arranged in order: for each node, all elements in its left subtree are less-or-equal to the node (<=), and all the elements in its right subtree are greater than the node (>). The tree shown above is a binary search tree -- the "root" node is a 5, and its left subtree nodes (1, 3, 4) are <= 5, and its right subtree nodes (6, 9) are > 5. Recursively, each of the subtrees must also obey the binary search tree constraint: in the (1, 3, 4) subtree, the 3 is the root, the 1 <= 3 and 4 > 3. Watch out for the exact wording in the problems -- a "binary search tree" is different from a "binary tree".

The nodes at the bottom edge of the tree have empty subtrees and are called "leaf" nodes (1, 4, 6) while the others are "internal" nodes (3, 5, 9).

Binary Search Tree Niche

Basically, binary search trees are fast at insert and lookup. The next section presents the code for these two algorithms. On average, a binary search tree algorithm can locate a node in an N node tree in order lg(N) time (log base 2). Therefore, binary search trees are good for "dictionary" problems where the code inserts and looks up information indexed by some key. The lg(N) behavior is the average case -- it's possible for a particular tree to be much slower depending on its shape.

Strategy

Some of the problems in this article use plain binary trees, and some use binary search trees. In any case, the problems concentrate on the combination of pointers and recursion. (See the articles linked above for pointer articles that do not emphasize recursion.)

For each problem, there are two things to understand...

The node/pointer structure that makes up the tree and the code that manipulates it The algorithm, typically recursive, that iterates over the tree

When thinking about a binary tree problem, it's often a good idea to draw a few little trees to think about the various cases.

http://cslibrary.stanford.edu/110/ BinaryTrees.html



Binary Trees

Page: 3

Typical Binary Tree Code in C/C++

As an introduction, we'll look at the code for the two most basic binary search tree operations -- lookup() and insert(). The code here works for C or C++. Java programers can read the discussion here, and then look at the Java versions in Section 4.

In C or C++, the binary tree is built with a node type like this...

struct node {

int data;

struct node* left;

struct node* right;

}

Lookup()

Given a binary search tree and a "target" value, search the tree to see if it contains the target. The basic pattern of the lookup() code occurs in many recursive tree algorithms: deal with the base case where the tree is empty, deal with the current node, and then use recursion to deal with the subtrees. If the tree is a binary search tree, there is often some sort of less-than test on the node to decide if the recursion should go left or right.

/*

Given a binary tree, return true if a node

with the target data is found in the tree. Recurs

down the tree, chooses the left or right

branch by comparing the target to each node.

*/

static int lookup(struct node* node, int target) {

// 1. Base case == empty tree

// in that case, the target is not found so return false

if (node == NULL) {

return(false);

}

else {

// 2. see if found here

if (target == node->data) return(true);

else {

// 3. otherwise recur down the correct subtree

if (target < node->data) return(lookup(node->left, target));

else return(lookup(node->right, target));

} }

}

The lookup() algorithm could be written as a while-loop that iterates down the tree. Our version uses recursion to help prepare you for the problems below that require recursion.

Pointer Changing Code

There is a common problem with pointer intensive code: what if a function needs to change one of the pointer parameters passed to it? For example, the insert() function below may want to change the

...