Binary Trees

2»

Comments

  • : 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:

    http://www.programmersheaven.com/c/MsgBoard/read.asp?Board=586&MsgID=312054&Setting=A9999F0001
  • : 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.
    :
    : Thank you in advance,
    : 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.


Sign In or Register to comment.

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories