# Binary Trees

2»

• : Thanks for the reply Steph. However, I'm not sure how I should notate the double pointer. Any input?
:
: Thanks,
: James
:

Then don't use it, because it still makes no sence.
• How about some information I can use Lundin, haha. I'm trying to stay consistent with the book and that's how they have it, using double pointers. Anyone?

Thanks,
James
• : How about some information I can use Lundin, haha. I'm trying to stay consistent with the book and that's how they have it, using double pointers. Anyone?
:
: Thanks,
: James
:

You still haven't told why you are using pointer-to-pointer. You just blindly do as they say in the book without reading the reason why? That function you wrote has absolutly no use for them.

• I believe the first pointer points to the root and the next (double) pointer points to the left or right branch of the tree.
• : I believe the first pointer points to the root and the next (double) pointer points to the left or right branch of the tree.
:

No it doesn't. As I see it, the only reason why they would use a double pointer is because they expect the function to dynamicly allocate something, then you would need a double pointer. Here is an example:

• : I believe the first pointer points to the root and the next (double) pointer points to the left or right branch of the tree.
:

It seems you did not understand something about pointers (the notation or something else). You should read or reread how to manipulate pointers before using trees. When you've got such a declaration:
[code]
struct node
{
struct node *left,*right;
int count;
char *word;
} tree;
[/code]
, tree is a structure and the child nodes are accessed this way:

tree.left
tree.right

and their members this way:

tree.left->count
tree.right->word

Take care, Steph.
• Here's the code u need to complete the god dam binary tree.

[code]

typedef struct nodeT {
int key;
struct nodeT *left,*right;
}nodeT,*treeT;

treeT NewTree(void) {//Funo para criar uma nova arvore
treeT arv;
arv = NULL;
return(arv);
}

treeT NewNode(int key) {//Funo para criar um novo n
treeT arv = New(treeT);
arv->key = key;
arv->left = NULL;
arv->right = NULL;

return(arv);
}

treeT insert(treeT arv, int key) {//Funo para inserir um novo n

if (arv == NULL) {
return(NewNode(key));
}
else {

if (key <= arv->key) arv->left = insert(arv->left, key);
else arv->right = insert(arv->right, key);

return(arv);
}
}
[/code]

Cheers, I've made this code a year ago, on a class of algorithms and data structures.
• Hey guys,

Sorry to revive this damn thread but I got it working. Thanks for the help once again.

James
• : Hi again,
:
: Yeah, the getword is from the book.
:
: Anyways, I've made a lot of progress, but now I'm getting a seg. fault. I have no idea why. I've commented where it's happening at the location that says:
:
: //*** SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0 ********
:
: As a refresher, this is the binary tree that counts words from a text file on the command line.
:
: Jim
:
: [code]
:
: #include
: #include
: struct tnode { // specify the "shape" of a tnode structure
: struct tnode *left; // the left and right branch pointers
: struct tnode *right;
: int count; // the word count
: char *word; // a pointer to the word
: } *root; // declare the root pointer variable
:
: struct tnode **tree_search(struct tnode **, char *);
: void tree_stats(struct tnode *);
: int get_word(char *);
:
: int total_nodes, total_words, high;
: struct tnode *most_frequent;
:
: int main(int argc, char *argv[]) {
: struct tnode **tpp;
: char word_buff[100]; // the reusable word buffer
: int i;
: while(get_word(word_buff)) {
: tpp = tree_search(&root, word_buff);
: /****CODE TO ADD NEW NODES AND COUNT REPEATS *****/
:
: if(*tpp!=NULL){
: (*tpp)->count++;
: }
: else{
: (*tpp)=malloc(sizeof(struct tnode));
: (*tpp)->left=NULL;
: (*tpp)->right=NULL;
: (*tpp)->count=1;
: (*tpp)->word=strdup(word_buff);
: }
:
: }
: tree_stats(root);
: printf("total_nodes %d
", total_nodes);
: printf("total_words %d
", total_words);
: if(most_frequent)
: printf("most frequent word <%s> count is %d
",
: most_frequent->word, most_frequent->count);
: for(i = 1; i < argc; i++) {
: tpp = tree_search(&root, argv[i]);
: if((*tpp) == NULL)
: printf("%s is NOT in the tree
", argv[i]);
: else
: printf("<%s> count is %d
", argv[i], (*tpp)-
: >count);
: }
: return(0);
: }
:
: // binary tree search returning a pointer to the pointer leading to hit
: struct tnode **tree_search(struct tnode **tpp, char *w) {
: /***** CODE TO DO THE BINARY SRCH *****/
: int cmp;
:
: while(*tpp){
: cmp=strcmp(w,(*tpp)->word);
: //*****SEG FAULT HAPPENING BELOW WHEN CMP IS <, >, OR == 0 ********
: if (cmp>0) {
: tpp=(*tpp)->right;
: }
: else if (cmp<0){
: tpp=(*tpp)->left;
: }
: else if (cmp==0){
: break;
: }
: }
:
:
: return(tpp);
: }
:
: // gather stats to check tree correctness
: void tree_stats(struct tnode *tp) {
: /***** RECURSIVE CODE TO COLLECT ALL OF THE STATISTICS *****/
: if(tp=NULL)
: return;
: total_words+=tp->count;
: total_nodes++;
: if(tp->count > high){
: high=tp->count;
: most_frequent=tp;
: }
: }
:
: #include
: /* Leave this routine EXACTLY as it stands */
: int get_word(char *s) {
: int c;
: do {
: c = getchar();
: if(c == EOF)
: return(0);
: } while(!isalpha(c) && !isdigit(c));
: do {
: if(isupper(c))
: c = tolower(c);
: *s++ = c;
: c = getchar();
: } while(isalpha(c) || isdigit(c));
: *s = 0;
: return(1);
: }
: [/code]
:
Hi,
I have a C++ Binary Tree library at www.5trees.com. In there you can use the tree class to count words in a file (and for many other things). The tree library took a couple of years to write and it has a lot of AVL code within. I have used it to write translators so counting words in a file is easy by comparison. Good Luck, Ben.