\hypertarget{structBSTNode}{
\section{BSTNode$<$ Data\-Type $>$ Struct Template Reference}
\label{structBSTNode}\index{BSTNode@{BSTNode}}
}
{\tt \#include $<$BSTNode.hh$>$}



\subsection{Detailed Description}
\subsubsection*{template$<$typename Data\-Type$>$ struct BSTNode$<$ Data\-Type $>$}

The Binary Search Tree node struct.

Contains the data for each node and also performs some important calculations on nodes to analyze tree structure. 



Definition at line 49 of file BSTNode.hh.\subsection*{Public Methods}
\begin{CompactItemize}
\item 
\hyperlink{structBSTNode_a0}{BSTNode} (const Data\-Type \&data, BSTNode $\ast$p\-Parent=NULL, BSTNode $\ast$p\-Left=NULL, BSTNode $\ast$p\-Right=NULL)
\begin{CompactList}\small\item\em Construct a node by copying the given data members.\item\end{CompactList}\item 
virtual BSTNode $\ast$ \hyperlink{structBSTNode_a1}{clone} (void) const
\begin{CompactList}\small\item\em Copy the current instance into a new BSTNode.\item\end{CompactList}\item 
virtual bool \hyperlink{structBSTNode_a2}{has\-Parent} (void) const
\begin{CompactList}\small\item\em True iff this node has a parent (i.e., if this node is $\ast$not$\ast$ the root).\item\end{CompactList}\item 
virtual bool \hyperlink{structBSTNode_a3}{has\-Grandparent} (void) const
\begin{CompactList}\small\item\em True iff this node's parent has a parent.\item\end{CompactList}\item 
virtual bool \hyperlink{structBSTNode_a4}{is\-Left\-Child} (void) const
\begin{CompactList}\small\item\em Tests if this node is the left child of its parent.\item\end{CompactList}\item 
virtual bool \hyperlink{structBSTNode_a5}{is\-Right\-Child} (void) const
\begin{CompactList}\small\item\em Tests if this node is the right child of its parent.\item\end{CompactList}\item 
virtual bool \hyperlink{structBSTNode_a6}{is\-Leaf} (void) const
\begin{CompactList}\small\item\em Tests of this node is a leaf (has no childern).\item\end{CompactList}\item 
virtual int \hyperlink{structBSTNode_a7}{get\-Num\-Children} (void) const
\begin{CompactList}\small\item\em Gets the number of children this node has.\item\end{CompactList}\item 
virtual bool \hyperlink{structBSTNode_a8}{is\-Zig\-Zig} (void) const
\begin{CompactList}\small\item\em Test if this node has a \char`\"{}Zig-Zig\char`\"{} relation to the root of the tree.\item\end{CompactList}\item 
virtual bool \hyperlink{structBSTNode_a9}{is\-Zig\-Zag} (void) const
\begin{CompactList}\small\item\em Test if this node has a \char`\"{}Zig-Zag\char`\"{} relation to the root of the tree.\item\end{CompactList}\item 
virtual void \hyperlink{structBSTNode_a10}{print} (std::ostream \&out=std::cout, std::string filler=\char`\"{}\char`\"{}) const
\begin{CompactList}\small\item\em Pretty-Print this node and its subtree.\item\end{CompactList}\item 
virtual BSTNode $\ast$ \hyperlink{structBSTNode_a11}{rotate\-Right} (void)
\begin{CompactList}\small\item\em Rotate this node with its right child, returning a pointer to node that is now in its place.\item\end{CompactList}\item 
virtual BSTNode $\ast$ \hyperlink{structBSTNode_a12}{rotate\-Left} (void)
\begin{CompactList}\small\item\em Rotate this node with its left child, returning a pointer to node that is now in its place.\item\end{CompactList}\end{CompactItemize}
\subsection*{Public Attributes}
\begin{CompactItemize}
\item 
Data\-Type \hyperlink{structBSTNode_m0}{m\_\-data}
\begin{CompactList}\small\item\em The data contained by this node.\item\end{CompactList}\item 
BSTNode $\ast$ \hyperlink{structBSTNode_m1}{m\_\-p\-Parent}
\begin{CompactList}\small\item\em pointer to this node's parent.\item\end{CompactList}\item 
BSTNode $\ast$ \hyperlink{structBSTNode_m2}{m\_\-p\-Left}
\begin{CompactList}\small\item\em pointer to this node's left child.\item\end{CompactList}\item 
BSTNode $\ast$ \hyperlink{structBSTNode_m3}{m\_\-p\-Right}
\begin{CompactList}\small\item\em pointer to this node's right child.\item\end{CompactList}\end{CompactItemize}


\subsection{Constructor \& Destructor Documentation}
\hypertarget{structBSTNode_a0}{
\index{BSTNode@{BSTNode}!BSTNode@{BSTNode}}
\index{BSTNode@{BSTNode}!BSTNode@{BSTNode}}
\subsubsection[BSTNode]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ BSTNode$<$ Data\-Type $>$::BSTNode (const Data\-Type \& {\em data}, BSTNode$<$ Data\-Type $>$ $\ast$ {\em p\-Parent} = NULL, BSTNode$<$ Data\-Type $>$ $\ast$ {\em p\-Left} = NULL, BSTNode$<$ Data\-Type $>$ $\ast$ {\em p\-Right} = NULL)}}
\label{structBSTNode_a0}


Construct a node by copying the given data members.

\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
data}]data item to initalize the node to. \item[{\em 
p\-Parent}]Pointer to parent node. Defaults to  {\tt NULL}. \item[{\em 
p\-Left}]Pointer to left child node. Defaults to  {\tt NULL}. \item[{\em 
p\-Right}]Pointer to right child node. Defaults to  {\tt NULL}. \end{description}
\end{Desc}


Definition at line 20 of file BSTNode.cc.

Referenced by BSTNode$<$ Data\-Type $>$::clone().

\subsection{Member Function Documentation}
\hypertarget{structBSTNode_a1}{
\index{BSTNode@{BSTNode}!clone@{clone}}
\index{clone@{clone}!BSTNode@{BSTNode}}
\subsubsection[clone]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ BSTNode$<$ Data\-Type $>$ $\ast$ BSTNode$<$ Data\-Type $>$::clone (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a1}


Copy the current instance into a new BSTNode.

The client is  responsible for deleting this newly allocated BSTNode

\begin{Desc}
\item[Returns :]\par
a dynamically allocated clone of the current node. \end{Desc}


Definition at line 40 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::BSTNode(), and BSTNode$<$ Data\-Type $>$::m\_\-data.\hypertarget{structBSTNode_a7}{
\index{BSTNode@{BSTNode}!getNumChildren@{getNumChildren}}
\index{getNumChildren@{getNumChildren}!BSTNode@{BSTNode}}
\subsubsection[getNumChildren]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ int BSTNode$<$ Data\-Type $>$::get\-Num\-Children (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a7}


Gets the number of children this node has.

As this is the node for a binary tree, the value will be either 0, 1, or 2.

\begin{Desc}
\item[Returns :]\par
the number of children this node has. \end{Desc}


Definition at line 88 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::m\_\-p\-Left, and BSTNode$<$ Data\-Type $>$::m\_\-p\-Right.

Referenced by BSTNode$<$ Data\-Type $>$::is\-Leaf().\hypertarget{structBSTNode_a3}{
\index{BSTNode@{BSTNode}!hasGrandparent@{hasGrandparent}}
\index{hasGrandparent@{hasGrandparent}!BSTNode@{BSTNode}}
\subsubsection[hasGrandparent]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ bool BSTNode$<$ Data\-Type $>$::has\-Grandparent (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a3}


True iff this node's parent has a parent.

\begin{Desc}
\item[Returns :]\par
{\tt true} if this node's parent has  a parent. \end{Desc}


Definition at line 56 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::has\-Parent(), and BSTNode$<$ Data\-Type $>$::m\_\-p\-Parent.

Referenced by BSTNode$<$ Data\-Type $>$::is\-Zig\-Zag(), and BSTNode$<$ Data\-Type $>$::is\-Zig\-Zig().\hypertarget{structBSTNode_a2}{
\index{BSTNode@{BSTNode}!hasParent@{hasParent}}
\index{hasParent@{hasParent}!BSTNode@{BSTNode}}
\subsubsection[hasParent]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ bool BSTNode$<$ Data\-Type $>$::has\-Parent (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a2}


True iff this node has a parent (i.e., if this node is $\ast$not$\ast$ the root).

\begin{Desc}
\item[Returns :]\par
{\tt true} if this node has a parent. \end{Desc}


Definition at line 48 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::m\_\-p\-Parent.

Referenced by BSTNode$<$ Data\-Type $>$::has\-Grandparent(), BSTNode$<$ Data\-Type $>$::is\-Left\-Child(), and BSTNode$<$ Data\-Type $>$::is\-Right\-Child().\hypertarget{structBSTNode_a6}{
\index{BSTNode@{BSTNode}!isLeaf@{isLeaf}}
\index{isLeaf@{isLeaf}!BSTNode@{BSTNode}}
\subsubsection[isLeaf]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ bool BSTNode$<$ Data\-Type $>$::is\-Leaf (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a6}


Tests of this node is a leaf (has no childern).

\begin{Desc}
\item[Returns :]\par
{\tt true} iff this node is a leaf. \end{Desc}


Definition at line 80 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::get\-Num\-Children().\hypertarget{structBSTNode_a4}{
\index{BSTNode@{BSTNode}!isLeftChild@{isLeftChild}}
\index{isLeftChild@{isLeftChild}!BSTNode@{BSTNode}}
\subsubsection[isLeftChild]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ bool BSTNode$<$ Data\-Type $>$::is\-Left\-Child (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a4}


Tests if this node is the left child of its parent.

If the node has no parent, it is not the left child of its parent,  so this function returns false.

\begin{Desc}
\item[Returns :]\par
{\tt true} iff this node is a left  child of its parent. {\tt false} if  this node does not have a parent. \end{Desc}


Definition at line 64 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::has\-Parent(), BSTNode$<$ Data\-Type $>$::m\_\-p\-Left, and BSTNode$<$ Data\-Type $>$::m\_\-p\-Parent.

Referenced by BSTNode$<$ Data\-Type $>$::is\-Zig\-Zig().\hypertarget{structBSTNode_a5}{
\index{BSTNode@{BSTNode}!isRightChild@{isRightChild}}
\index{isRightChild@{isRightChild}!BSTNode@{BSTNode}}
\subsubsection[isRightChild]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ bool BSTNode$<$ Data\-Type $>$::is\-Right\-Child (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a5}


Tests if this node is the right child of its parent.

If the node has no parent, it is not the right child of its parent,  so this function returns false.

\begin{Desc}
\item[Returns :]\par
{\tt true} iff this node is a right  child of its parent. {\tt false} if  this node does not have a parent. \end{Desc}


Definition at line 72 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::has\-Parent(), BSTNode$<$ Data\-Type $>$::m\_\-p\-Parent, and BSTNode$<$ Data\-Type $>$::m\_\-p\-Right.

Referenced by BSTNode$<$ Data\-Type $>$::is\-Zig\-Zig().\hypertarget{structBSTNode_a9}{
\index{BSTNode@{BSTNode}!isZigZag@{isZigZag}}
\index{isZigZag@{isZigZag}!BSTNode@{BSTNode}}
\subsubsection[isZigZag]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ bool BSTNode$<$ Data\-Type $>$::is\-Zig\-Zag (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a9}


Test if this node has a \char`\"{}Zig-Zag\char`\"{} relation to the root of the tree.

(left child of right child, or right child of left child)

\begin{Desc}
\item[Returns :]\par
{\tt true} iff this node is a left child of a  right child or a right child of a left child. \end{Desc}


Definition at line 128 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::has\-Grandparent(), and BSTNode$<$ Data\-Type $>$::is\-Zig\-Zig().\hypertarget{structBSTNode_a8}{
\index{BSTNode@{BSTNode}!isZigZig@{isZigZig}}
\index{isZigZig@{isZigZig}!BSTNode@{BSTNode}}
\subsubsection[isZigZig]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ bool BSTNode$<$ Data\-Type $>$::is\-Zig\-Zig (void) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a8}


Test if this node has a \char`\"{}Zig-Zig\char`\"{} relation to the root of the tree.

(left child of left child, or right child of right child)

\begin{Desc}
\item[Returns :]\par
{\tt true} iff this node is a right child of a  right child or a left child of a left child. \end{Desc}


Definition at line 107 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::has\-Grandparent(), BSTNode$<$ Data\-Type $>$::is\-Left\-Child(), BSTNode$<$ Data\-Type $>$::is\-Right\-Child(), and BSTNode$<$ Data\-Type $>$::m\_\-p\-Parent.

Referenced by BSTNode$<$ Data\-Type $>$::is\-Zig\-Zag().\hypertarget{structBSTNode_a10}{
\index{BSTNode@{BSTNode}!print@{print}}
\index{print@{print}!BSTNode@{BSTNode}}
\subsubsection[print]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ void BSTNode$<$ Data\-Type $>$::print (std::ostream \& {\em out} = std::cout, std::string {\em filler} = \char`\"{}\char`\"{}) const\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a10}


Pretty-Print this node and its subtree.

\begin{Desc}
\item[Parameters: ]\par
\begin{description}
\item[{\em 
out}]The {\tt ostream} to output the pretty printed tree to. \item[{\em 
filler}]The filler character to use while printing.  (Defaults to the emptry string. The client shouldn't mess with this.) \end{description}
\end{Desc}


Definition at line 138 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::m\_\-data, BSTNode$<$ Data\-Type $>$::m\_\-p\-Left, and BSTNode$<$ Data\-Type $>$::m\_\-p\-Right.\hypertarget{structBSTNode_a12}{
\index{BSTNode@{BSTNode}!rotateLeft@{rotateLeft}}
\index{rotateLeft@{rotateLeft}!BSTNode@{BSTNode}}
\subsubsection[rotateLeft]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ BSTNode$<$ Data\-Type $>$ $\ast$ BSTNode$<$ Data\-Type $>$::rotate\-Left (void)\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a12}


Rotate this node with its left child, returning a pointer to node that is now in its place.

\begin{Desc}
\item[Returns :]\par
a pointer to the node that has been rotated to the position where the current node was. \end{Desc}


Definition at line 207 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::m\_\-p\-Left, and BSTNode$<$ Data\-Type $>$::m\_\-p\-Right.\hypertarget{structBSTNode_a11}{
\index{BSTNode@{BSTNode}!rotateRight@{rotateRight}}
\index{rotateRight@{rotateRight}!BSTNode@{BSTNode}}
\subsubsection[rotateRight]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ BSTNode$<$ Data\-Type $>$ $\ast$ BSTNode$<$ Data\-Type $>$::rotate\-Right (void)\hspace{0.3cm}{\tt  \mbox{[}virtual\mbox{]}}}}
\label{structBSTNode_a11}


Rotate this node with its right child, returning a pointer to node that is now in its place.

\begin{Desc}
\item[Returns :]\par
a pointer to the node that has been rotated to the position where the current node was. \end{Desc}


Definition at line 186 of file BSTNode.cc.

References BSTNode$<$ Data\-Type $>$::m\_\-p\-Left, and BSTNode$<$ Data\-Type $>$::m\_\-p\-Right.

\subsection{Member Data Documentation}
\hypertarget{structBSTNode_m0}{
\index{BSTNode@{BSTNode}!m_data@{m\_\-data}}
\index{m_data@{m\_\-data}!BSTNode@{BSTNode}}
\subsubsection[m\_\-data]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ Data\-Type BSTNode$<$ Data\-Type $>$::m\_\-data}}
\label{structBSTNode_m0}


The data contained by this node.



Definition at line 208 of file BSTNode.hh.

Referenced by BSTNode$<$ Data\-Type $>$::clone(), and BSTNode$<$ Data\-Type $>$::print().\hypertarget{structBSTNode_m2}{
\index{BSTNode@{BSTNode}!m_pLeft@{m\_\-pLeft}}
\index{m_pLeft@{m\_\-pLeft}!BSTNode@{BSTNode}}
\subsubsection[m\_\-pLeft]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ BSTNode$\ast$ BSTNode$<$ Data\-Type $>$::m\_\-p\-Left}}
\label{structBSTNode_m2}


pointer to this node's left child.



Definition at line 214 of file BSTNode.hh.

Referenced by BSTNode$<$ Data\-Type $>$::get\-Num\-Children(), BSTNode$<$ Data\-Type $>$::is\-Left\-Child(), BSTNode$<$ Data\-Type $>$::print(), BSTNode$<$ Data\-Type $>$::rotate\-Left(), and BSTNode$<$ Data\-Type $>$::rotate\-Right().\hypertarget{structBSTNode_m1}{
\index{BSTNode@{BSTNode}!m_pParent@{m\_\-pParent}}
\index{m_pParent@{m\_\-pParent}!BSTNode@{BSTNode}}
\subsubsection[m\_\-pParent]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ BSTNode$\ast$ BSTNode$<$ Data\-Type $>$::m\_\-p\-Parent}}
\label{structBSTNode_m1}


pointer to this node's parent.



Definition at line 211 of file BSTNode.hh.

Referenced by Binary\-Search\-Tree$<$ Key\-Type, Value\-Type $>$::clone\-Tree(), BSTNode$<$ Data\-Type $>$::has\-Grandparent(), BSTNode$<$ Data\-Type $>$::has\-Parent(), BSTNode$<$ Data\-Type $>$::is\-Left\-Child(), BSTNode$<$ Data\-Type $>$::is\-Right\-Child(), and BSTNode$<$ Data\-Type $>$::is\-Zig\-Zig().\hypertarget{structBSTNode_m3}{
\index{BSTNode@{BSTNode}!m_pRight@{m\_\-pRight}}
\index{m_pRight@{m\_\-pRight}!BSTNode@{BSTNode}}
\subsubsection[m\_\-pRight]{\setlength{\rightskip}{0pt plus 5cm}template$<$typename Data\-Type$>$ BSTNode$\ast$ BSTNode$<$ Data\-Type $>$::m\_\-p\-Right}}
\label{structBSTNode_m3}


pointer to this node's right child.



Definition at line 217 of file BSTNode.hh.

Referenced by BSTNode$<$ Data\-Type $>$::get\-Num\-Children(), BSTNode$<$ Data\-Type $>$::is\-Right\-Child(), BSTNode$<$ Data\-Type $>$::print(), BSTNode$<$ Data\-Type $>$::rotate\-Left(), and BSTNode$<$ Data\-Type $>$::rotate\-Right().

The documentation for this struct was generated from the following files:\begin{CompactItemize}
\item 
\hyperlink{BSTNode_8hh}{BSTNode.hh}\item 
\hyperlink{BSTNode_8cc}{BSTNode.cc}\end{CompactItemize}
