数据结构学习总结－7－二叉树 Time:2007-9-11
/*********************************************************************************** ** Program Name : correlative operations of BTree
** Author : Lu Jian Hua
** Time : 2007-6-2
************************************************************************************/
#include <iostream>
using namespace std ;
const int LEFT = 0 ;
const int RIGHT = 1 ;
/*-------------------------------------Class Node ( Node Of BTree )----------------START--------------------*/ class Node // Node of tree
{
public:
char c ; // data portion
Node *L_Child ; // left child
Node *R_Child ; // right child
Node *next ;
Node() : c(0), L_Child(NULL), R_Child(NULL) {}
Node(char ch) : c(ch), L_Child(NULL), R_Child(NULL), next(NULL) {}
} ;
/*-------------------------------------Class Node ( Node Of BTree )-----------------END---------------------*/
/*--------------------------------------Class Position------------------------------START-------------------*/ class Position
{
public:
Node *node ;
int pos ;
Position() : node(NULL), pos(LEFT) {}
Position(Node *n, int p) : node(n), pos(p) {}
} ;
/*--------------------------------------Class Position------------------------------END---------------------*/
/*--------------------------------------Class Stack---------------------------------START-------------------*/ class Stack
{
public:
Stack(int max_size) ; // constructor
Node* GetTopValue() const ; // get the top value of stack
void Push(Node* value) ; // push
Node* Pop() ; // pop
void Init() ; // initialize the stack
bool IsEmpty() ; // is empty ?
private:
enum { MAX_SIZE = 100 } ;
int top ;
数据结构学习总结－7－二叉树 Time:2007-9-11
Node* element[MAX_SIZE] ;
} ;
Stack::Stack(int max_size) : top(-1) {}
Node* Stack::GetTopValue() const
{
if (top < 0)
{
return 0 ;
}
return element[top] ;
}
void Stack::Push(Node* value) // Operation:push a element into stack {
if (top >= MAX_SIZE-1)
{
cout << "The stack is full! " << endl << endl ;
return ;
}
top++ ; // 1> move the top pointer
element[top] = value ; // 2> infill the space top pointer directing }
Node* Stack::Pop() // Operation:Pop a element from stack {
if (top < 0)
{
return 0 ;
}
Node* temp = element[top] ; // 1> get the value
top-- ; // 2> move the top pointer
return temp ;
}
void Stack::Init()
{
top = -1 ;
}
bool Stack::IsEmpty() // test if the stack is empty ?
{
return ( top < 0 ) ;
}
/*--------------------------------------Class Stack---------------------------------END---------------------*/
/*--------------------------------------Class Queue---------------------------------START-------------------*/
数据结构学习总结－7－二叉树 Time:2007-9-11
class Queue // class of Queue
{
public:
Queue() ;
Node* GetValue() const ; // get the current value of Queue Node* Delete() ; // out_Queue
void Append(Node* value) ; // In__Queue bool IsEmpty() const ; // is empty ?
bool IsFull() const ; // is full ?
private:
int front ; // front
int rear ; // rear
enum { MAX_SIZE = 500 } ; // Notice:remember ; at the end Node* element[MAX_SIZE] ; // implement with array
} ;
Queue::Queue() : front(0), rear(0) {}
Node* Queue::GetValue() const
{
if ( IsEmpty() )
{
cout << "The queue is empty!" << endl << endl ;
return 0 ;
}
int temp = front ;
return element[++temp] ;
}
void Queue::Append(Node* value)
{
if ( IsFull() )
{
cout << "The queue is full!" << endl << endl ;
return ;
}
rear = (rear+1) % MAX_SIZE ;
element[rear] = value ;
}
Node* Queue::Delete()
{
if ( IsEmpty() )
{
cout << "The queue is empty!" << endl << endl ;
return 0 ;
}
//return element[(++front) % MAX_SIZE] ; // different from the next sentence?? front = (front+1) % MAX_SIZE ;
return element[front] ;
}
数据结构学习总结－7－二叉树 Time:2007-9-11
bool Queue::IsEmpty() const
{
return (rear == front) ;
}
bool Queue::IsFull() const
{
return ( (rear+1) % MAX_SIZE == front ) ;
}
/*--------------------------------------Class Queue---------------------------------END---------------------*/
/*--------------------------------------GLOBAL VARIABLE-----------------------------START-------------------*/
Node* TAG = (Node*)10000 ;
const int ROW = 80 ;
const int COL = 80 ;
char a[ROW][COL] ;
Node *RFPrint = NULL ; // root_for_print
/*--------------------------------------GLOBAL VARIABLE-----------------------------END---------------------*/
void operator <<(ostream os, Node node) //-------------- output a node directly ---------------------- {
os << node.c << " " ;
}
int max(int a, int b) //-------------- return the maximum of two values ------------
{
return ( a > b ? a : b ) ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Pre_Order
** Parameters : Node *root (the root of a binary tree)
** Return Value : void
** Details : all the nodes of a binary tree will be printed in PreOrder by RECURSION **--------------------------------------------------------------------------------------------------------*/
void Pre_Order(Node *root) // the recursive function
{
if (root == NULL) // the end condition for recursion
return ;
cout << (*root) ; // print the node
Pre_Order(root->L_Child) ; // dispose the left node
Pre_Order(root->R_Child) ; // dispose the right node
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Pre_Order2
** Parameters : Node *root (the root of a binary tree)
** Stack *s (the stack used)
** Return Value : void
数据结构学习总结－7－二叉树 Time:2007-9-11
** Details : 1> print all the nodes of a binary tree in Pre_Order
** 2> NON-REVISION
** 3> use a stack
**--------------------------------------------------------------------------------------------------------*/
void Pre_Order2(Node *root) // the function without recursion
{
Stack* s = new Stack(100) ;
while (root)
{
cout << (*root) ; // print the node first
if (root->R_Child) // push the right node
s->Push(root->R_Child) ;
if (root->L_Child) // if left child exists, dispose it in the same way root = root->L_Child ;
else // if left child no exists, pop the proper right node to dispose
root = s->Pop() ;
}
delete s ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Mid_Order
** Parameters : Node *root (the root of a binary tree)
** Return Value : void
** Details : all the nodes of a binary tree in MidOrder by RECURSION
**--------------------------------------------------------------------------------------------------------*/
void Mid_Order(Node *root) // the recursive function
{
if (root == NULL) // the end condition for recursion
return ;
Mid_Order(root->L_Child) ; // dispose the left node
cout << (*root) ; // print the node
Mid_Order(root->R_Child) ; // dispose the right node
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Mid_Order2
** Parameters : Node *root (the root of a binary tree)
** Stack *s (the stack used)
** Return Value : void
** Details : 1> print all the nodes of a binary tree in Mid_Order
** 2> NON-RECURSION
** 3> use a stack
**--------------------------------------------------------------------------------------------------------*/
void Mid_Order2(Node *r)
{
Stack *s = new Stack(100) ;
while ( r || s->IsEmpty() == false )
{
if (r)
数据结构学习总结－7－二叉树 Time:2007-9-11
{
s->Push(r) ; // push the node
r = r->L_Child ;
}
else // if no more node in the left
{
Node *temp = s->Pop() ;
cout << (*temp) ;
r = temp->R_Child ; // after output the node, then visit the right node }
}
delete s ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Pos_Order
** Parameters : Node *root (the root of a binary tree)
** Return Value : void
** Details : all the nodes of a binary tree in PostOrder by RECURSION
**--------------------------------------------------------------------------------------------------------*/ void Pos_Order(Node *root) // the recursive function
{
if (root == NULL) // the end condition for recursion
return ;
Pos_Order(root->L_Child) ; // dispose the left node
Pos_Order(root->R_Child) ; // dispose the right node
cout << (*root) ; // print the node
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Pos_Order2
** Parameters : Node *root (the root of a binary tree)
** Stack *s (the stack used)
** Return Value : void
** Details : 1> print all the nodes of a binary tree in Post_Order
** 2> NON-RECURSION
** 3> use a stack
**--------------------------------------------------------------------------------------------------------*/ void Pos_Order2(Node *r)
{
Stack *s = new Stack(100) ;
while ( r || s->IsEmpty() == false ) // end until the stack is empty
{
if (r) // any node here thought as a middle node {
s->Push(r) ;
r = r->L_Child ;
}
else // when the node has no left node, dispose it {
if ( (s->GetTopValue())->R_Child == NULL) // if has no right node {
cout << ( *(s->Pop()) ) ; // output the node directly
/*-----------------------------------------------------------------------------------------
数据结构学习总结－7－二叉树 Time:2007-9-11
* If s->GetTopValue() == TAG, indicates that the nodes in the right portion have been pushed
* into the stack, so it can be pop directly, or indicates these nodes have not been pushed
* into the stack. The tag is just used to different from both cases.
------------------------------------------------------------------------------------------*/
while (s->GetTopValue() != NULL && s->GetTopValue() == TAG) {
s->Pop() ;
cout << ( *(s->Pop()) ) ;
}
}
else // if it has right node
{
Node *temp = s->GetTopValue() ;
s->Push(TAG) ;
r = temp->R_Child ;
}
}
} // end while
delete s ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Get_Node_Counts
** Parameters : Node *root (the root of a binary tree)
** Return Value : int (the total nodes of the binary tree)
** Details : get total counts of nodes in a binary tree through the RECURSION way
**--------------------------------------------------------------------------------------------------------*/
int Get_Node_Counts(Node *r) /* r = root */
{
if (r == NULL)
return 0 ;
else
return ( 1+ Get_Node_Counts(r->L_Child) + Get_Node_Counts(r->R_Child) );
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Get_Node_Counts2
** Parameters : Node *root (the root of a binary tree)
** Stack *s (the stack used)
** Return Value : int (the total nodes of the binary tree)
** Details : get total counts of the nodes in a binary tree through NON-RECURSION
**--------------------------------------------------------------------------------------------------------*/
int Get_Node_Counts2(Node *r)
{
Stack *s = new Stack(100) ;
int count = 0 ;
while (r)
{
++ count ;
if (r->R_Child)
s->Push(r->R_Child) ;
数据结构学习总结－7－二叉树 Time:2007-9-11
if (r->L_Child)
r = r->L_Child ;
else
r = s->Pop() ;
}
delete s ;
return count ;
}
/*-------------------------------------------------------------------------------------------------------- ** Function Name : Get_Tree_Height
** Parameters : Node *root (the root of a binary tree)
** Return Value : int (the height of the binary tree)
** Details : get the height of a binary tree in the way of recursion
**--------------------------------------------------------------------------------------------------------*/ int Get_Tree_Height(Node *r)
{
if (r == NULL)
return 0 ;
else
return ( 1+ max(Get_Tree_Height(r->L_Child), Get_Tree_Height(r->R_Child)) ) ; }
/*-------------------------------------------------------------------------------------------------------- ** Function Name : Leftest
** Parameters : Node *r
** Return Value : Node*
** Details : find the leftest node of a node
**--------------------------------------------------------------------------------------------------------*/ Node* Leftest(Node *r)
{
if (r == NULL)
return NULL ;
while (r)
{
if (r->L_Child == NULL)
return r ;
else
r = r->L_Child ;
}
return r ;
}
/*-------------------------------------------------------------------------------------------------------- ** Function Name : Righest
** Parameters : Node *r
** Return Value : Node*
** Details : find the Rightest node of a node
**--------------------------------------------------------------------------------------------------------*/ Node* Rightest(Node *r)
{
if (r == NULL)
数据结构学习总结－7－二叉树 Time:2007-9-11
return NULL ;
while (r)
{
if (r->R_Child == NULL)
return r ;
else
r = r->R_Child ;
}
return r ;
}
/*-------------------------------------------------------------------------------------------------------- ** Function Name : BTree_To_List
** Parameters : Node *r (r == root)
** Return Value : Node * (return the header of the chain)
** Details : the function transform a binary tree to a single chain (Mid_Order)
**--------------------------------------------------------------------------------------------------------*/ void Make_Links(Node *r) // r = root
{
if (r == NULL)
return ;
if (r->L_Child)
Rightest(r->L_Child)->next = r ;
if (r->R_Child)
r->next = Leftest(r->R_Child) ;
Make_Links(r->L_Child) ;
Make_Links(r->R_Child) ;
}
Node* BTree_To_List(Node *r)
{
Node *left = Leftest(r) ;
Node *right = Rightest(r) ;
Node *header = new Node('H') ;
header->next = left ;
right->next = NULL ;
Make_Links(r) ;
return header ;
}
/*-------------------------------------------------------------------------------------------------------- ** Function Name : List_Printer
** Parameters : Node *header (the header of a chain)
** Return Value : void
** Details : print all the nodes of the chain
**--------------------------------------------------------------------------------------------------------*/ void List_Printer(const Node *header) // List_Printer
{
const Node *recent = header ;
while (recent)
{
数据结构学习总结－7－二叉树 Time:2007-9-11
cout << recent->c << " --> " ;
recent = recent->next ;
if (recent == NULL)
cout << "NULL" ;
}
cout << endl << endl ;
}
/*-------------------------------------------------------------------------------------------------------- ** Function Name : Hierarchy_Travel
** Parameters : Node *root (the root of a binary tree)
** Queue *q (the queue to be used)
** Return Value : void
** Details : the function travel a binary tree hierarchically by use a queue
**--------------------------------------------------------------------------------------------------------*/ void Hierarchy_Travel(Node *r)
{
Queue *q = new Queue() ;
if (r == NULL)
{
cout << "A NULL Tree!" << endl << endl ;
return ;
}
/*--------------------------------------------------------------------------------
** Details : First append the root to the queue, and then, after letting a node out ** from the queue, you must let its left child and its right child into ** the queue.(Of course, on condition that it has child exists)
** Circle until no elements exist in the queue
**--------------------------------------------------------------------------------*/
q->Append(r) ;
while (q->IsEmpty() == false)
{
Node *temp = q->Delete() ;
cout << (*temp) ;
if (temp->L_Child)
q->Append(temp->L_Child) ;
if (temp->R_Child)
q->Append(temp->R_Child) ;
}
delete q ;
}
/*-------------------------------------------------------------------------------------------------------- ** Function Name : Find_Null_Node
** Parameters : Node *root (the root of a binary tree)
** Queue *q (the queue to be used)
** Return Value : Position (the data structure has been defined)
** Details : 1> The function are always used in a full binary tree
** 2> It can find the first node whose left child or right child is NULL
**--------------------------------------------------------------------------------------------------------*/
数据结构学习总结－7－二叉树 Time:2007-9-11
Position Find_Null_Node(Node *r, Queue *q)
{
if (r == NULL) // if a binary tree is null, return NULL to indicate return Position(NULL, LEFT) ;
if (q->IsEmpty() )
q->Append(r) ;
while (q->IsEmpty() == false)
{
Node *temp = q->GetValue() ;
if (temp->L_Child == NULL)
return Position(temp, LEFT) ;
if (temp->R_Child == NULL)
return Position(temp, RIGHT) ;
q->Delete() ;
if (temp->L_Child)
q->Append(temp->L_Child) ;
if (temp->R_Child)
q->Append(temp->R_Child) ;
}
return Position(NULL, LEFT) ;
}
/*--------------------------------------------------------------------------------------------------------
** Function Name : Add_New_Node
** Parameters : Position pos(pos is a data structure, it contains a pointer of the node to be added and ** the direction [left or righ?] to be added)
** Queue *q (the queue to be used)
** Node *node (the node will be added to the full binary tree)
** Return Value : void
** Details : add a new node into a full binary tree
**--------------------------------------------------------------------------------------------------------*/
void Add_New_Node(Position pos, Node *node, Queue *q)
{
if (pos.node == NULL)
{
cout << "Can't be added, the binary tree is empty!" ;
return ;
}
if (pos.pos == LEFT)
pos.node->L_Child = node ;
else
pos.node->R_Child = node ;
q->Append(node) ;
}
/*--------------------------------------------------------------------------------------------------------
数据结构学习总结－7－二叉树 Time:2007-9-11
** Function Name : Print
** Parameters : Node *root (the root of a binary tree)
** int x (x coordinate of the certain node)
** int y (y coordinate of the certain node)
** Return Value : void
** Details : print the architecture to a table
**--------------------------------------------------------------------------------------------------------*/ void Print(Node *r, int x, int y) // r==root, a=arry, x=coordinate x, y=coordinate y {
Queue queue ;
static Queue *q = &queue ;
if (r == NULL)
return ;
q->Append(r) ;
while (q->IsEmpty() == false)
{
Node *temp = q->Delete() ;
a[x][y] = temp->c ;
if (temp->L_Child)
a[x+1][y-1] = '/' ;
if (temp->R_Child)
a[x+1][y+1] = '\\' ;
if (temp->L_Child)
q->Append(temp->L_Child) ;
if (temp->R_Child)
q->Append(temp->R_Child) ;
}
}
/*-------------------------------------------------------------------------------------------------------- ** Function Name : Get_Node_Rank
** Parameters : Node *root (the root of a binary tree)
** Node *recent (the recent node to be disposed)
** Return Value : void
** Details : get the rank of a certain node in the binary tree
** root : 1
** .... : 2
** .... : 3
** .... : 4
** ........
**--------------------------------------------------------------------------------------------------------*/ int Get_Node_Rank(Node *root, Node *recent)
{
bool found = false ;
int count = 0 ;
Stack s(100) ; // the stack may be used
while (root)
{
s.Push(root) ;
if ( s.GetTopValue() == recent )
数据结构学习总结－7－二叉树 Time:2007-9-11
} } { } else found = true ; break ; root = root->L_Child ; if (root == NULL) { Node *temp = s.GetTopValue() ; s.Push(TAG) ; root = temp->R_Child ; if (root == NULL) { while (true) { if (s.GetTopValue() == TAG) { s.Pop() ; s.Pop() ; } else { if (s.GetTopValue() == NULL) cout << "Null Pointer Exists..." << endl << endl ; root = ( s.GetTopValue()) ->R_Child ; if (root == NULL) { s.Pop() ; continue ; } else { s.Push(TAG) ; break ; } } } } } if (found) { while (s.IsEmpty() == false) { if (s.Pop() != TAG) count ++ ; } } else return 0 ; return count ;
数据结构学习总结－7－二叉树 Time:2007-9-11
/*-------------------------------------------------------------------------------------------------------- ** Function Name : Print_Tree
** Parameters : Node *root (the root of a binary tree)
** int x (x coordinate of the certain node)
** int y (y coordinate of the certain node)
** Return Value : void
** Details : print the architecture to the screen(through a table)
**--------------------------------------------------------------------------------------------------------*/ void Print_Tree(Node *r, int x, int y)
{
int num = ( Get_Node_Rank(RFPrint, r) <= 7 ? (8-Get_Node_Rank(RFPrint,r)) : 1 ) ; a[x][y] = r->c ;
for (int i=1; i<=num; i++)
{
if (r->L_Child)
a[x+i][y-i] = '/' ;
if (r->R_Child)
a[x+i][y+i] = '\\' ;
}
if (r->L_Child)
{
Print_Tree(r->L_Child, x+(num+1), y-(num+1)) ;
}
if (r->R_Child)
{
Print_Tree(r->R_Child, x+(num+1), y+(num+1)) ;
}
}
/*-------------------------------------------------------------------------------------------------------- ** Function Name : Init_Table
** Parameters : NULL
** Return Value : void
** Details : initialize all the elements of the table with NULL character
**--------------------------------------------------------------------------------------------------------*/ void Init_Table()
{
for (int i=0; i<ROW; i++) // initialize the char table for (int j=0; j<COL; j++)
a[i][j] = ' ' ;
}
/*-------------------------------------------------------------------------------------------------------- ** Function Name : Print_Table
** Parameters : NULL
** Return Value : void
** Details : print the table to the screen
**--------------------------------------------------------------------------------------------------------*/ void Print_Table()
{
for (int i=0; i<ROW; i++) // print the tree for (int j=0; j<COL; j++)
cout << a[i][j] ;
}
数据结构学习总结－7－二叉树 Time:2007-9-11
int main()
{
Node A = Node('A') ;
Node B = Node('B') ;
Node C = Node('C') ;
Node D = Node('D') ;
Node E = Node('E') ;
Node F = Node('F') ;
Node G = Node('G') ;
Node H = Node('H') ;
Node I = Node('I') ;
Node J = Node('J') ;
Node K = Node('K') ;
Node L = Node('L') ;
Node M = Node('M') ;
Node N = Node('N') ;
Node O = Node('O') ;
Node P = Node('P') ;
Node Q = Node('Q') ;
A.L_Child = &B ;
A.R_Child = &C ;
B.L_Child = &D ;
B.R_Child = &E ;
C.L_Child = &F ;
C.R_Child = &G ;
D.L_Child = &H ;
D.R_Child = &I ;
E.L_Child = &J ;
E.R_Child = &K ;
F.L_Child = &L ;
F.R_Child = &M ;
G.L_Child = &N ;
G.R_Child = &O ;
H.L_Child = &P ;
H.R_Child = &Q ;
Node *root = &A ;
cout << "------------------------------------------------------------------------------" << endl
<< "Details : The Program Demenstrate The Correlative Operations Of A Binary Tree" << endl
<< "Author : Lu Jian Hua" << endl
<< "Time : 2007-6-9" << endl
<< "------------------------------------------------------------------------------" << endl << endl ;
Init_Table() ;
RFPrint = root ;
Print_Tree(root, 0, 40) ; // print the tree to the char table
Print_Table() ;
cout << "The results of hierachy travel : " ;
Hierarchy_Travel(root) ; // hierarchy Travel
cout << endl << endl ;
数据结构学习总结－7－二叉树 Time:2007-9-11
cout << "The Quantity Of Nodes (With Recursion) : " << Get_Node_Counts(root) << endl << endl
<< "The Quantity Of Nodes (NO Recursion) : " << Get_Node_Counts2(root) << endl << endl
<< "The Height Of Tree (NO Recursion) : " << Get_Tree_Height(root) << endl << endl
<< "The Leftest Node : " ;
cout << Leftest(root)->c << endl << endl ;
cout << "The Leftest Node : " ;
cout << Rightest(root)->c << endl << endl ;
cout << "Pre Order With Recursion : " ;
Pre_Order(root) ; cout << endl << endl ;
cout << "Pre Order No Recursion : " ;
Pre_Order2(root) ; cout << endl << endl ;
cout << "Mid Order With Recursion : " ;
Mid_Order(root) ; cout << endl << endl ;
cout << "Mid Order No Recursion : " ;
Mid_Order2(root) ; cout << endl << endl ;
cout << "Pos Order With Recursion : " ;
Pos_Order(root) ; cout << endl << endl ;
cout << "Pos Order No Recursion : " ;
Pos_Order2(root) ; cout << endl << endl ;
cout << "The Binary Tree Can Be Transformed Into A Single Chain ..." << endl << endl << "The Result As Follows : " << endl << endl ;
List_Printer( BTree_To_List(root) ) ;
cout << "----------------------------------------------------" << endl
<< " Now Will Build A Full Binary Tree " << endl
<< "----------------------------------------------------" << endl << endl ;
Node r = Node('A');
Queue q ;
while (true)
{
char c = 0 ;
cout << "Another Node ? (Y/N) " ;
cin >> c;
if (c != 'n' && c != 'N')
{
Node *temp = new Node() ;
cout << "Please Enter The Value : " ;
cin >> temp->c ;
temp->L_Child = temp->R_Child = NULL ;
Add_New_Node( Find_Null_Node(&r, &q), temp, &q ) ;
}
数据结构学习总结－7－二叉树 Time:2007-9-11
else
break ;
}
RFPrint = &r ;
Init_Table() ;
Print_Tree(&r, 0, 40) ;
Print_Table() ;
system("pause") ;
return 0 ;
}
/******************************************************************************** *
* Notice : This Program Can Be Launched In VC6.0 Environment
*
********************************************************************************/