树的建立、深度及路径

#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