C++

Forum

 
Preorder thread bin tree to be true?

Pages: 12
mlanuri10 (46)
General Tree

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
 



#ifndef GENTREE_T
#define GENTREE_T

#include "GtNode.h"


#include <queue>

#include <cstdio>

#include <iostream>
using std::cout;
using std::endl;

template <class BaseData>
GenTree<BaseData>::GenTree()
{
  root = 0;
}



template <class BaseData>
GenTree<BaseData>::GenTree(const GenTree<BaseData> & initGenTree)
{
  if (initGenTree.root != NULL)
    {
      root=new GtNode<BaseData>;
      copyAux(initGenTree.root,root);
    }
  else root=NULL;
}



template <class BaseData>
GenTree<BaseData>::~GenTree()
{
  delaux(root);
}



template <class BaseData>
bool GenTree<BaseData>::empty()
{
  if (root==NULL) return(true);
  else return(false);
}



template <class BaseData>
bool GenTree<BaseData>::full()
{
  GtNode<BaseData> *p;
  p=new GtNode<BaseData>;
  if (p==0) return(true);
  else
    {
      delete p;
      return(false);
    }
}



template <class BaseData>
void GenTree<BaseData>::operator = (const GenTree<BaseData> & initGenTree)
{
  if (root != NULL)
    {
      delaux(root->firstChild);
      delaux(root->sibling);
    }
  if (initGenTree.root != NULL)
    {
      if (root==NULL)
        root=new GtNode<BaseData>;
      copyAux(initGenTree.root,root);
    }
  else
    {
      if (root !=NULL) delete root;
      root=NULL;
    }
}



template <class BaseData>
void GenTree<BaseData>::copyAux(GtNode<BaseData> *src, GtNode<BaseData> *dest)
{
  if (src !=NULL)
    {
      dest->info=src->info;
      if (src->firstChild != NULL)
        {
          GtNode<BaseData> *temp;
          temp=new GtNode<BaseData>;
          dest->firstChild=temp;
          copyAux(src->firstChild,temp);
        }
      if (src->sibling != NULL)
        {
          GtNode<BaseData> *temp;
          temp=new GtNode<BaseData>;
          dest->sibling=temp;
          copyAux(src->sibling,temp);
        }
    }
}



template <class BaseData>
void GenTree<BaseData>::delaux(GtNode<BaseData> * rt)
{
  if (rt != NULL)
    {
      delaux(rt->firstChild);
      delaux(rt->sibling);
      delete rt;
    }
}




template <class BaseData>
void GenTree<BaseData>::depthFirstTraversal( void (*processnode)(BaseData &value) )
{
  depthFirstTraversalAux( GenTree<BaseData>::root,  processnode    )  ;
}



template <class BaseData>
void GenTree<BaseData>::depthFirstTraversalAux(  GtNode<BaseData>  *item ,
    void (*processnode)(BaseData &value) )
{
  if (item)
    {

      processnode( (item->info) );
      depthFirstTraversalAux(  (item->firstChild),  processnode )  ;
      depthFirstTraversalAux(  (item->sibling) , processnode  );
    }

}



#endif 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 

I guess that's everything. Let me know if there's any missing.


#ifndef GENTREE_H
#define  GENTREE_H

#include <cstdio>

#include "GtNode.h"

template < typename BaseData >
class GenTree
  {

  public:
    GenTree();
    GenTree(const GenTree<BaseData> & initGenTree);
    virtual ~GenTree();
    bool empty();
    virtual bool full();
    void operator = (const GenTree<BaseData> & initGenTree);
    void depthFirstTraversal( void (*processnode)(BaseData  &value) );
    virtual void breadthFirstTraversal( void (*processnode)(BaseData  &value) ) = 0;

  protected:
    GtNode<BaseData> *root;

  private:
    void copyAux(GtNode<BaseData> * src, GtNode<BaseData> * dest);
    void delaux(GtNode<BaseData> * rt);
    void depthFirstTraversalAux( GtNode<BaseData> *item ,
                                 void (*processnode)(BaseData  &value) );

  };


#include "GenTree.t"


#endif
dhayden (5795)
This seems like far too many classes for what it's doing.

Still missing ThreadBinTree.t.

In GtNode.h:

GtNode is a template but doesn't depend on BaseData. So there's no need for it to be a template.

1
2
3
4
5
6
7
8
9
10
11
12
13
 
template <class BaseData>
GtNode<BaseData>& GtNode<BaseData>::operator = (  const GtNode<BaseData> & init\
GtNode )
{
  this = 0;
  GtNode<BaseData>   temp;
  temp -> info = initGtNode;
  temp-> firstChild = *(initGtNode.firstChild);
  temp -> sibling = *(initGtNode.sibling);
  this = &temp;

  return *this;
}

Line 10 Doesn't do what you want and is probably illegal (I think this is const). You want to change the value within this:
1
2
3
4
5
6
7
8
9
 
template <class BaseData>
GtNode<BaseData>& GtNode<BaseData>::operator = (  const GtNode<BaseData> & init\
GtNode )
{
  info = initGtNode;
  firstChild = *(initGtNode.firstChild);
  sibling = *(initGtNode.sibling);
  return *this;
}


But is this right? are you leaking the previous values of firstChild and sibling? The big question here is who owns the subtrees? Who is responsible for deleting them? You need to decide and stick with it. Usually the node owns the subtrees.

Node.h should disappear. There no reason to have this class since it adds nothing to BaseData.

I think that, at most, you need 2 tree classes here: BinTree and ThreadBinTree
mlanuri10 (46)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
 



#ifndef THREADBINTREE_T
#define THREADBINTREE_T



#include <cstdio>

#ifndef leftChild
#define leftChild  firstChild
#endif

#ifndef rightChild
#define rightChild  sibling
#endif



template <class BaseData>
BinThreadTree<BaseData>::
BinThreadTree (  bool (*precedes)(const BaseData& x, const BaseData& y)    )   : BinSearchTree<BaseData> (  BinSearchTree<BaseData>::precedes )
{

  if (   GenTree<BaseData>::root == 0 )
    delete GenTree<BaseData>::root;

  BinThreadTree<BaseData>::root = new threadBinNode<BaseData>;
  BinThreadTree<BaseData>::root -> leftChild =  BinThreadTree<BaseData>::root;
  BinThreadTree<BaseData>::root -> rightChild =  BinThreadTree<BaseData>::root;
  BinThreadTree<BaseData>::root -> leftThread =  true;
  BinThreadTree<BaseData>::root -> rightThread =  false;

}



/*

template <class BaseData>
BinSearchTree<BaseData>::BinSearchTree (const BinSearchTree<BaseData> &initBinSTree)
{
  precedes=initBinSTree.precedes;
}

*/


template <class BaseData>
bool BinThreadTree<BaseData>::inOrderAdd( BaseData item)
{

  threadBinNode<BaseData> *q, *p, *parentq;
  bool left, done;
  p = new threadBinNode<BaseData>;
  p -> info = item;

  // Prepare for the while test by following the left child pointer
  // from the dummy header

  parentq =  BinThreadTree<BaseData>::root;
  q =   static_cast< threadBinNode<BaseData>*  >
        ( BinThreadTree<BaseData>::root ->  leftChild ) ;

  left = true;
  done = parentq -> leftThread;



  while ( !done )

    // Now allow q and its parent to travel down an appropriate branch until
    // an insertion spot is found
    //   if (precedes( item, q -> info) )
    if ( item <= q -> info )
      {
        parentq = static_cast< threadBinNode<BaseData>*  >(q);
        q =  static_cast< threadBinNode<BaseData>*  >
             (q -> leftChild )  ;
        left = true;
        done = parentq -> leftThread;
      }
    else
      {

        parentq = static_cast< threadBinNode<BaseData>*  >(q);
        q =  static_cast< threadBinNode<BaseData>*  >
             ( q -> rightChild ) ;
        left = false;
        done = parentq -> rightThread;
      }


  // Now insert p as the left or right child of parentq
  p -> leftThread = true;
  p -> rightThread = true;
  if (left)
    {
      p -> leftChild = static_cast< threadBinNode<BaseData>*  >( parentq -> leftChild);
      p -> rightChild =static_cast< threadBinNode<BaseData>*  >(parentq);
      parentq -> leftChild = static_cast< threadBinNode<BaseData>*  >(p);
      parentq -> leftThread = false;
    }
  else
    {
      p -> rightChild =
        static_cast< threadBinNode<BaseData>*  >(parentq -> rightChild);
      p -> leftChild =
        static_cast< threadBinNode<BaseData>*  >(parentq);

      parentq -> rightChild = static_cast< threadBinNode<BaseData>*  >(p);
      parentq -> rightThread = false;
    }


  return true ;
}



template <class BaseData>
void BinThreadTree<BaseData>::inorder(void (*processNode)(BaseData &item))
{

  threadBinNode<BaseData>  *p;
  p =   BinThreadTree<BaseData>::root;
  do
    {
      if (p->rightThread)
        p = static_cast< threadBinNode<BaseData>*  >(p->rightChild);
      else
        {
          p = static_cast< threadBinNode<BaseData>*  >(p->rightChild);
          while (!p->leftThread)
            p =  static_cast< threadBinNode<BaseData>*  >(p->leftChild);
        }
      if (p !=  BinThreadTree<BaseData>::root )
        processNode(p->info);
    }
  while (p != root);
}




template <class BaseData>
bool BinThreadTree<BaseData>::preOrderAdd( BaseData item)
{

/*  TODO */


  return true ;
}














template <class BaseData>
void BinThreadTree<BaseData>::preorder(void (*processNode)(BaseData &item))
{

  threadBinNode<BaseData>  *p;
  p =    static_cast< threadBinNode<BaseData>*  >
         ( BinThreadTree<BaseData>::root ->  leftChild ) ;


  do
    {
      if ( p !=   BinThreadTree<BaseData>::root )
        processNode( p->info );
      if  (!p -> leftThread )
        p =  static_cast< threadBinNode<BaseData>*  >(p -> leftChild);
      else
        p = static_cast< threadBinNode<BaseData>*  >(p->rightChild);

    }
  while (p !=   BinThreadTree<BaseData>::root );


}











#endif
dhayden (5795)
Thanks. At last I can compile the code.
mlanuri10 (46)
No problem. Just for the heck of it.


Here's the binary tree for you.
1
2
3
4
5
6
7
8
9
 

               555
        ____/   \____
       /                    \
    111                 866
   /   \                  /   
 99     333        666
                         \
                        777
dhayden (5795)
I'm sorry to say this but almost every method looks wrong to me. Perhaps I just don't understand but here are some questions:
- Why does the BinThreadTree constructor create a root node without data? Shouldn't it be null? Or is it always a sentinel and the left-most and right-most nodes point to the root instead of pointing to null?

- Why does inorder stop at the root? Why doesn't it start by descending the left side of the root?

- why doesn't preorder() check if the right node is threaded? It seems to me that it can bounce back and forth between a parent and the parent's left child.

Can you point me at a reference for how this code is supposed to work? The one that I found assumes that the tree starts empty and the left- and right- most nodes point to null to indicate the end of the tree.
mlanuri10 (46)
Threaded Binary starts at the header node or "dummy" node.

The header node has two real pointers. The left node points to the root of the tree and the right node points back to the header.

1
2
3
4
5
6
7
8
9
10
11
12
 
                        ___
                      /      |
              HEADER    |
                /      \___|
               555
        ____/   \____
       /                    \
    111                 866
   /   \                  /   
 99     333        666
                         \
                        777


If the right node is threaded, it will go to its successor of the traversal. Left node is threaded, it will go to its predecessor. When it ends the traversal, it should go back to the header and stops there.
dhayden (5795)
Do you need all these classes? The code would probably shrink by 50% or more if we can simplify it.

To that end, and because all the static casts were making my head hurt, I added left() and right() methods to threadBinNode():
1
2
3
4
5
6
 
    threadBinNode<BaseData> * &left() {
        return reinterpret_cast<threadBinNode<BaseData> * &>(GtNode<BaseData>::firstChild);
    }
    threadBinNode<BaseData> * &right() {
        return reinterpret_cast<threadBinNode<BaseData> * &> (GtNode<BaseData>::sibling);
    }

I also added a root() method to BinThreadTree:
1
2
3
 
      threadBinNode<BaseData> * &root() {
          return reinterpret_cast<threadBinNode<BaseData> * &> (BinSearchTree<BaseData>::root);
      }

I also removed the root member from BinThreadTree since you already have a root in one of the lower tree classes.

And I added (or fixed? I don't remember now) a destructor to threadBinNode:
1
2
3
4
5
6
 
template <class BaseData>
threadBinNode<BaseData>::~threadBinNode()
{
    if (!leftThread) delete left();
    if (!rightThread) delete right();
}


preOrderAdd() was just a mess. For example, it never called precedes(). How can you know where to insert the item if you don't compare to nodes in the tree? Also why do you have preorderAdd and inOrderAdd?? There should be just one add() method (and it should probably overload BinTree::add(), but that's a totally different story).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
template <class BaseData>
bool BinThreadTree<BaseData>::preOrderAdd( BaseData item)
{
    threadBinNode<BaseData>* q, * p;
    bool left, done;
    p = new threadBinNode<BaseData>;
    p->info = item;

    q = root()->left();

    left = true;
    done = root()->leftThread;

    while (!done)
    {
        left = BinSearchTree<BaseData>::precedes(item, q->info);
        if (left) {
            if (q->leftThread) {
                break;
            } else {
                q = q->left();
            }
        } else {
            if (q->rightThread) {
                break;
            } else {
                q = q->right();
            }
        }
    }

    // Now insert p as the left or right child of q
    p->leftThread = true;
    p->rightThread = true;
    if (left)
    {
        p->left() = q->left();
        p->right() = q;
        q->left() = p;
        q->leftThread = false;
    }
    else
    {
        p->right() = q->right();
        p->left() = q;
        q->right() = p;
        q->rightThread = false;
    }

  return true ;
}


Then inorder() was pretty easy:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
template <class BaseData>
void BinThreadTree<BaseData>::inorder(void (*processNode)(BaseData &item))
{
  threadBinNode<BaseData>  *p;
  p =  root();
  while (!p->leftThread) {
      p = p->left();
  }

  while (p != root()) {
      processNode(p->info);

      if (p->rightThread)
        p = p->right();
      else
        {
          p = p->right();
          while (!p->leftThread)
            p =  p->left();
        }
  }
}


I think the big question is still "why so many classes?" There seem to be far more than necessary to me. Are you using these base classes somewhere else? Do you expect that you will be? Unless the answer to one of these questions is "yes" then the base classes just get in the way (as evidenced by having to write a cumbersome static cast every time you accessed a pointer to a node).
Topic archived. No new replies allowed.
Pages: 12