이 진 트 리 에 대한 간단 한 실현
17690 단어 데이터 구조
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode< T>(const T& x)
:_data( x)
,_left( NULL)
,_right( NULL)
{}
T _data;
BinaryTreeNode<T >* _left;
BinaryTreeNode<T >* _right;
};
template<class T>
class BinaryTree
{
public:
BinaryTree< T>() //
:_root( NULL)
{}
BinaryTree< T>(const T* a,size_t size)
{
size_t index=0;
_root=_CreateTree( a,index,size );
}
~BinaryTree< T>() //
{
Clear();
_root= NULL;
cout<< "~BinaryTree<T>()" <<endl; //
}
BinaryTree< T>(const BinaryTree& bt) //
{
_root=_Copy( bt._root);
}
//BinaryTree<T>& operator=(const BinaryTree& bt) //
//{
// if(this!=&bt)
// {
// this->Clear();
// _root=_Copy(bt._root);
// }
// cout<<"BinaryTree<T> operator=()"<<endl;
// return *this;
//}
BinaryTree<T >& operator=(BinaryTree< T> bt ) // ， swap()
{
swap(_root, bt._root);
return *this ;
}
void PreOrder() // ―― （ ）， ： ， ，
{
_PreOrder(_root);
cout<<endl;
}
void InOrder() // ―― ， ： ， ，
{
_InOrder(_root);
cout<<endl;
}
void PostOrder() // ―― ， ： ， ，
{
_PostOrder(_root);
cout<<endl;
}
void LevelOrder() // ―― ， ：
{
_LevelOrder(_root);
cout<<endl;
}
void PreOrder_Non_R() // ―― （ ）， ： ， ，
{
_PreOrder_Non_R(_root);
cout<<endl;
}
void InOrder_Non_R() // ―― ， ： ， ，
{
_InOrder_Non_R(_root);
cout<<endl;
}
void PostOrder_Non_R() // ―― ， ： ， ，
{
_PostOrder_Non_R(_root);
cout<<endl;
}
void Clear()
{
_Clear(_root);
}
int Size() //
{
return _Size(_root);
}
int Hight() //
{
return _Hight(_root);
}
int LeafNum()
{
return _LeafNum(_root);
}
BinaryTreeNode<T >* Find(const T& x)
{
return _Find(_root,x );
}
protected:
BinaryTreeNode<T >* _CreateTree(const T* a,size_t& index,size_t size) // （ ），
{
BinaryTreeNode<T >* root=NULL;
if((index <size)&&( a[index ]!='#'))
{
root= new BinaryTreeNode <T>(a[index]);
root->_left=_CreateTree( a,++index ,size);
root->_right=_CreateTree( a,++index ,size);
}
return root;
}
void _PreOrder(BinaryTreeNode <T>* root) // （ ） ， ： ， ，
{
if(root ==NULL)
return;
cout<< root->_data<<" " ;
_PreOrder( root->_left);
_PreOrder( root->_right);
}
void _InOrder(BinaryTreeNode <T>* root) // （ ） ， ： ， ，
{
if(root ==NULL)
return;
_InOrder( root->_left);
cout<< root->_data<<" " ;
_InOrder( root->_right);
}
void _PostOrder(BinaryTreeNode <T>* root) // （ ） ， ： ， ，
{
if(root ==NULL)
return;
_PostOrder( root->_left);
_PostOrder( root->_right);
cout<< root->_data<<" " ;
}
//void _LevelOrder(BinaryTreeNode<T>* root) // ， ： （ ， Queue, ）
//{
// queue<BinaryTreeNode<T>*> q; // ，
// q.push(root); //
// while(root)
// {
// cout<<root->_data<<" "; //
// if(!q.empty())
// {
// BinaryTreeNode<T>* cur=q.front(); //
// q.pop(); //
// q.push(cur->_left); //
// q.push(cur->_right); //
// root=q.front();
// }
// }
//}
void _LevelOrder(BinaryTreeNode <T>* root) // ， ： （ ， Queue, ）
{
queue<BinaryTreeNode <T>*> q;
if(root )
q.push( root);
while(!q.empty())
{
BinaryTreeNode<T >* front=q.front();
cout<<front->_data<< " ";
q.pop();
if(front->_left)
q.push(front->_left);
if(front->_right)
q.push(front->_right);
}
}
int _Size(BinaryTreeNode <T>* root) //
{
if(root ==NULL)
return 0;
return _Size(root ->_left)+_Size(root->_right)+1; // + +
}
int _Hight(BinaryTreeNode <T>* root) //
{
if(root ==NULL)
return 0;
int LeftHight=_Hight(root ->_left);
int RightHight=_Hight(root ->_right);
return (LeftHight>RightHight)?(LeftHight+1):(RightHight+1); //
}
int _LeafNum(BinaryTreeNode <T>* root) //
{
if(root ==NULL)
return 0;
if((root ->_left==NULL)&&( root->_right==NULL )) // ，
return 1;
return _LeafNum(root ->_left)+_LeafNum(root->_right);
}
void _Clear(BinaryTreeNode <T>* root) // ( )
{
if(root !=NULL)
{
_Clear( root->_left);
_Clear( root->_right);
delete(root );
}
}
BinaryTreeNode<T >* _Copy(BinaryTreeNode< T>* root ) //
{
if(root ==NULL)
return NULL ;
BinaryTreeNode<T >* newRoot;
BinaryTreeNode<T >* cur=root;
if(cur!=NULL )
{
newRoot= new BinaryTreeNode <T>(cur->_data);
newRoot->_left=_Copy(cur->_left);
newRoot->_right=_Copy(cur->_right);
}
return newRoot;
}
void _PreOrder_Non_R(BinaryTreeNode <T>* root) // （ ） ， ： ， ， , stack
{
stack<BinaryTreeNode <T>*> s;
if(root )
s.push( root);
while(!s.empty())
{
BinaryTreeNode<T >* top=s.top(); //
cout<<top->_data<< " "; //
s.pop(); //
if(top->_right) // ， ， ， ，
s.push(top->_right); // ， ， ,
if(top->_left)
s.push(top->_left);
}
}
void _InOrder_Non_R(BinaryTreeNode <T>* root) // （ ） ， ： ， ，
{
stack<BinaryTreeNode <T>*> s;
BinaryTreeNode<T >* cur=root;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left; //
}
if(!s.empty())
{
BinaryTreeNode<T >* top=s.top(); //
cout<<top->_data<< " "; //
s.pop();
cur=top->_right; //
}
}
}
void _PostOrder_Non_R(BinaryTreeNode <T>* root) // （ ） ， ： ， ，
{
stack<BinaryTreeNode <T>*> s;
BinaryTreeNode<T >* cur=root;
BinaryTreeNode<T >* prevVisited=NULL;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left;
}
BinaryTreeNode<T >* top=s.top();
if(top->_right==NULL ||top->_right==prevVisited)
{
cout<<top->_data<< " ";
prevVisited=top;
s.pop();
}
else
cur=top->_right;
}
}
BinaryTreeNode<T >* _Find(BinaryTreeNode< T>* root ,const T& x) //
{
if(root ==NULL)
return NULL ;
if(root ->_data==x)
return root ;
BinaryTreeNode<T >* lRet=_Find(root->_left, x);
if(lRet)
return lRet;
return _Find(root ->_right,x);
}
protected:
BinaryTreeNode<T >* _root;
};
void test()
{
int array[10]={1,2,3,'#' ,'#',4,'#','#',5,6};
//BinaryTree<int> t1;
BinaryTree<int > t2(array,10);
//t2.PreOrder(); //1, 2, 3, 4, 5, 6
//t2.InOrder(); //3, 2, 4, 1, 6, 5
//t2.PostOrder(); //3, 4, 2, 6, 5, 1
//t2.LevelOrder(); //1, 2, 5, 3, 4, 6
//cout<<t2.Size()<<endl;
//cout<<t2.Hight()<<endl;
//cout<<t2.LeafNum()<<endl;
//BinaryTree<int> t3(t2); //
//t3.PreOrder();
//t3.InOrder();
//t3.PostOrder();
//t3.LevelOrder();
//cout<<t3.Size()<<endl;
//cout<<t3.Hight()<<endl;
//cout<<t3.LeafNum()<<endl;
//BinaryTree<int> t4; //
//t4=t2;
//t4.PreOrder();
//t4.InOrder();
//t4.PostOrder();
//t4.LevelOrder();
//cout<<t4.Size()<<endl;
//cout<<t4.Hight()<<endl;
//cout<<t4.LeafNum()<<endl;
//t2.PreOrder_Non_R();
//t2.InOrder_Non_R();
//t2.PostOrder_Non_R();
BinaryTreeNode<int >* ret=t2.Find(4);
}
int main()
{
test();
system( "pause");
return 0;
}차원 적 사고: (재 귀적 이지 않 고 대열 의 선진 적 인 선 출 원칙 을 이용)
우선, 이 진 트 리 뿌리 노드 를 방문 하여 대열 에 합류 합 니 다.
그 다음 에 대기 열 이 비어 있 지 않 을 때 다음 작업 을 반복 합 니 다.
1. 대기 열 에서 노드 하나 꺼 내기
2. 좌우 노드 를 대기 열 에 눌 러 줍 니 다.
본 고 는 '내 면 의 소 리 를 찾 아 라' 블 로그 에서 나 온 것 으로 작가 에 게 연락 하 세 요!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
