Lecture
Это окончание невероятной информации про очереди .
...
+---+---+ +---+---+ ↑ ↑ ↑ '----------------leaves------------------'
Special terminology is used when discussing trees. Programmers are not experts in philology, and so the terminology used in graph theory (after all, trees are a special case of graphs!) is a classic example of the misuse of words. The first element of a tree is called the root. Each data element is called a node (node), and any fragment of the tree is called a subtree (subtree). A node that has no subtrees attached to it is called a terminal node (terminal node) or a leaf (leaf). The height (height) of a tree equals the maximum number of levels from the root to a leaf. When working with trees, it is tempting to assume that they exist in memory in the same form as on paper. But remember that a tree is merely a way of logically organizing data in memory, and memory itself is linear.
In a certain sense, a binary tree is a special kind of linked list. Elements can be inserted, deleted, and retrieved in any order. Moreover, the retrieval operation is not destructive. Although trees are easy to picture, they are associated with a number of difficult problems in programming theory. This section only touches on trees superficially.
Most functions that work with trees are recursive, since a tree is by its very nature a recursive data structure. In other words, each subtree is, in turn, itself a tree. Therefore, the functions developed here will be recursive. Non-recursive versions of these functions do exist, but their code is much harder to understand.
The way a tree is ordered depends on how it will subsequently be accessed. The process of visiting each node of a tree in turn is called tree traversal (tree traversal). Consider the following tree:
d
↙ ↘
b f
↙ ↘ ↙ ↘
a c e g
There are three orders of tree traversal: symmetric-order traversal, or inorder traversal (inorder), preorder traversal, forward traversal, ordered traversal, top-down traversal, or breadth-first traversal (preorder) and reverse-order traversal, depth-first traversal, reverse traversal, bottom-up traversal (postorder). In symmetric (inorder) traversal, the left subtree is processed first, then the root, and then the right subtree. In preorder traversal, the root is processed first, then the left subtree, and then the right subtree. In postorder (bottom-up) traversal, the left subtree is processed first, then the right subtree, and finally the root. The access sequence for each traversal method is shown below:
Inorder traversal a b c d e f g Preorder traversal d b a c f e g Postorder traversal a c b e g f d
Although a tree does not have to be ordered, most problems make use of exactly such trees. Of course, the structure of an ordered tree depends on the method used to traverse it. For the rest of this chapter, symmetric (inorder) traversal is assumed. Therefore, an ordered binary tree will be one in which the left subtree contains nodes less than or equal to the root, and the right subtree contains nodes greater than the root.
The function stree() shown below creates an ordered binary tree:
struct tree {
char info;
struct tree *left;
struct tree *right;
};
struct tree *stree(
struct tree *root,
struct tree *r,
char info)
{
if(!r) {
r = (struct tree *) malloc(sizeof(struct tree));
if(!r) {
printf("Out of memory\n");
exit(0);
}
r->left = NULL;
r->right = NULL;
r->info = info;
if(!root) return r; /* first entry */
if(info < root->info) root->left = r;
else root->right = r;
return r;
}
if(info < r->info)
stree(r,r->left,info);
else
stree(r,r->right,info);
return root;
}
The algorithm shown above simply follows the links of the tree, moving to the left or right branch of the current node based on the contents of the info field, until it reaches the place where the new element should be inserted. To use this function, you need a global pointer variable to the root of the tree. This pointer must initially be null (NULL). On the first call, the function stree() returns a pointer to the root of the tree, which must be assigned to the global variable. On subsequent calls, the function continues to return a pointer to the root. Suppose the global variable holding the root of the tree is called rt. Then the function stree() is called as follows:
/* call the street() function */ rt = street(rt, rt, info);
The function stree() uses a recursive algorithm, as do most tree-processing procedures. An equivalent function based on iterative methods would be several times longer. The function stree() must be called with the following parameters (from left to right): a pointer to the root of the entire tree, a pointer to the root of the next subtree in which the search is performed, and the data to be stored. On the first call, both of the first two parameters point to the root of the entire tree. For simplicity, the nodes of the tree store single characters. However, any other data type can be used instead.
To traverse the tree built by the function stree() in symmetric order and print the info field at each node, you can use the function inorder() shown below:
void inorder(struct tree *root)
{
if(!root) return;
inorder(root->left);
if(root->info) printf("%c ", root->info);
inorder(root->right);
}
This recursive function terminates when it reaches a terminal node (a null pointer).
The following listing shows the functions that perform breadth-first and depth-first traversal of a tree.
void preorder(struct tree *root)
{
if(!root) return;
if(root->info) printf("%c ", root->info);
preorder(root->left);
preorder(root->right);
}
void postorder(struct tree *root)
{
if(!root) return;
postorder(root->left);
postorder(root->right);
if(root->info) printf("%c ", root->info);
}
Now let's look at a short but interesting program that builds an ordered binary tree and then, traversing it in symmetric order, displays it sideways on the screen. Displaying the tree requires only a slight modification of the inorder() function. Because the tree is printed sideways on the screen, the right subtree must be printed before the left one for correct display. (Technically this is the opposite of symmetric traversal.) The new function is called printtree(), and its code is shown below:
void print_tree(struct tree *r, int l)
{
int i;
if(r == NULL) return;
print_tree(r->right, l+1);
for(i=0; iinfo);
print_tree(r->left, l+1);
}
Next is the full listing of the tree-printing program. Try entering different trees to see how they are built.
/* This program displays a binary tree on the screen. */
#include
#include
struct tree {
char info;
struct tree *left;
struct tree *right;
};
struct tree *root; /* the root node of the tree */
struct tree *stree(struct tree *root,
struct tree *r, char info);
void print_tree(struct tree *root, int l);
int main(void)
{
char s[80];
root = NULL; /* initialize the tree's root */
do {
printf("Enter a letter: ");
gets(s);
root = stree(root, root, *s);
} while(*s);
print_tree(root, 0);
return 0;
}
struct tree *stree(
struct tree *root,
struct tree *r,
char info)
{
if(!r) {
r = (struct tree *) malloc(sizeof(struct tree));
if(!r) {
printf("Out of memory\n");
exit(0);
}
r->left = NULL;
r->right = NULL;
r->info = info;
if(!root) return r; /* first entry */
if(info < root->info) root->left = r;
else root->right = r;
return r;
}
if(info < r->info)
stree(r, r->left, info);
else
stree(r, r->right, info);
return root;
}
void print_tree(struct tree *r, int l)
{
int i;
if(!r) return;
print_tree(r->right, l+1);
for(i=0; iinfo);
print_tree(r->left, l+1);
}
Essentially, this program sorts the information you enter. The sorting method is a variation of insertion sort, which was discussed in the previous chapter. In the average case, its performance can be quite good.
If you have run the tree-printing program, you have probably noticed that some trees are balanced, i.e., every subtree has roughly the same height as the others, while some trees are very far from that state. For example, the tree a⇒b⇒c⇒d looks as follows:
a
↘
b
↘
c
↘
d
This tree has no left subtrees. Such a tree is called degenerate, because it has effectively degenerated into a linear list. In general, if the data used to build a tree is random, the resulting tree ends up close to balanced. If, however, the data is pre-sorted, a degenerate tree is created. (For this reason, the tree is sometimes rebalanced after every insertion, but this process is fairly complex and is beyond the scope of this chapter.)
Search functions are easy to implement for binary trees. The function shown below returns a pointer to the tree node whose information matches the search key, or null (NULL) if no such node exists.
struct tree *search_tree(struct tree *root, char key)
{
if(!root) return root; /* empty tree */
while(root->info != key) {
if(keyinfo) root = root->left;
else root = root->right;
if(root == NULL) break;
}
return root;
}
Unfortunately, deleting a tree node is not as simple as finding one. The node being deleted can be the root, a left node, or a right node. In addition, the node may have subtrees attached to it (the number of attached subtrees can be 0, 1, or 2). The process of resetting the pointers is handled by the recursive algorithm shown below:
struct tree *dtree(struct tree *root, char key)
{
struct tree *p,*p2;
if(!root) return root; /* node not found */
if(root->info == key) { /* deleting the root */
/* this means an empty tree */
if(root->left == root->right){
free(root);
return NULL;
}
/* or if one of the subtrees is empty */
else if(root->left == NULL) {
p = root->right;
free(root);
return p;
}
else if(root->right == NULL) {
p = root->left;
free(root);
return p;
}
/* or both subtrees exist */
else {
p2 = root->right;
p = root->right;
while(p->left) p = p->left;
p->left = root->left;
free(root);
return p2;
}
}
if(root->info < key) root->right = dtree(root->right, key);
else root->left = dtree(root->left, key);
return root;
}
You must also make sure that the pointer to the root of the tree, declared outside this function, is updated correctly, since the node being deleted may be the root. The best way to do this is to assign the root pointer the value returned by the function dtree():
root = dtree(root, key);
Binary trees are an exceptionally powerful, flexible, and efficient tool. Because searching a balanced tree requires at most log2n comparisons in the worst case, it is far better than a linked list, in which only sequential search is possible.
Часть 1 Queues, Stacks, Linked Lists, and Trees
Часть 2 - Queues, Stacks, Linked Lists, and Trees
Comments