首先二叉樹的節(jié)點定義如下：
struct BinaryNode
{

                 BinaryNode *_left;
                 BinaryNode *_right;
                 T _data;
                BinaryNode( T data ) :_data(data), _left( NULL), _right(NULL )
                {};
};

二叉樹的結(jié)構(gòu)以及接口如下
template<class T>
class BinaryTree
{
                 typedef BinaryNode <T> Node;
public:
                BinaryTree() :_head( NULL)
                {};
                BinaryTree( const T * a, size_t size, const T & valiue)
                ~BinaryTree()
                BinaryTree( BinaryTree &b )
                void PrevOder()
                 void InOder()
                 void PostOder()
private:
public:
                 void LevalOder()
                 size_t depth()
                 size_t size()
                 size_t learsize()
                 void _LevalOder(BinaryNode <T> *root);
                 size_t _depth(BinaryNode <T> *root);
                 void _size(BinaryNode <T> *root, int *p);
                 void _leafsize(BinaryNode <T> *root, size_t *p);
                 int Leafsize(BinaryNode <T> *root);
                 void PrevOder_Nor();
                 void InOder_Nor();
                 void PostOder_Nor();
                 void Distory(Node *_root)
                 Node* _Copy(Node *cur);
private:
                 BinaryNode<T > *_root;
};


二叉樹的建立（構(gòu)造函數(shù)）
                BinaryTree( const T * a, size_t size, const T & valiue)
                {
                                 size_t index = 0;
                                _root = _CreatTree( a, size , index, valiue);
                }
                 BinaryNode<T >* _CreatTree(const T* a, size_t size, size_t &index, const T &valiue)
                {
                                 BinaryNode<T > *root = NULL;
                                 if (index < size&& a[index ] != valiue)
                                {
                                                root = new BinaryNode <T>(a[index]);
                                                root->_left = _CreatTree(a, size , ++index, valiue);
                                                root->_right = _CreatTree(a, size , ++index, valiue);
                                }
                                 return root;
                }
二叉樹的銷毀（析構(gòu)函數(shù)）
                ~BinaryTree()
                {
                                Distory(_root);
                                cout << " ~BinaryTree()" << endl;
                }
                 void Distory(Node *_root)
                {
                                 if (_root == NULL)
                                                 return;
                                Distory( _root->_left);
                                Distory( _root->_right);
                                 if (_root )
                                                 delete _root ;
                                 _root == NULL ;

                }
二叉樹的拷貝(拷貝構(gòu)造)
                BinaryTree( BinaryTree &b )
                {
                                _root = _Copy( b._root);
                }
BinaryNode<T >* BinaryTree< T>::_Copy(Node *cur)
{
                 if (cur == NULL)
                                 return NULL ;
                 Node *tmp = new Node(cur->_data);
                tmp->_left=_Copy( cur->_left);
                tmp->_right=_Copy( cur->_right);
                 return tmp;

}
求葉子節(jié)點個數(shù)（兩種方法）
一：
int BinaryTree <T>::Leafsize( BinaryNode<T > *root)
{
                 int count;
                 if (root == NULL)
                                count = 0;
                 else if (root->_left == NULL&&root ->_right == NULL)
                {
                                count = 1;
                }
                 else  count = Leafsize(root ->_left) + Leafsize(root->_right);
                 return count;
}
二：
void BinaryTree <T>::_leafsize( BinaryNode<T > *root, size_t * p)
{
                 if (root != NULL)
                {
                                _leafsize( root->_left,p );
                                _leafsize( root->_right,p );
                                 if (root ->_left == NULL&& root->_right == NULL )
                                {
                                                ++ *p;
                                }

                }
}

二叉樹前序遍歷遞歸
                 void _PrevOder(BinaryNode <T> * root)
                {
                                 if (root == NULL)
                                                 return;
                                cout << root->_data << " " ;
                                _PrevOder( root->_left);
                                _PrevOder( root->_right);
                }
二叉樹前序遍歷非遞歸
void BinaryTree <T>::PrevOder_Nor()
{
                 BinaryNode<T > *cur = _root;
                 stack<BinaryNode <T>*> s;
                 if (cur == NULL )
                                 return;
                s.push(cur);
                 while (!s.empty())
                {
                                 BinaryNode<T > *tmp = s.top();
                                cout << tmp->_data << " ";
                                s.pop();
                                 if (tmp->_right)
                                {
                                                s.push(tmp->_right);
                                }
                                 if (tmp->_left)
                                {
                                                s.push(tmp->_left);
                                }
                }
                cout << endl;
                
}
二叉樹層序遍歷（隊列實現(xiàn)）
void BinaryTree <T>::_LevalOder( BinaryNode<T > *root)
{
                 deque<BinaryNode <T>*> q;
                q.push_back( root);
                 while (q.size())
                {
                                 BinaryNode<T > *pNode = q.front();
                                q.pop_front();
                                cout << pNode->_data << " ";
                                 if (pNode->_left)
                                {
                                                q.push_back(pNode->_left);
                                }
                                 if (pNode->_right)
                                {
                                                q.push_back(pNode->_right);
                                }
                }
                

}
二叉樹中序遍歷遞歸
                 void _InOder(BinaryNode <T> * root)
                {
                                 if (root == NULL)
                                                 return;
                                _InOder( root->_left);
                                cout << root->_data << " " ;
                                _InOder( root->_right);
                }
二叉樹中序遍歷非遞歸
void BinaryTree <T>::InOder_Nor()
{
                 if (_root == NULL )
                                 return;
                 Node *cur = _root;
                 stack<Node *> s;
                 while (cur||!s.empty())
                {
                                 while (cur)
                                {
                                                s.push(cur);
                                                cur = cur->_left;
                                }
                                 Node *tmp = s.top();
                                cout << tmp->_data << " ";
                                s.pop();
                                cur = tmp->_right;
                }
                cout << endl;

}
二叉樹后序遍歷遞歸
                 void  _PostOder(BinaryNode <T> * root)
                {
                                 if (root == NULL)
                                                 return;
                                _PostOder( root->_left);
                                _PostOder( root->_right);
                                cout << root->_data << " " ;
                }
二叉樹后序遍歷非遞歸
void BinaryTree <T>::PostOder_Nor()
{
                 if (_root == NULL )
                                 return;
                 Node *cur = _root;
                 stack<Node *> s;
                 Node *prev = NULL ;
                 while (cur||!s.empty())
                {
                                 while (cur)
                                {
                                                s.push(cur);
                                                cur = cur->_left;
                                }
                                 Node *tmp = s.top();
                                 if (tmp->_right == NULL || tmp->_right == prev)
                                {
                                                cout << tmp->_data << " " ;
                                                s.pop();
                                                prev = tmp;
                                }
                                 else
                                {
                                                cur = tmp->_right;
                                }
                }
                cout << endl;
                
}
二叉樹的深度
size_t BinaryTree <T>::_depth( BinaryNode<T > *root)
{
                 int hleft;
                 int hright;
                 int max;
                 if (root )
                {
                                hleft = _depth( root->_left);
                                hright = _depth( root->_right);
                                max = hleft > hright ? hleft : hright;
                                 return max + 1;

                }
                 else
                {
                                 return 0;
                }
}
二叉樹的大小
                 size_t size()
                {
                                 int count = 0;
                                _size(_root,&count);
                                 return count;
                }
void BinaryTree <T>::_size( BinaryNode<T > *root,int *p)
{
                 if (root )
                {
                                ++(* p);
                                _size( root->_left, p );
                                _size( root->_right, p );
                }
                 return ;
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。

創(chuàng)新互聯(lián)建站成立以來不斷整合自身及行業(yè)資源、不斷突破觀念以使企業(yè)策略得到完善和成熟，建立了一套“以技術(shù)為基點，以客戶需求中心、市場為導(dǎo)向”的快速反應(yīng)體系。對公司的主營項目，如中高端企業(yè)網(wǎng)站企劃 / 設(shè)計、行業(yè) / 企業(yè)門戶設(shè)計推廣、行業(yè)門戶平臺運營、成都App定制開發(fā)、成都做手機網(wǎng)站、微信網(wǎng)站制作、軟件開發(fā)、BGP機房服務(wù)器托管等實行標準化操作，讓客戶可以直觀的預(yù)知到從創(chuàng)新互聯(lián)建站可以獲得的服務(wù)效果。

當前題目：數(shù)據(jù)結(jié)構(gòu)之二叉樹（構(gòu)造拷貝構(gòu)造以及前序中序后續(xù)三種遍歷方法）-創(chuàng)新互聯(lián)
標題鏈接：http://aaarwkj.com/article34/dpgsse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、品牌網(wǎng)站制作、網(wǎng)站設(shè)計、自適應(yīng)網(wǎng)站、關(guān)鍵詞優(yōu)化、品牌網(wǎng)站設(shè)計

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)