首页 > 代码库 > 二叉树的层次遍历
二叉树的层次遍历
问题:
如何实现二叉树的层次遍历?
解析:
我们可以使用队列来解决这个问题
<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 #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> bool BSTrees<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> void BSTrees<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(); } #endif
#include <iostream> #include "BST.h" using namespace std; void main() { BSTrees<int>Bst; int Arr[9] = {6,2,8,4,10,0,12,16,14}; for (int i=0;i<9;i++) Bst.insert(Arr[i]); Bst.traverse(Bst.getRoot()); cout<<"Tree'slength is:"<<Bst.getLength()<<endl; Bst.traverseLevel(Bst.getRoot()); }
二叉树的层次遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。