BST построить дерево двойных указателей
Я не уверен, как установить указатель на указатель для построения дерева. Как после того, как я перешел к листу и вызову insert, как мне вставить другой элемент, вызывающий insert, с корневым узлом или адресом корневого указателя? Я думаю, что проблема с этой функцией является имя корня, где это должно быть двойной указатель правильно?
#include "bst.h"
#include <stdio.h>
#include <stdlib.h>
//arbitrary list of temp nodes
TreeNode *new_node, *root, *tmp, *parent;
int elemArray[100], i1, i2, i0;
int main( int argc, char *argv[] ) {
//Throw error is *Argv[] is not an integer
//assuming it was an integer
int cnt = atoi( argv[1] );
printf( "number is %d\n", cnt );
//
printf("Enter %i integer values to place in tree:\n", cnt);
for ( i1 = 0; i1 < cnt; ++i1) {
scanf( "%d", &elemArray[i1] );
}
//first ouput "INput Values"
printf( " Input Values:\n " );
for ( i2 = 0; i2 < cnt; ++i2) {
printf( "%d\n", elemArray[i2] );
}
TreeNode** root = (TreeNode*)malloc(sizeof(TreeNode*));
buildTree(root, elemArray, cnt );
printf( "Preorder:\n ");
//traverse
//TreeNode* tempN = malloc(sizeof(TreeNode*));
//tempN->data= 5;
traverse( root, PREORDER);
//traverse a single node
printf( "Inorder:\n ");
printf( "Postorder:\n ");
//Build tree with each element
return 0;
}
Это файл.h
/// The definition of the tree structure
typedef struct TreeNode {
int data ; // the data stored in the node
struct TreeNode* left ; // node's left child
struct TreeNode* right ; // node's right child
} TreeNode;
/// The three supported traversals
typedef enum {
PREORDER, // parent -> left -> right
INORDER, // left -> parent -> right
POSTORDER // left -> right -> parent
} TraversalType;
и, наконец, функция перемещения, поскольку она не прошла первый тест.
void traverse( const TreeNode* root, const TraversalType type ) {
if ( type == PREORDER) {
if (root != NULL)
{
printf("%d", root->data);
traverse( root->left, PREORDER);
traverse( root-> right, PREORDER);
}
}
}
void build_tree(TreeNode** root, const int elements[], const int count) {
TreeNode* node = malloc(sizeof(TreeNode*));
node->left = node ->right = NULL;
*root = node;
for ( int i0 = 0; i0 < count; ++i0 ){
TreeNode* node = malloc(sizeof(TreeNode*));
*root = node;
node->data = elements[cnt];
insertNode( &(*root), &node );
}
}
Почему insertNode получает ошибки (несколько), и я не знаю, какой указатель, а какая структура. ПАРНИ, ЛЮБОЙ НАДВЕТ, ПОЖАЛУЙСТА, ПОЖАЛУЙСТА?
bst.c:94:20: error: request for member 'left' in something not a structure or union
insert(root->left, new_node);
void insertNode(TreeNode** root, TreeNode* new_node) {
if (new_node-> data < &root-> data) {
if (&root-> left == NULL)
&root-> left == new_node;
else
insert(root->left, new_node);
}
if (new_node->data > &root->data) {
if(&root-> right ==NULL)
&root->right = new_node;
else
insert(&root->right, new_node);
}
}
SO for Edit 2: у меня есть файл заголовка с build_Tree(**root, elems[], sizeofElem[]), что означает, что мне нужна вставка вспомогательной функции. Да, было бы проще добавить ввод, начиная *.
Редактировать 1
#include "bst.h"
#include <stdio.h>
#include <stdlib.h>
//arbitrary list of temp nodes
TreeNode *new_node, *root, *tmp, *parent, *current;
int elemArray[5], i1, i2, i0;
/*
Insert a new node into the tree by referencing the root and using recursion
*/
TreeNode* getN(int dataElem) {
TreeNode *newNode = malloc(sizeof(*newNode));
if (newNode != NULL)
{
newNode->data = dataElem;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
/** This func should just be the root of the tree in the parameter,
but I like the idea of a pointer becuase it helps to create a tempory
pointer rather than newNode
**/
TreeNode* addNodeToTree(TreeNode *root, int data) {
TreeNode *current = *root; //define the current pointer to the root always
TreeNode *parent = *root
TreeNode *newNode = getN(data);
if (*root == NULL)
{
printf("First Node");
*root = newNode;
}
else
{
while(current != NULL)
{
parent = current;
if (current->data > data)
current = current->left;
else if (current->data < data)
current = current->right;
}
if (parent->data > data)
parent->left = newNode;
else if (parent->data < data)
parent->right = newNode;
}
}
void build_Tree(TreeNode** root, const int elements[], const int count) {
*root = malloc(sizeof(TreeNode));
for ( i0 = 0; i0 < count; ++i0 ){
printf("%d\n", elements[count]);
addNodeToTree(&root, elements[count]);
}
}
int main( int argc, char *argv[] ) {
//Throw error is *Argv[] is not an integer
//assuming it was an integer
int cnt = atoi( argv[1] );
printf( "number is %d\n", cnt );
//
printf("Enter %i integer values to place in tree:\n", cnt);
for ( i1 = 0; i1 < cnt; ++i1) {
scanf( "%d", &elemArray[i1] );
}
//first ouput "INput Values"
printf( " Input Values:\n " );
for ( i2 = 0; i2 < cnt; ++i2) {
printf( "%d\n", elemArray[i2] );
printf("building tree0\n");
}
printf("building tree\n");
TreeNode** root = (TreeNode**)malloc(sizeof(TreeNode*));
TreeNode *root = NULL;
build_Tree(root, elemArray, cnt );
printf( "Preorder:\n ");
//traverse
//TreeNode* tempN = malloc(sizeof(TreeNode*));
//tempN->data= 5;
traverse( *root, PREORDER); //pass the pointer of root to traverse the tree
//traverse a single node
printf( "Inorder:\n ");
printf( "Postorder:\n ");
//Build tree with each element
return 0;
}
void traverse( const TreeNode* root, const TraversalType type ) {
if ( type == PREORDER) {
if (root != NULL)
{
printf("%d", root->data);
traverse( root->left, PREORDER);
traverse( root-> right, PREORDER);
}
}
}
/**
void insertNode(TreeNode** root, TreeNode* new_node) {
if (new_node-> data < *root-> data) {
if (*root-> left == NULL)
*root-> left == new_node;
else
insert(*root->left, new_node);
}
if (new_node->data > *root->data) {
if(*root-> right ==NULL)
*root->right = new_node;
else
insert(*root->right, new_node);
}
}
**/
//question1: what is the
Редактировать 2 для основного и build_tree
void build_Tree(TreeNode** root, const int elements[], const int count) {
//*root = malloc(sizeof(TreeNode));
for ( i0 = 0; i0 < count; i0++ ){
//create the node
//
TreeNode *current = *root; //define the current pointer to the root always
TreeNode *parent = *root;
//dont create node
int data = elements[i0];
TreeNode *newNode = getN(data);
if (*root == NULL)
{
printf("First Node %d\n", elements[i0]);
*root = newNode;
}
else
{
printf("Next Node %d\n", elements[i0]);
while(current != NULL)
{
parent = current;
if (current->data > data)
current = current->left;
else if (current->data < data)
current = current->right;
}
if (parent->data > data)
parent->left = newNode;
else if (parent->data < data)
parent->right = newNode;
}
//return root;
}
}
TreeNode* getN(int dataElem) {
TreeNode *newNode = malloc(sizeof(*newNode));
if (newNode != NULL)
{
newNode->data = dataElem;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
int main( int argc, char *argv[] ) {
//Throw error is *Argv[] is not an integer
//assuming it was an integer
int cnt = atoi( argv[1] );
printf( "number is %d\n", cnt );
//
printf("Enter %i integer values to place in tree:\n", cnt);
for ( i1 = 0; i1 < cnt; ++i1) {
scanf( "%d", &elemArray[i1] );
}
//first ouput "INput Values"
printf( " Input Values:\n " );
for ( i2 = 0; i2 < cnt; ++i2) {
printf( "%d\n", elemArray[i2] );
printf("building tree0\n");
}
printf("building tree\n");
TreeNode* root; //= malloc(sizeof(TreeNode*));
root = NULL;
build_Tree(&root, elemArray, cnt );
printf( "Preorder:\n ");
//traverse
//TreeNode* tempN = malloc(sizeof(TreeNode*));
//tempN->data= 5;
//traverse( *root, PREORDER); //pass the pointer of root to traverse the tree
//traverse a single node
printf( "Inorder:\n ");
printf( "Postorder:\n ");
//Build tree with each element
return 0;
}
1 ответ
Решение
Скажем, вы создали функцию addNodeToTree(TreeNode *root, int data), пройти root узел и data к этому в качестве аргумента.
Теперь внутри этой функции просто создайте другую переменную, скажем TreeNode *current = root что поможет нам в основном пройти по дереву и поместить узел в соответствующую позицию, и TreeNode *newNode = NULL(это станет новым узлом, который должен быть вставлен).
Теперь, прежде чем двигаться вперед, чтобы фактически разместить узел, мы сначала проверим, если root не является нулевым, то есть дерево EMPTY, Для этого мы проверим:
if (root == NULL)
{
newNode = malloc(sizeof(*newNode)); // else we can make a function for this
// thingy too. Creating a function too,
// for you to look at.
root = newNode;
}
Если дерево не EMPTYт.е. он уже содержит узел, тогда мы пройдемся по дереву, чтобы найти место, куда поместить новый узел. Итак else часть, будет как:
else
{
parent = current = root;
// This loop will actually help us, find the `parent`,
// of the `newNode`(which is to be inserted)
while (current != NULL)
{
parent = current;
if (current->data > data)
current = current->left;
else if (current->data < data)
current = current->right;
}
// Now once, we have found, the node, under which the
// newNode will be placed, now we have to check, whether
// newNode will become a `left child/right child` of the
// parent.
newNode = getNewNode(data);
if (parent->data > data)
parent->left = newNode;
else if (parent->data < data)
parent->right = newNode;
return root;
}
TreeNode * getNewNode(int data)
{
TreeNode *newNode = malloc(sizeof(*newNode));
if (newNode != NULL)
{
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
Теперь newNode был вставлен, и вы можете просто пройти в любом порядке, чтобы увидеть дерево.
РЕДАКТИРОВАТЬ 1:
Вот один рабочий пример, просто посмотрите, имеет ли это смысл. В противном случае, пожалуйста, задайте любой вопрос, который может возникнуть.
#include <stdio.h>
#include <stdlib.h>
typedef struct TREENODE
{
int data;
struct TREENODE *left;
struct TREENODE *right;
}TreeNode;
void display(TreeNode *node)
{
printf("*********************************\n");
printf("Address of Node: %p\n", node);
printf("Data: %d\n", node->data);
printf("Left Child: %p\n", node->left);
printf("Right Child: %p\n", node->right);
printf("*********************************\n");
}
TreeNode * getNewNode(int data)
{
TreeNode *newNode = malloc(sizeof(*newNode));
if (newNode != NULL)
{
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
}
return newNode;
}
int getIntData(char *message)
{
int value = 0;
char buffer[BUFSIZ] = {'\0'};
fputs(message, stdout);
fgets(buffer, sizeof(buffer), stdin);
sscanf(buffer, "%d", &value);
return value;
}
TreeNode * addNodeToTree(TreeNode *root, int data)
{
TreeNode *current = root, *parent = root;
TreeNode *newNode = getNewNode(data);
if (root == NULL)
{
root = newNode;
}
else
{
while(current != NULL)
{
parent = current;
if (current->data > data)
current = current->left;
else if (current->data < data)
current = current->right;
}
if (parent->data > data)
parent->left = newNode;
else if (parent->data < data)
parent->right = newNode;
}
return root;
}
void inOrderTraversal(TreeNode *root)
{
if (root != NULL)
{
inOrderTraversal(root->left);
display(root);
inOrderTraversal(root->right);
}
}
int main(void)
{
TreeNode *root = NULL;
int data = 0;
data = getIntData("Enter Data: ");
root = addNodeToTree(root, data);
data = getIntData("Enter Data: ");
root = addNodeToTree(root, data);
data = getIntData("Enter Data: ");
root = addNodeToTree(root, data);
inOrderTraversal(root);
return EXIT_SUCCESS;
}
РЕДАКТИРОВАТЬ 2:
Делать addNodeToTree(...)Чтобы реализовать указатель на указатель, нужно просто изменить функцию следующим образом:
void addNodeToTree(TreeNode **root, int data)
{
TreeNode *current = *root;
TreeNode *parent = *root;
TreeNode *newNode = getNewNode(data);
if (*root == NULL)
{
*root = newNode;
}
else
{
// same as before, just don't return anythingy, from the function.
// As the function uses pointer to a pointer, hence whatever changes
// are done, here will be reciprocated in the main function automatically
}
// no need to return anythingy
}
И звонок от main теперь будет выглядеть так:
int main(void)
{
TreeNode *root = NULL;
int data = 0;
data = getIntData("Enter Data: ");
addNodeToTree(&root, data);
// Just see the call to addNodeToTree(...), the rest is same, as before
}
РЕДАКТИРОВАТЬ 3:
Чтобы взять элементы из массива, а не добавлять их непосредственно в дерево, просто измените main метод к этой форме:
int main(void)
{
TreeNode *root = NULL;
int element[5] = {19, 11, 5, 28, 25};
int size = sizeof(element) / sizeof(element[0]);
int counter = 0;
for (counter = 0; counter < size; ++counter)
{
addNodeToTree(&root, element[counter]);
}
inOrderTraversal(root);
return EXIT_SUCCESS;
}