To just search the tree, without adding a missing key, use the _tfind function.
Returns:
A pointer to the node on success, otherwise a null pointer.
#include <stdio.h>
#include <stdlib.h>
#include <search.h>
typedef unsigned long DWORD;
static void *root = NULL;
int cmp(const void *elem1, const void *elem2)
{
printf("root %p\n", root);
printf("cmp1 %p\n", elem1);
printf("cmp2 %p\n", elem2);
DWORD v1 = *(DWORD*)elem1; // here elem is a DWORD*
DWORD v2 = *(DWORD*)elem2;
printf("v1 %d, v2 %d\n", v1, v2);
return v1 - v2;
}
void show(const void *elem, _VISIT visit, int level)
{
DWORD* v = *(DWORD**)elem; // here elem is a DWORD**
printf("v %d\n", *v);
printf("visit %d\n", visit);
printf("level %d\n", level);
}
int main(int argc, char *argv[])
{
DWORD* key;
void* x;
key = malloc(sizeof(DWORD));
printf("key1 %p\n", key);
*key = 20;
x = _tsearch(key, (void**)&root, cmp);
printf("elem1 %p\n", x);
key = malloc(sizeof(DWORD));
printf("key2 %p\n", key);
*key = 200;
x = _tsearch(key, (void**)&root, cmp);
printf("elem2 %p\n", x);
_twalk(root, show);
return 0;
}
The parameters elem, elem1 and elem2 in the cmp and show functions are all void* but they do not point to the same type of data. In the example they sometimes point to DWORD* or to DWORD**. That's strange!#include <search.h>
#define nKeys ((int)(sizeof(keys)/sizeof(int)))
int __cdecl MyCmp(const void *elem1, const void *elem2)
{
return *((int *)(elem1)) - *((int *)(elem2));
}
static int min = 10000;
static int max = -10000;
char *sVisit[] = {"preorder ",
"postorder",
"endorder ",
"leaf "};
void __cdecl FindMinMax(const void *elem, _VISIT visit, int level)
{
printf("\n[el=% .4d, visit=%s, lev=%d]", **((int **)elem), sVisit[visit], level);
if ((visit == _leaf ||visit == _preorder) && elem)
{
if (**((int **)elem)>= max)
max = **((int **)elem);
if (**((int **)elem)<= min)
min = **((int **)elem);
}
}
void PrintData(int *keys, void **proot, int n)
{
printf("Checking data... ");
for (int i=0; i<n; i++)
{
void *node = _tfind((void *)&keys[i], proot, MyCmp);
if (node)
printf("%d ", **((int **)node));
}
printf("\n");
}
int main(int argc, char *argv[])
{
int keys[] = { 5, -1, 3, -14, 8, 10, 9, 6 };
void *root = NULL;
printf("Inserting data... ");
for (int i=0; i<nKeys; i++)
{
if (_tsearch((void *)&keys[i], &root, MyCmp))
printf ("%d ", keys[i]);
else
printf("\nError!\n");
}
printf("\n");
PrintData(keys, &root, nKeys);
printf("Deleting data... ");
printf ("%d ", **((int **)_tdelete ((void *)&keys[0], &root, MyCmp)));
printf ("%d ", **((int **)_tdelete ((void *)&keys[1], &root, MyCmp)));
printf("\n");
PrintData(keys, &root, nKeys);
printf("Walking data... ");
_twalk(root, FindMinMax);
printf("\n");
printf("Minimum element is %d\n", min);
printf("Maximum element is %d\n", max);
}
EDIT: Improved version
Inserting data... 5 -1 3 -14 8 10 9 6
Checking data... 5 -1 3 -14 8 10 9 6
Deleting data... 8 3
You have deleted the first two keys. Why is 8 and 3 returned?Checking data... 3 -14 8 10 9 6
Walking data...
[el= 0003, visit=preorder , lev=0]
[el=-0014, visit=leaf , lev=1]
[el= 0003, visit=postorder, lev=0]
[el= 0008, visit=preorder , lev=1]
[el= 0006, visit=leaf , lev=2]
[el= 0008, visit=postorder, lev=1]
[el= 0010, visit=preorder , lev=2]
[el= 0009, visit=leaf , lev=3]
[el= 0010, visit=postorder, lev=2]
[el= 0010, visit=endorder , lev=2]
[el= 0008, visit=endorder , lev=1]
[el= 0003, visit=endorder , lev=0]
Minimum element is -14
Maximum element is 10
Why is 3 at level 0 and not 2?I have not deleted 8 and 3, but I deleted 5 and -1 >:(.Code: [Select]Inserting data... 5 -1 3 -14 8 10 9 6
You have deleted the first two keys. Why is 8 and 3 returned?
Checking data... 5 -1 3 -14 8 10 9 6
Deleting data... 8 3
That's absolutely correct. To avoid any problem I rewrote the example:Code: [Select]Checking data... 3 -14 8 10 9 6
Why is 3 at level 0 and not 2?
Walking data...
[el= 0003, visit=preorder , lev=0]
[el=-0014, visit=leaf , lev=1]
[el= 0003, visit=postorder, lev=0]
[el= 0008, visit=preorder , lev=1]
[el= 0006, visit=leaf , lev=2]
[el= 0008, visit=postorder, lev=1]
[el= 0010, visit=preorder , lev=2]
[el= 0009, visit=leaf , lev=3]
[el= 0010, visit=postorder, lev=2]
[el= 0010, visit=endorder , lev=2]
[el= 0008, visit=endorder , lev=1]
[el= 0003, visit=endorder , lev=0]
Minimum element is -14
Maximum element is 10
Why is -14 at level 1 and not 2?
Shouldn't 3 be a leaf?
#include<stdio.h>
#include<stdlib.h>
#include <search.h>
#define nKeys ((int)(sizeof(_keys)/sizeof(int)))
int __cdecl MyCmp(const void *elem1, const void *elem2)
{
//printf("comparing %d - %d\n", *((int *)(elem1)), *((int *)(elem2)));
return *((int *)(elem1)) - *((int *)(elem2));
}
static int min = 10000;
static int max = -10000;
char *sVisit[] = {"preorder ",
"postorder",
"endorder ",
"leaf "};
void __cdecl PrintWalk(const void *elem, _VISIT visit, int level)
{
printf("[el=% .4d, visit=%s, lev=%d]\n", **((int **)elem), sVisit[visit], level);
}
void __cdecl WalkInOrder(const void *elem, _VISIT visit, int level)
{
if (visit==_leaf || visit==_postorder)
printf("[el=% .4d, visit=%s, lev=%d]\n", **((int **)elem), sVisit[visit], level);
}
void __cdecl WalkPreOrder(const void *elem, _VISIT visit, int level)
{
if (visit==_leaf || visit==_preorder)
printf("[el=% .4d, visit=%s, lev=%d]\n", **((int **)elem), sVisit[visit], level);
}
void __cdecl WalkPostOrder(const void *elem, _VISIT visit, int level)
{
if (visit==_leaf || visit==_endorder)
printf("[el=% .4d, visit=%s, lev=%d]\n", **((int **)elem), sVisit[visit], level);
}
void __cdecl FindMinMax(const void *elem, _VISIT visit, int level)
{
PrintWalk(elem, visit, level);
if ((visit == _leaf ||visit == _preorder) && elem)
{
if (**((int **)elem)>= max)
max = **((int **)elem);
if (**((int **)elem)<= min)
min = **((int **)elem);
}
}
void PrintData(int *keys, void **proot, int n)
{
printf("Checking data... ");
for (int i=0; i<n; i++)
{
void *node = _tfind((void *)&keys[i], proot, MyCmp);
if (node)
printf("%d ", **((int **)node));
}
printf("\n");
}
int main(int argc, char *argv[])
{
int _keys[] = { 5, -1, 3, -14, 8, 10, 9, 6 };
int *keys[nKeys] = { NULL };
void *root = NULL;
for (int i=0; i<nKeys; i++)
keys[i] = &_keys[i];
printf("Inserting data... ");
for (int i=0; i<nKeys; i++)
{
if (_tsearch((void *)keys[i], &root, MyCmp))
printf ("%d ", *keys[i]);
else
printf("\nError!\n");
}
printf("\n");
printf ("\nUnordered data\n");
_twalk(root, PrintWalk);
printf ("\nOrdered data\n");
_twalk(root, WalkInOrder);
printf ("\nPreordered data\n");
_twalk(root, WalkPreOrder);
printf ("\nPostordered data\n");
_twalk(root, WalkPostOrder);
printf("\nDeleting data...\n");
void *p = _tdelete ((void *)keys[0], &root, MyCmp);
printf ("% .2d deleted (return value points to %d and root points to %d)\n", *keys[0], **((int **)p), **((int **)root));
p = _tdelete ((void *)keys[1], &root, MyCmp);
printf ("% .2d deleted (return value points to %d and root points to %d)\n", *keys[1], **((int **)p), **((int **)root));
printf("\n");
printf ("\nUnordered data\n");
_twalk(root, PrintWalk);
printf ("\nOrdered data\n");
_twalk(root, WalkInOrder);
printf ("\nPreordered data\n");
_twalk(root, WalkPreOrder);
printf ("\nPostordered data\n");
_twalk(root, WalkPostOrder);
printf("\nWalking data...\n");
_twalk(root, FindMinMax);
printf("\n");
printf("Minimum element is %d\n", min);
printf("Maximum element is %d\n", max);
}
I added a diagram below to show how the tree is built. It is correct. Check it against the program printout.What should 'endorder' be? I have never heard before.See below
How is it possible to traverse a tree in preorder, postorder or inorder traversal?Preorder means that the walk is entering a node with two childerns and moves on left branch descending on values lower than the root value.
My error! I forgot to remove the two deleted nodes from the tree.Why is 3 at level 0 and not 2?That's absolutely correct. To avoid any problem I rewrote the example:
Why is -14 at level 1 and not 2?
Shouldn't 3 be a leaf?
The next problem, I was not aware off is, that the tree is not build in a natural way. In a natural way, the 5 who is first inserted gets the root and will be the root until the 5 shall be deleted. Pelle uses an other insert stategy. May be some way of outobalancing the tree. I don't know! At the end the tree is a sorted binary tree. That's what counts.This should be a self-balanced tree, where the root changes to balance the tree at each isertion/deletion. There should be a trigger level that moves the root to keep both branches almost balanced.