You need to build a binary tree with the methods inorder_tree_walk, tree_search, tree_minimum, tree_successor, tree_insert and tree_delete. The compiler swears at lines with tree-> root. In the code, the insert and delete functions do not work, the rest, I think, is correct. The code was made exclusively for Korman. On the photo list of errors. Tell me how to fix the program?

#include "stdafx.h" #include <stdlib.h> struct tree { int key; struct tree *parent, *left, *right; struct tree *root; }; void inorder_tree_walk(struct tree *x) { if (x != NULL) { inorder_tree_walk(x->left); printf("%d ", x->key); inorder_tree_walk(x->right); } } struct tree *tree_search(struct tree *x, int key) { if (x == NULL || key == x->key) return x; if (key < (x->key)) { return tree_search(x->left, key); } else{ return tree_search(x->right, key); } } struct tree *tree_minimum(struct tree *x) { while (x->left != NULL) x = x->left; return x; } struct tree *tree_successor(struct tree *x) { struct tree *y; if (x->right != NULL) { return tree_minimum(x->right); } y = x->parent; while (y != NULL && x == y->right) { x = y; y = y->parent; return y; } } struct tree *tree_insert(struct tree *x, int key) { struct tree *z = NULL; struct tree *y = NULL; x = tree->root; while (x != NULL) { y = x; if (z->key < x->key) x = x->left; else x = x->right; } z->parent = y; if (y == NULL) { tree->root = z; } else if (z->key < y->key) y->left = z; else y->right = z; } struct tree *tree_delete(struct tree *tree, int key) { struct tree *z; struct tree *x; struct tree *y; if (z->left == NULL || z->right == NULL) { y = z; } else y = tree_successor(z); if (y->left != NULL) x = y->left; else x = y->right; if (x != NULL) x->parent = y->parent; if (y->parent = NULL) tree->root = x; else if (y = y->parent->left) y->parent->left = x; else y->parent->right = x; if (y != z) z->key = y->key; return y; } int main() { tree *root = NULL; root = tree_insert(root, 7); root = tree_insert(root, 13); root = tree_insert(root, 8); root = tree_insert(root, 23); root = tree_insert(root, -7); root = tree_insert(root, 13); root = tree_insert(root, 31); root = tree_insert(root, 5); inorder_tree_walk(root); printf("\n\n"); tree *tmp; tmp = tree_minimum(root); printf("minimum = %d\n", tmp->key); root = tree_delete(root, 8); root = tree_delete(root, -7); root = tree_delete(root, 31); inorder_tree_walk(root); printf("\n\n"); tmp = tree_search(root, 13); if (tmp == NULL) { printf("no element\n"); } else { printf("found element\n"); } getchar(); }

enter image description here

  • x = tree->root; A tree is a type and cannot be used as a variable. But what is there - this is what you should know as a developer of this code. - KoVadim
  • changed tree to drzewo, pops up the exception "drzewo was nullptr" struct tree * tree_insert (struct tree * drzewo, int key) {struct tree * x = NULL; struct tree * z = NULL; struct tree * y = NULL; x = drzewo-> root; while (x! = NULL) {y = x; if (z-> key <x-> key) x = x-> left; else x = x-> right; } z-> parent = y; if (y == NULL) {drzewo-> root = z; } else if (z-> key <y-> key) y-> left = z; else y-> right = z; return 0; } - Yana Glance
  • @Yana Glance Select the specific language in which the program should be written. C and C ++ are two different languages. - Vlad from Moscow

1 answer 1

tree is the name of a structure tag, not the name of an object of this type. Therefore, sentences like this

 x = tree->root;

incorrect.

Obviously, in connection with this and other errors, the tree_insert and tree_delete are incorrect.

First, I would remove the root data member from the definition of the structure. I did not somtrel all the methods of your implementation of the tree, but in my opinion there is no point in every node of the tree to hold a pointer to the root node.

 struct tree { int key; struct tree *parent, *left, *right; struct tree *root; ^^^^^^^^^^^^^^^^^ };

The structure might look like this.

 struct tree { int key; struct tree *parent, *left, *right; };

Given this structure definition, the tree_insert function may look like one of the following, as will be shown below.

Note that, first, the function must return a pointer to the root node of the tree, and your function returns nothing.

 struct tree *tree_insert(struct tree *x, int key) { struct tree *z = NULL; struct tree *y = NULL; x = tree->root; while (x != NULL) { y = x; if (z->key < x->key) x = x->left; else x = x->right; } z->parent = y; if (y == NULL) { tree->root = z; } else if (z->key < y->key) y->left = z; else y->right = z; }

Moreover, the node passed to it may be NULL , but in the function this circumstance is completely ignored.

Here are a couple of function definitions.

Either the function can be defined as follows.

 struct tree * tree_insert(struct tree *root, int key) { struct tree *parent = NULL; while (root != NULL) { parent = root; if (key < root->key) { root = root->left; } else { root = root->right; } } struct tree *node = (struct tree *)malloc(sizeof(struct tree)); node->key = key; node->parent = parent; node->left = NULL; node->right = NULL; if (parent != NULL) { if (key < parent->key) { parent->left = node; } else { parent->right = node; } } else { root = node; } return root; }

Or more compact.

 struct tree * tree_insert(struct tree *root, int key) { struct tree *parent = NULL; struct tree **current = &root; while (*current != NULL) { parent = *current; if (key < ( *current )->key) { current = &( *current )->left; } else { current = &(*current)->right; } } *current = (struct tree *)malloc(sizeof(struct tree)); (*current)->key = key; (*current)->parent = parent; (*current)->left = NULL; (*current)->right = NULL; return root; }

I would prefer the second implementation.

Below is a demonstration program.

 #include <stdlib.h> #include <stdio.h> struct tree * tree_insert(struct tree *root, int key) { struct tree *parent = NULL; struct tree **current = &root; while (*current != NULL) { parent = *current; if (key < ( *current )->key) { current = &( *current )->left; } else { current = &(*current)->right; } } *current = (struct tree *)malloc(sizeof(struct tree)); (*current)->key = key; (*current)->parent = parent; (*current)->left = NULL; (*current)->right = NULL; return root; } void inorder_tree_walk( const struct tree *root ) { if (root != NULL) { inorder_tree_walk(root->left); printf("%d ", root->key); inorder_tree_walk(root->right); } } int main( void ) { tree *root = NULL; root = tree_insert(root, 7); root = tree_insert(root, 13); root = tree_insert(root, 8); root = tree_insert(root, 23); root = tree_insert(root, -7); root = tree_insert(root, 13); root = tree_insert(root, 31); root = tree_insert(root, 5); inorder_tree_walk(root); printf("\n\n"); }

Her console output will be as follows.

 -7 5 7 8 13 13 23 31

This output corresponds to the following tree.

  7 /\ / \ / \ -7 13 \ / \ \ / \ 6 8 23 / \ / \ 13 31

With that said, you will also need to fix other functions, such as tree_delete and tree_successor . At least you need to check the passed parameters for NULL equality.