嵌入式

编程与应用
posts - 14, comments - 1, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

 

#ifndef BINARY_TREE
#define BINARY_TREE
#include
<stack>
#include
<iostream>
using namespace std;
template
<class T> class BinaryTree;
template
<class T>
class BTNode
{
public:
    BTNode()
{lChild=rChild=NULL;}
    BTNode(
const T&x)
    
{
        element
=x;
        lChild
=rChild=NULL;
    }

    BTNode(
const T& x,BTNode<T>*l,BTNode<T>* r)
    
{
        element
=x;lChild=l;rChild=r;
    }

    friend 
class BinaryTree<T>;
private:
    T element;
    BTNode
<T>* lChild,*rChild;
    
static stack<BTNode<T>*> s;
}
;
template
<class T>
stack
<BTNode<T>*> BTNode<T>::s;

template
<class T>
class BinaryTree
{
public:
    BinaryTree()
{root=NULL;}
    
bool IsEmpty()const{return root==NULL}
    
void Clear();
    
bool Root(T& x)const;
    
void MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right);
    
void BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right);
    
void PreOrder();
protected:
    BTNode
<T>* root;
private:
    
void PreOrder(BTNode<T>*current);
}
;

#endif//BINARY_TREE

template
<class T>
bool BinaryTree<T>::Root(T &x)const
{
    
if(root){
        x
=root->element;return true;
    }

    
else return false;
}


template
<class T>
void BinaryTree<T>::MakeTree(const T& x,BinaryTree<T>& left,BinaryTree<T>& right)
{
    
if(root||&left==&right) return;
    root
=new BTNode<T>(x,left.root,right.root);
    left.root
=right.root=NULL;
}


template
<class T>
void BinaryTree<T>::BreakTree(T& x,BinaryTree<T>& left,BinaryTree<T>& right)
{
    
if(root||&left==&right||left.root==right.root) return;
    x
=root->element;
    left.root
=root->lChild;right.root=root->rChild;
    delete root;root
=NULL;//
}


template
<class T>
void BinaryTree<T>::PreOrder(BTNode<T>* current)
{
loop:
    
while(current){
        Visit(current
->element);
        
if(current->rChild)
            BTNode
<T>::s.push(current->rChild);
        current
=current->lChild;
    }

    current
=BTNode<T>::s.top();Visit(current->element);BTNode<T>::s.pop();
    
if(BTNode<T>::s.empty()) return;
    
else goto loop;
}


template
<class T>
void BinaryTree<T>::PreOrder()
{
    
if(root)
        PreOrder(root);
    
if(root->rChild)
        PreOrder(root
->rChild);
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理