C++

Forum

 
Preorder thread bin tree to be true?

Pages: 12
mlanuri10 (46)
I tried to arrange the code for the preOrder for the BinThreadTree. How can I arrange for them and make them true?

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
 
template <class BaseData>
bool BinThreadTree<BaseData>::preOrderAdd( BaseData item)
{

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

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

    left = true;
    done = parentq->leftThread;

    while (!done)
    {
        if (q != BinThreadTree<BaseData>::root)
            item = q->info;
        if(!q->leftThread)
        { 
            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 ;
}


My input values are 555, 111, 333, 99, 866, 666, 777.
I want the preOrder should be 555, 111, 99, 33, 866, 666, 777.
Last edited on
jonnin (11333)
you insert the same way no matter what.

preorder is just how you look at it once its inserted. not sure what you are asking, but preorderadd seems like either a bad name or a confused idea?

looking at it in preorder is just print(process, whatever), go left, go right.
mlanuri10 (46)
Preorder means mode, left, right. I have to use a thread binary tree with PreOrder when adding to the tree.
doug4 (1535)
As @jonnin said, adding and preorder refer to different things. Adding creates a tree. Preorder is for processing the elements of the tree, just as you described in your previous post (root, left, right).

The binary tree that you end up with when you enter your input values is:


             555
        ____/   \____
       /             \
    111               866
   /   \             /   \
 99     333       666     777


When you perform preorder processing, you get: 
555, 111, 99, 333, 866, 666, 777


This is exactly what you are looking for (except for your typo "33").

If your instructor is requiring preorder in the "add" step, you will have to ask him/her what he/she wants.
mlanuri10 (46)
Remember, threaded tree is the same as a binary tree but you have the left and right to be either threaded pointer or real pointer. So, I was asking for how to arrange them.

item = q->info // Processing the node

What about going to left and right based on the pointer either threaded or real pointer to another node?
doug4 (1535)
Remember, threaded tree is the same as a binary tree but you have the left and right to be either threaded pointer or real pointer.

Nothing for me to remember because I have never before heard of a threaded binary tree. I googled it and see what it is doing. The word "threaded" threw me off, because I thought it had something to do with parallel programming. Now I see it has an entirely different meaning in this context. (Yikes!)

I don't have any words of wisdom for you other than draw it out. This web page shows how to do an in-order threaded binary tree. Taking these concepts and massaging them to be a pre-order threaded binary tree should not be too complex for a competent programmer.

https://www.geeksforgeeks.org/threaded-binary-tree/
mlanuri10 (46)
Jeez, you haven't taught about Threaded Trees?
mlanuri10 (46)
Here's the outcome when I fixed the code: 555 111 333 99 866 666 777

I want the 99 to be first and then 333.

Anything wrong?
doug4 (1535)
Jeez, you haven't taught about Threaded Trees?


Nope. I'm sorry for my ignorance on the subject.

I won't bother this thread again.
dhayden (5795)
Jeez, you haven't taught about Threaded Trees?
First I've heard of them too, and I've been doing this for decades. The use case for threaded trees seems pretty limited to me too, especially in these days of ample RAM. So while interesting, I think you're learning about a data structure that isn't very useful.

Returning to the problem, the threaded pointers let you traverse the tree from smallest to largest - a linear traversal. This is definitely NOT what you want to do when inserting an item. You want to descend the tree based on the real pointers. The trick is updating the threaded pointers once you decide where to insert.

As an aside, why all the static casts to threadBinNode<BaseData>*? Aren't the pointers of that type to begin with? Perhaps you should show us the declaration of threadBinNode
mlanuri10 (46)
Can you please tell me what's wrong with my order? The pre order traversal.

555 111 333 99 866 666 777

99 has to be first and then 333.

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
 




#ifndef THREAD_BINNODE_H
#define THREAD_BINNODE_H


#ifndef leftChild
#define leftChild  firstChild
#endif

#ifndef rightChild
#define rightChild  sibling
#endif



#include "GtNode.h"

template <class BaseData>
class threadBinNode : public GtNode<BaseData>
  {
  public:
    bool leftThread, rightThread;
    threadBinNode();
    threadBinNode<BaseData> &operator = ( const threadBinNode<BaseData> & initThreadNode );
    threadBinNode (const threadBinNode<BaseData> &initNode);
  };


template <class BaseData>
threadBinNode<BaseData>::threadBinNode() : GtNode<BaseData>()
{
  leftThread = false;
  rightThread = false;
}


template <class BaseData>
threadBinNode<BaseData>& threadBinNode<BaseData>::
operator = (  const threadBinNode<BaseData> & initThreadNode )

{
  GtNode<BaseData>::operator = ( initThreadNode )
  (*this).leftThread = initThreadNode.leftThread;
  (*this).rightThread = initThreadNode.rightThread;

  return *this;
}




template <class BaseData>
threadBinNode<BaseData>::threadBinNode(  const threadBinNode<BaseData> & initNode )
    : GtNode<BaseData>(initNode)
{
  (*this).leftThread = initNode.leftThread;
  (*this).rightThread = initNode.rightThread;

}









#endif
dhayden (5795)
We still don't have enough information, or at least I don't.

I want the preOrder should be 555, 111, 99, 33, 866, 666, 777.
You haven't shown any code that produces output. So how can we tell what's wrong?

Please post a full program that compiles, along with the exact input that's causing trouble. Post the actual output you're getting and the output that you expect.
dhayden (5795)
There still isn't enough info to know the problem. Please post a program that compiles, along with the input that's causing trouble, the output that you're getting and the output that you expect. Right now your program doesn't generate any output. We can't see your main program so we don't know what it does with the input. It's like walking into a car repair shop, saying that there's a knocking noise and not bringing the car with you.
mlanuri10 (46)
@dhayden, here's the main program. I commented the some of them just to focus on that 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
 
#include <iostream>
using std::cout;
using std::cin;
using std::endl;



//#include "TD_Tree.h"
//#include "BinTree.h"
//#include "BinSearchTree.h"

#include "ThreadBinTree.h"

int preceed (const char& c1, const char& c2)
{
  return  c1 - c2;
}


bool preceed2 (const int &x, const int &y)
{
  return x <= y;
}


void dump(char & value)
{
  cout << value;
}

void dump2( int & value)
{
  cout << value << "  ";
}


int main()
{

  cout << endl;

  

   BinThreadTree<int> t5(preceed2);

    t5.preOrderAdd( 555 );
    t5.preOrderAdd( 111 );
    t5.preOrderAdd( 333 );
   t5.preOrderAdd( 99 );
   t5.preOrderAdd( 866 );
   t5.preOrderAdd( 666 );
   t5.preOrderAdd( 777 );

    t5.preorder( dump2);


    //BinThreadTree<int> t6(preceed2);

    //t6.inOrderAdd(555);
    //t6.inOrderAdd(111);
    //t6.inOrderAdd(333);
    //t6.inOrderAdd(99);
    //t6.inOrderAdd(866);
    //t6.inOrderAdd(666);
    //t6.inOrderAdd(777);

    //t6.inorder(dump2);





  /*

    TDTree<char>  t1( preceed);
    t1.add( 'H', 'H', 1 );
    t1.add( 'H', 'i', 1 );
    t1.add( 'i', ' ',  1);
    t1.add( 'H', 't', 2 );
    t1.add( 't', 'h', 1 );
    t1.add( 't', 'r', 2 );
    t1.add( 't', 'e', 3 );
    t1.add( 'h', 'E',  1);
    cout << " t1 printing breadth first traversal \n";
    t1.breadthFirstTraversal( dump);
    cout << endl << endl;


    cout << " t1 printing depth first traversal \n";
    t1.depthFirstTraversal( dump);
    cout << endl << endl;

  */







  cout<<endl;

  return (0);

}
Last edited on
dhayden (5795)
mlanuri10 You're still leaving us to guess too much. We can't compile what you've posted because we don't have most of the header files, including ThreadBinTree.h and GtNode.h.

Again, post code that will compile.
mlanuri10 (46)
There's a lot to it.

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
 


#ifndef THREAD_BINNODE_H
#define THREAD_BINNODE_H


#ifndef leftChild
#define leftChild  firstChild
#endif

#ifndef rightChild
#define rightChild  sibling
#endif



#include "GtNode.h"

template <class BaseData>
class threadBinNode : public GtNode<BaseData>
  {
  public:
    bool leftThread, rightThread;
    threadBinNode();
    threadBinNode<BaseData> &operator = ( const threadBinNode<BaseData> & initThreadNode );
    threadBinNode (const threadBinNode<BaseData> &initNode);
  };


template <class BaseData>
threadBinNode<BaseData>::threadBinNode() : GtNode<BaseData>()
{
  leftThread = false;
  rightThread = false;
}


template <class BaseData>
threadBinNode<BaseData>& threadBinNode<BaseData>::
operator = (  const threadBinNode<BaseData> & initThreadNode )

{
  GtNode<BaseData>::operator = ( initThreadNode )
  (*this).leftThread = initThreadNode.leftThread;
  (*this).rightThread = initThreadNode.rightThread;

  return *this;
}




template <class BaseData>
threadBinNode<BaseData>::threadBinNode(  const threadBinNode<BaseData> & initNode )
    : GtNode<BaseData>(initNode)
{
  (*this).leftThread = initNode.leftThread;
  (*this).rightThread = initNode.rightThread;

}

#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
42
43
44
45
46
47
48
49
50
51
52
53
54
 


#ifndef GTNODE_H
#define GTNODE_H


#include "Node.h"

template <class BaseData>
class GtNode : public Node<BaseData>
  {
  public:
    GtNode *firstChild, *sibling;  // pointers to subtrees
    GtNode();
    GtNode<BaseData> &operator = ( const GtNode<BaseData> & initGtNode );
    //needs copy constructor
    GtNode (const GtNode<BaseData> &initNode);
  };


template <class BaseData>
GtNode<BaseData>::GtNode() : Node<BaseData>()
{
  firstChild = 0;
  sibling = 0;
}


template <class BaseData>
GtNode<BaseData>& GtNode<BaseData>::operator = (  const GtNode<BaseData> & initGtNode )
{
  this = 0;
  GtNode<BaseData>   temp;
  temp -> info = initGtNode;
  temp-> firstChild = *(initGtNode.firstChild);
  temp -> sibling = *(initGtNode.sibling);
  this = &temp;

  return *this;
}

template <class BaseData>
GtNode<BaseData>::GtNode(  const GtNode<BaseData> & initGtNode )
{
  this = 0;
  GtNode<BaseData>   temp;
  temp -> info = initGtNode;
  temp-> firstChild = *(initGtNode.firstChild);
  temp -> sibling = *(initGtNode.sibling);
  this = &temp;

}
#endif



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 


#ifndef NODE_H
#define NODE_H


template <class BaseData>
class Node
  {
  public:
    BaseData info;                   // the data in the node
    Node();
  };

template <class BaseData>
Node<BaseData>::Node()
{
  info = (BaseData)0;
}


#endif


That's all.
dhayden (5795)
That's all.

No it isn't. We're still missing ThreadBinTree.h You included preorderAdd() in the first post but what about the rest of the class? There's a root member and a constructor and preorder() method.

I tried to cobble together a version of the class based on what you've posted. My program crashed here in preOrderAdd():
1
2
3
4
5
 

    while (!done)
    {
        if (q != BinThreadTree<BaseData>::root)
            item = q->info;   ///////////// CRASHES HERE

What is the initial value of root? Isn't it nullptr?
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
 
#ifndef THREADBINTREE_H
#define THREADBINTREE_H

#include <cstdio>

#include "BinSearchTree.h"
#include "threadBinNode.h"


template < typename BaseData >
class BinThreadTree : public BinSearchTree<BaseData>
  {

  public:
    BinThreadTree (   bool (*precedes)(const BaseData& x, const BaseData& y)    );
    //  BinSearchTree (const BinSearchTree<BaseData> &initBinSTree);
    void preorder(void (*processNode)(BaseData &item));
    void inorder(void (*processNode)(BaseData &item));
    virtual bool inOrderAdd (BaseData item);
    virtual bool preOrderAdd (BaseData item);

  protected:


  private:
    threadBinNode<BaseData> *root;

  };



#include "ThreadBinTree.t"


#endif
mlanuri10 (46)
Binary Search 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
 

#ifndef BINSEARCHTREE_T
#define BINSEARCHTREE_T

#include <queue>

#include <cstdio>


template <class BaseData>
BinSearchTree<BaseData>::
BinSearchTree ( bool (*precedes)(const BaseData& x, const BaseData& y) ) : BinTree<BaseData> ()
{
  this->precedes = precedes;
}

/*
template <class BaseData>
BinTree<BaseData>::BinTree( int numOfNodes ) : GenTree<BaseData> ()
{
  maxNodes = numOfNodes;
  numNodes = 0;
}
*/


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



/*
void BinSearchTree<BaseData>::operator = (const BinSearchTree<BaseData> & initBinSTree)
{
 (BinTree<BaseData>)(*this) = (Bintree<BaseData>)initBinSTree;
  precedes = initBinSTree.precedes;
}
*/


template <class BaseData>
bool BinSearchTree<BaseData>::add( BaseData item)
  {
    return addAux( GenTree<BaseData>::root, item);
  }





template <class BaseData>
bool BinSearchTree<BaseData>::addAux(GtNode<BaseData> *& rt, BaseData item)
// Note that since the pointer rt will be altered by this
// function, it must be passed by reference.
{

  if (rt == NULL)
    {
      rt = new GtNode<BaseData>;
      if (!rt)
        return false;
      else
        {
          rt -> info = item;
          rt -> leftChild  = 0;
          rt -> rightChild = 0;
          return true;
        }
    }
  else
    if (precedes(item, rt -> info))
      return addAux(rt -> leftChild, item);
    else
      return addAux(rt -> rightChild, item);



}



#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
 


#ifndef BINSEARCHTREE_H
#define  BINSEARCHTREE_H

#include <cstdio>

#include "BinTree.h"



template < typename BaseData >
class BinSearchTree : public BinTree<BaseData>
  {

  public:
    BinSearchTree (bool (*precedes)(const BaseData& x, const BaseData& y));
    BinSearchTree (const BinSearchTree<BaseData> &initBinSTree);
    //void operator = (const BinSSearchTree<BaseData> & initBinSTree);
    virtual bool add ( BaseData item);

  protected:
    // Comparison function for items in tree
    bool (*precedes)(const BaseData& x, const BaseData& y);

  private:
    //  private auxiliary functions
    bool addAux( GtNode<BaseData> *&rt, const BaseData item);

  };



#include "BinSearchTree.t"


#endif
mlanuri10 (46)
Binary 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
 


#ifndef BINTREE_T
#define BINTREE_T

#include <queue>

#include <cstdio>


template <class BaseData>
BinTree<BaseData>::BinTree() : GenTree<BaseData> ()
{
  maxNodes = 0;
  numNodes = 0;
}

template <class BaseData>
BinTree<BaseData>::BinTree( int numOfNodes ) : GenTree<BaseData> ()
{
  maxNodes = numOfNodes;
  numNodes = 0;
}

template <class BaseData>
BinTree<BaseData>::BinTree( const BinTree<BaseData> & initBinTree )
    : GenTree<BaseData>(initBinTree)
{
  if ( initBinTree.root != 0 )
    {
      maxNodes = initBinTree.maxNodes ;
      numNodes = initBinTree.numNodes ;
    }
  else GenTree<BaseData>::root  = 0;
  maxNodes = 0;
  numNodes = 0;
}



template<class BaseData>
BinTree<BaseData>::~BinTree()
{ }



template<class BaseData>
bool BinTree<BaseData>::full()
{
  if ( maxNodes == 0 ) return(false);
  else if ( numNodes == maxNodes ) return(true);
  else
    {
      return ( this -> GenTree<BaseData>::full() ) ;
    }

}




template <class BaseData>
void BinTree<BaseData>::operator = ( const BinTree<BaseData> & initBinTree )
{
  GenTree<BaseData>::operator = (initBinTree);

  maxNodes = initBinTree.maxNodes;
  numNodes = initBinTree.numNodes;
}



template <class BaseData>
void BinTree<BaseData>::breadthFirstTraversal( void (*processnode)(BaseData &value) )
{

  std::queue<  GtNode<BaseData>* > nodes2visit;

  GtNode<BaseData>  *item = GenTree<BaseData>::root;

  if ( item )
    {
      nodes2visit.push( item );

      while ( !nodes2visit.empty() )
        {
          item  =  nodes2visit.front();
          nodes2visit.pop();
          processnode( (item->info) );

          if (item -> firstChild )
            nodes2visit.push( item -> firstChild );

          if (item -> sibling )
            nodes2visit.push( item -> sibling );
        }
    }

}



#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
42
43
 


#ifndef BINTREE_H
#define  BINTREE_H

#include <cstdio>

#include "GenTree.h"


#ifndef leftChild
#define leftChild  firstChild
#endif

#ifndef rightChild
#define rightChild  sibling
#endif


template < typename BaseData >
class BinTree : public GenTree<BaseData>
  {
  protected:
    int maxNodes;
    int numNodes;

  public:
    BinTree();
    BinTree( int numOfNodes );     // constructor
    BinTree ( const BinTree<BaseData> & initBinTree );    // copy constructor
    virtual ~BinTree();
    bool full();
    void operator = ( const BinTree<BaseData> & initBinTree );  // assign
    virtual void breadthFirstTraversal( void (*processnode)(BaseData  &value) );
    virtual bool add( BaseData item ) = 0;

  };


#include "BinTree.t"


#endif
Pages: 12