Язык С++ и программирование на нем. Рейзлин В.И. - 156 стр.

UptoLike

Составители:

Рубрика:

158

мент правого поддерева. В первом случае для достижения этого звена

необходимо перейти в следующую вершину по левой ветви, а затем пе-

реходить в очередные вершины только по правой ветви до тех пор, пока

очередной указатель не будет равен NULL. Во втором случае необхо-

димо перейти в следующую вершину по правой ветви, а затем перехо-

дить в очередные вершины только по левой ветви до тех пор, пока оче-

редной указатель не станет равен NULL. Такие подходящие звенья мо-

гут иметь не более одной ветви. Ниже (рис. 12) схематично изображено

исключение из дерева вершины с ключом 50:

100 100

20 120 20 120

15 50 130 15 35 130

30 55 30 55

28 35 60 28 33 60

Рис. 12. Исключение из дерева вершины с ключом 50

Приведём программу, реализующую дерево поиска со всеми опе-

рациями с помощью класса tree и несколько изменённой функции

insert.

#include <fstream.h>

struct node {

int key, code;

node *left, *right;

node (int k, int c, node *l, node *r){ key = k; code = c; left = l; right =

r; }

};

int f(int);

class tree {

node *root;

void print (node *r); // Печать с указателя r.

public:

int insert (int);

void del (int);