树的建立、深度及路径

#include <cstdlib>
#include <iostream>
#include "Tree.h"
#include "Stack.h"
using namespace std;

int main()
{
    Tree<char> tree;
    cout << "Enter each Nodes two ones a time, which are SuperNode and SubNode : "<<endl;

    tree.CreatTree();
   
    int height=tree.getHeight();
   
    cout << "The height of this tree is "<<height<<endl;
   
    cout<<endl;   
    cout << "Each path in this tree is as following :"<<endl;
   
    tree.getAllpath();
   
   
    system("PAUSE");
   
    return 0;
}

 

 

#include <iostream>
#include"Queue.h"
#include"Stack.h"
#ifndef TREE_H
#define TREE_H

using namespace std;

template<typename T>
class TreeNode
{
public:
  T element;
  TreeNode<T> * firstchild;
  TreeNode<T> * nextsibling;

  TreeNode()
  {
    firstchild = NULL;
    nextsibling = NULL;
  }

  TreeNode(T element)
  {
    this->element = element;
    firstchild = NULL;
    nextsibling = NULL;
  }
};
template < typename T >
 class Tree
 {
 public:
  Tree();
  int getSize();
  int getHeight();
  void CreatTree();
  void getAllpath();
  
 private:
  TreeNode<T> * root;
  Queue<TreeNode<T>*> queue;
  Stack<char> stack;
  int size;
  int Height(TreeNode<T> *root);
  void Allpath(TreeNode<T> *root);
};

template < typename T >
Tree<T>::Tree()
{
  root=new TreeNode<T>();
}

template < typename T >
void Tree<T>::CreatTree()
{
  char fa,ch;
  cin>>fa;
  cin>>ch;
 
  TreeNode<T> *r;
  TreeNode<T> *p;
  for( ; ch!='#' ; ){
   p =new TreeNode<T>(ch);
   queue.enqueue(p);
   if(fa=='@')  root=p;
    else
    {
      TreeNode<T>*treenode=queue.getHead();
         while(treenode->element!=fa){
              queue.dequeue();
              treenode=queue.getHead();
         };
       
        if(!(treenode->firstchild))
        {treenode->firstchild=p;
         r=p;
         size++;
        
        }
        else
        {r->nextsibling=p;
         r=p;
         size++;
       
        }
    }
    cin>>fa;cin>>ch;
  }
}

template < typename T >
int Tree<T>::getHeight()
{
  return Height(root);
}

template < typename T >
int Tree<T>::Height(TreeNode<T> *root)
{
  if(!root) return 0;
  else{
       int h1=Height(root->firstchild);
       int h2=Height(root->nextsibling);
       if(h2>(h1+1))
            return h2;
       else return h1+1;
      }
}

template < typename T >
void Tree<T>::getAllpath()
{
  Allpath(root);
}

template < typename T >
void Tree<T>::Allpath(TreeNode<T> *r)
{
  while(r){
           stack.push(r->element);
           if(!r->firstchild)
              stack.print();
           else Allpath(r->firstchild);
           char del=stack.pop();
           r=r->nextsibling;
  }
}

#endif

 

#ifndef QUEUE_H
#define QUEUE_H
#include <stdexcept>
using namespace std;

template<typename T>
class Node
{
public:
  T element;  // Element contained in the node
  Node<T> *next; // Pointer to the next node

  Node() // No-arg constructor
  {
    next = NULL;
  }

  Node(T element) // Constructor
  {
    this->element = element;
    next = NULL;
  }
};

template<typename T>
class Queue
{
public:
  Queue();
  void enqueue(T element);
  T dequeue() throw (runtime_error);
  int getSize();
  T getHead();
 
private:
 Node<T> *head, *tail;
  int size;
};

template<typename T>
Queue<T>::Queue()
{
  head = tail = NULL;
  size = 0;
}

template<typename T>
void Queue<T>::enqueue(T element)
{
   if (tail == NULL)
  {
    head = tail = new Node<T>(element);
  }
  else
  {
    tail->next = new Node<T>(element);
    tail = tail->next;
  }

  size++;
}

template<typename T>
T Queue<T>::dequeue() throw (runtime_error)
{
   if (size == 0)
   throw runtime_error("No elements in the list");
  else
  {
    Node<T> *temp = head;
    head = head->next;
    size--;
    if (head == NULL) tail = NULL;
    T element = temp->element;
    delete temp;
    return element;
  }
}

template<typename T>
int Queue<T>::getSize()
{
  return size;
}
template<typename T>
T Queue<T>::getHead()
{
  return head->element;
}
#endif

 

#ifndef STACK_H
#define STACK_H
#include <iostream>
using namespace std;

template<typename T>
class Node2
{
public:
  T element;  // Element contained in the node
  Node2<T> *next; // Pointer to the next node

  Node2() // No-arg constructor
  {
    next = NULL;
  }

  Node2(T element) // Constructor
  {
    this->element = element;
    next = NULL;
  }
};

template<typename T>
class Stack
{
public:
  Stack();
  bool empty();
  T peek();
  T push(T value);
  T pop();
  int getSize();
  void print();
private:
 Node2<T> *head, *tail;
  int size;
};

template<typename T>
Stack<T>::Stack()
{
 head = tail = NULL;
  size = 0;
}

template<typename T>
bool Stack<T>::empty()
{
  return head == NULL;
}

template<typename T>
T Stack<T>::peek()
{
   if (size == 0)
    throw runtime_error("Index out of range");
  else
    return tail->element;
}

template<typename T>
T Stack<T>::push(T element)
{
  if (tail == NULL)
  {
    head = tail = new Node2<T>(element);
  }
  else
  {
    tail->next = new Node2<T>(element);
    tail = tail->next;
  }

  size++;
  return element;
}

template<typename T>
T Stack<T>::pop()
{
 if (size == 0)
    throw runtime_error("No elements in the list");
  else if (size == 1)
  {
    Node2<T> *temp = head;
    head = tail = NULL;
    size = 0;
    T element = temp->element;
    delete temp;
    return element;
  }
  else
  {
    Node2<T> *current = head;

    for (int i = 0; i < size - 2; i++)
      current = current->next;

    Node2<T> *temp = tail;
    tail = current;
    tail->next = NULL;
    size--;
    T element = temp->element;
    delete temp;
    return element;
  }
}

template<typename T>
int Stack<T>::getSize()
{
  return size;
}

template<typename T>
void Stack<T>::print()
{
  Node2<T> *point=head;
  while(point!=NULL){
  cout<<point->element<<" ";
  point=point->next;
  }
 cout<<endl;
}
#endif