BST Baum Doppelzeiger bauen
Ich bin nicht sicher, wie ich einen Zeiger auf einen Zeiger setzen soll, um einen Baum zu erstellen. Wie sollte ich, wenn ich einmal zu einem Blatt gereist bin und insert aufgerufen habe, ein weiteres Element einfügen, das insert mit dem Wurzelknoten oder der Adresse des Wurzelzeigers aufruft? Ich denke, das Problem mit dieser Funktion ist der Name root, wo das der doppelte Zeiger sein sollte, oder?
#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;
}
Dies ist die .h-Datei
/// 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;
und zuletzt die Traverse-Funktion, soweit sie den ersten Test nicht bestanden hat.
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 );
}
}
Warum erhält der insertNode die Fehler (mehrfach) und ich weiß nicht, welcher der Zeiger und welcher die Struktur ist. Jungs, jeder Tipp wird hilfreich sein, bitte?
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 für Edit 2: Ich habe eine Header-Datei mit einem build_Tree (** root, elems [], sizeofElem []), was bedeutet, dass ich eine Hilfsfunktion einfügen muss. Ja, es wäre einfacher, durch Eingabe ab * hinzuzufügen.
Edit 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
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;
}