【算法】二叉树的层次遍历
问题：如何实现二叉树的层次遍历？
解析：
我们可以使用队列来解决这个问题
<1>将根节点压入队列
<2>判断队列是否为空
<3>不为空则获取队列最前端的元素，打印出该元素
<4>将该元素移除队列
<5>如果该元素有左孩子，则将其左孩子进入队列
<6>如果该元素有右孩子，则将其右孩子进入队列
主要函数如下所示：template<typename Type> void BSTrees<Type>::traverseLevel(Node* root)
{
if( root == NULL)
{
cout<<"This is a empty tree"<<endl;
return;
}
queue<Node*> que;
que.push(root);
while( !que.empty() )
{
Node* ptr = que.front();
que.pop();
cout<<ptr->e<<endl;
if(ptr->leftChild != NULL)
que.push(ptr->leftChild);
if(ptr->rightChild != NULL)
que.push(ptr->rightChild);
}
}整个程序如下所示：
BSTrees.h
//BSTrees.h
#ifndef DDXX_BSTREES_H
#define DDXX_BSTREES_H
#include <iostream>
#include <queue>
using namespace std;
template<typename Type>
class BSTrees
{
public:
BSTrees();
~BSTrees();
public:
struct Node
{
Type e;
Node* leftChild;
Node* rightChild;
Node()
{
}
Node(Type _e)
{
e = _e;
leftChild = NULL;
rightChild= NULL;
}
};
public:
bool insert(Type e);
bool erase1(Type e);
bool erase2(Type e);
void clear();
bool isEmpty();
int getLength();
Node* find(Type e);
Node* getRoot();
Node* getParent(Node* p);
void traverse(Node* ptr);
void traverseLevel(Node* ptr);
private:
void clears(Node* &p);
private:
Node* m_root;
int m_Length;
};
template<typename Type> BSTrees<Type>::BSTrees()
{
m_root = NULL;
m_Length = 0;
}
template<typename Type> bool BSTrees<Type>::insert(Type e)
{
Node* ptr = new Node(e);
if ( ptr == NULL )
{
cout<<"Allocate memory for the element failed"<<endl;
return false;
}
if( m_root == NULL)
{
m_root = ptr;
m_Length++;
return true;
}
Node* p = m_root;
Node* pParent = m_root;
while( p != NULL)
{
if( e == p->e)
{
cout<<"the element is already exist"<<endl;
delete ptr;
ptr = NULL;
return false;
}
pParent = p;
if( e > p->e)
{
p = p->rightChild;
}
else
{
p = p->leftChild;
}
}
if( e < pParent->e )
{
pParent->leftChild = ptr;
}
if( e > pParent->e)
{
pParent->rightChild = ptr;
}
m_Length++;
return true;
}
template<typename Type> bool BSTrees<Type>::erase1(Type e)
{
Node *p = find(e);
if ( p == NULL )
{
cout<<"There's no this element to delete"<<endl;
return false;
}
if ( p->leftChild == NULL)
{
Node* pParent = getParent(p);
if( pParent->leftChild == p )
pParent->leftChild = p->rightChild;
else
pParent->rightChild = p->rightChild;
delete p;
p = NULL;
m_Length--;
return true;
}
if ( p->rightChild == NULL)
{
Node* pParent = getParent(p);
if( pParent->leftChild == p)
pParent->leftChild = p->leftChild;
else
pParent->rightChild = p->leftChild;
delete p;
p = NULL;
m_Length--;
return true;
}
if ( p->leftChild != NULL && p->rightChild != NULL)
{
Node* pParent = getParent(p);
Node* pPre = p->leftChild;
Node* ptmp = pPre;
while( pPre->rightChild != NULL )
{
ptmp = pPre;
pPre = pPre->rightChild;
}
if( ptmp != pPre)
{ ptmp->rightChild = pPre->leftChild;
pPre->leftChild = p->leftChild;
pPre->rightChild = p->rightChild;
}
else
pPre->rightChild = p->rightChild;
if( pParent == NULL )
m_root = pPre;
else
if( pParent->leftChild == p)
pParent->leftChild = pPre;
else
pParent->rightChild = pPre;
delete p;
p = NULL;
m_Length--;
return true;
}
}
template<typename Type> boolBSTrees<Type>::erase2(Type e)
{
Node *p = find(e);
if ( p == NULL )
{
cout<<"There's no this element to delete"<<endl;
return false;
}
if ( p->leftChild == NULL)
{
Node* pParent = getParent(p);
if( pParent->leftChild == p )
pParent->leftChild = p->rightChild;
else
pParent->rightChild = p->rightChild;
delete p;
p = NULL;
m_Length--;
return true;
}
if ( p->rightChild == NULL)
{
Node* pParent = getParent(p);
if( pParent->leftChild == p)
pParent->leftChild = p->leftChild;
else
pParent->rightChild = p->leftChild;
delete p;
p = NULL;
m_Length--;
return true;
}
if( p->leftChild != NULL && p->rightChild != NULL)
{
Node* pParent = getParent(p);
Node* ptr = p->leftChild;
while( ptr->rightChild != NULL )
ptr = ptr->rightChild;
ptr->rightChild = p->rightChild;
if( pParent == NULL )
m_root = p->leftChild;
else
if(pParent->leftChild == p)
pParent->leftChild = p->leftChild;
else
pParent->rightChild = p->leftChild;
delete p;
p = NULL;
m_Length--;
return true;
}
}
template<typename Type> voidBSTrees<Type>::clear()
{
if( m_root == NULL )
return;
clears(m_root);
m_root = NULL;
}
template<typename Type> void BSTrees<Type>::clears(Node* &p)
{
if(p->leftChild != NULL)
{
clears(p->leftChild);
p->leftChild = NULL;
}
if(p->rightChild != NULL)
{
clears(p->rightChild);
p->rightChild = NULL;
}
delete p;
p = NULL;
m_Length--;
}
template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::getRoot()
{
return m_root;
}
template<typename Type> int BSTrees<Type>::getLength()
{
return m_Length;
}
template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::getParent(Node* p)
{
if( p == m_root)
return NULL;
Node* ptr = m_root;
Node* ptf = ptr;
while( ptr != NULL )
{
if ( ptr->e == p->e )
return ptf;
if ( ptr->e > p->e )
{
ptf = ptr;
ptr = ptr->leftChild;
}
else
{
ptf = ptr;
ptr = ptr->rightChild;
}
}
}
template<typename Type> typename BSTrees<Type>::Node* BSTrees<Type>::find(Type e)
{
Node* ptr = m_root;
while(ptr != NULL)
{
if ( ptr->e == e )
return ptr;
if ( ptr->e > e )
ptr = ptr->leftChild;
else
ptr = ptr->rightChild;
}
//if ( ptr == NULL )
return NULL;
}
template<typename Type> void BSTrees<Type>::traverse(Node* ptr)
{
if( ptr == NULL )
return;
if( ptr->leftChild != NULL )
traverse(ptr->leftChild);
cout<<"Element value:"<<ptr->e<<endl;
if( ptr->rightChild != NULL )
traverse(ptr->rightChild);
}
template<typename Type> void BSTrees<Type>::traverseLevel(Node* root)
{
if( root == NULL)
{
cout<<"This is a empty tree"<<endl;
return;
}
queue<Node*> que;
que.push(root);
while( !que.empty() )
{
Node* ptr = que.front();
que.pop();
cout<<ptr->e<<endl;
if(ptr->leftChild != NULL)
que.push(ptr->leftChild);
if(ptr->rightChild != NULL)
que.push(ptr->rightChild);
}
}
template<typename Type> BSTrees<Type>::~BSTrees()
{
clear();
}
#endifmain.cpp
//main.cpp
#include <iostream>
#include "BST.h"
using namespace std;
void main()
{
BSTrees<int>Bst;
int Arr = {6,2,8,4,10,0,12,16,14};
for (int i=0;i<9;i++)
Bst.insert(Arr);
Bst.traverse(Bst.getRoot());
cout<<"Tree'slength is:"<<Bst.getLength()<<endl;
Bst.traverseLevel(Bst.getRoot());
}
页:
[1]