二叉樹常考面試題-創(chuàng)新互聯(lián)

• 樹相關(guān)的一些概念。

  

  目前成都創(chuàng)新互聯(lián)已為上千的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)絡(luò)空間、網(wǎng)站托管、服務(wù)器租用、企業(yè)網(wǎng)站設(shè)計、洪湖網(wǎng)站維護(hù)等服務(wù)，公司將堅持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長，共同發(fā)展。

樹是n（n>=0）個有限個數(shù)據(jù)的元素集合，形狀像一顆倒過來的樹。

結(jié)點：結(jié)點包含數(shù)據(jù)和指向其它結(jié)點的指針。

結(jié)點的度：結(jié)點擁有的子節(jié)點個數(shù)。

葉子節(jié)點：沒有子節(jié)點的節(jié)點(度為0)。

父子節(jié)點：一個節(jié)點father指向另一個節(jié)點child，則child為孩子節(jié)點，father為父親結(jié)點。

兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互為兄弟節(jié)點。

節(jié)點的祖先：從根節(jié)點開始到該節(jié)點所經(jīng)的所有節(jié)點都可以稱為該節(jié)點的祖先。

子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫。

樹的高度：樹中距離根節(jié)點最遠(yuǎn)結(jié)點的路徑長度。

樹的存儲結(jié)構(gòu)：

• 二叉樹的結(jié)構(gòu)

二叉樹:二叉樹是一棵特殊的樹，二叉樹每個節(jié)點最多有兩個孩子結(jié)點，分別稱為左孩子和右孩子。

滿二叉樹:高度為N的滿二叉樹有2^N - 1個節(jié)點的二叉樹。

完全二叉樹 若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹

前序遍歷(先根遍歷):

（1）：先訪問根節(jié)點；

（2）：前序訪問左子樹；

（3）：前序訪問右子樹；

中序遍歷:

（1）：中序訪問左子樹

（2）：訪問根節(jié)點；

（3）：中序訪問右子樹；

后序遍歷(后根遍歷):

（1）：后序訪問左子樹；

（2）：后序訪問右子樹；

（3）：訪問根節(jié)點；

層序遍歷：

（1）：一層層節(jié)點依次遍歷。

下面是二叉樹的具體實現(xiàn)：

template<class T>

struct BinaryTreeNode

{

          BinaryTreeNode<T > *_left;

          BinaryTreeNode<T > *_right;

          T _data;

};

template<class T>

class BinaryTree

{

          Typedef BinaryTreeNode< T> Node;

protected:

          Node *_root;

public:

          BinaryTree() //無參構(gòu)造函數(shù)

                   :_root( NULL)

          {

          }

          BinaryTree( const T *a, size_t size, const T& invalid)

          {

                   size_t index = 0;

                   _root = _CreateTree( a, size , invalid, index);

          }

protected:

          Node *__CreateTree( const T *a, size_t size, const T& invalid, size_t &index )

          {

                   Node *root = NULL;

                   if (index < size && a[index ] != invalid) //是有效值時

                   {

                             root = new Node(a [index]);

                             root->_left = __CreateTree( a, size , invalid, ++ index);

                             root->_right = __CreateTree( a, size , invalid, ++index);

          }

                   return root;

          }

//前序遍歷--------遞歸寫法，缺點是：有大量的壓棧開銷。

          void Prevorder(Node *root )

          {

                   if (root == NULL)

                   {

                             return;

                   }

                   else

                   {

                             cout << root->_data << " " ;

                             _prevorder( root->_left);

                             _prevorder( root->_right);

                   }

          }

//前序遍歷------------非遞歸寫法

//前序遍歷的非遞歸寫法思想：需要借助棧。

          void PrevOrderRonR()

          {

                   stack<Node*> s;

                   if (_root == NULL )//根結(jié)點為空的話直接return掉即可。

                   {

                             return;

                   }

                   if (_root)

                   {

                             s.push(_root); //根不為空的時候?qū)⒏Y(jié)點進(jìn)行壓棧。

                   }

                   while (!s.empty())//判斷棧是否為空

                   {

                             Node *top = s.top(); //棧不為空，則取棧頂元素

                             cout << top->_data << " ";//然后進(jìn)行訪問棧頂元素

                             s.pop(); //訪問完棧頂元素將其從棧中pop掉。

                             if (top->_right)//要根據(jù)棧進(jìn)行先序遍歷，則必須是先訪問根節(jié)點，再訪問左子樹，最后訪問右子樹，因為棧是“后進(jìn)先出的”，要想先訪問左子樹，則必須先入右子樹，再入左子樹。如果棧頂元素的右子樹不為空，

                             {

                                      s.push(top->_right); //棧頂?shù)挠易訕洳粸榭眨瑢⑵溥M(jìn)行壓棧。

                             }

                             if (top->_left)

                             {

                                      s.push(top->_left); //棧頂?shù)淖笞訕洳粸榭眨瑢⑵溥M(jìn)行壓棧。

                             }

                   }

                   cout << endl;

          }

//中序遍歷----------遞歸寫法

          void _Inorder(Node *root )

          {

                   if (root == NULL)

                   {

                             return;

                   }

                   else

                   {

                             _Inorder(Node * root)

                             {

                                      if (root == NULL )

                                      {

                                                return;

                                      }

                                      else

                                      {

                                                _Inorder(root->_left);

                                                cout << root->_data << " " ;

                                                Inorder(root->_right);

                                      }

                             }

                   }

          }

//中序遍歷的非遞歸寫法，思想是：也是借助棧，主要核心是找最左結(jié)點，定義一個cur指針，讓它最開始指向_root。

          void TnOrderNonR()

          {

                   stack<Node*> s;

                   Node *cur = _root;

                   while (cur || !s.empty())

                   {

                             whie(cur) //找最左結(jié)點

                             {

                                      s.push(cur); //將cur壓棧。

                                      cur = cur->_left; //cur指向它的左孩子

                             }

                             Node *top = s.top();

                             cout << top->_data << " ";

                             s.pop();

                             cur = top->_right;

                   }

          }

//后序遍歷---------遞歸寫法

          void Postorder(Node *root )

          {

                   if (root == NULL)

                   {

                             return;

                   }

                   else

                   {

                             Postorder( root->_left);

                             Postorder( root->_right);

                             cout << root->_data << " " ;

                   }

          }

//后序遍歷----------非遞歸寫法，思想是：先找最左結(jié)點，找到后但不能訪問最左結(jié)點，要先判斷最左結(jié)點的右子樹是否為空，若為空， 則可以訪問最左結(jié)點，否則不可以訪問最左結(jié)點，需要訪問右子樹。

//可以訪問根結(jié)點的條件：上一層訪問的節(jié)點為右子樹。所以我們需要定義兩個指針prev與cur ，cur用來保存當(dāng)前結(jié)點，prev用來保存上一層訪問的結(jié)點。

          void PostOrderNonR()

          {

                   stack<Node*> s;

                   Node *prev = NULL;

                   Node *cur = _root;

                   while (cur || !s.empty())

                   {

                             while (cur)//找最左結(jié)點

                             {

                                      s.push(cur);

                                      cur = cur->_left;

                             }

                             Node *top = s.top(); //定義一個棧頂指針，用來指向棧頂元素。

                             if (top->_right == NULL || top->_right == prev)//棧頂節(jié)點的右子樹為空或者上一次訪問的節(jié)點為右子樹，則可以訪問棧頂元素。

                             {

                                      cout << top->_data << " " ;

                                      s.pop();

                                      prev = top;

                             }

                             else

                             {

                                      cur = top->_left;

                             }

                   }

          }

//二叉樹的層序遍歷（即是一層一層的進(jìn)行遍歷）：思想是：需要借助隊列，首先取隊頭，判斷它是否為空，若為空直接return；不為空的時候，進(jìn)行入隊操作。

//如何取到隊頭？入數(shù)據(jù)還是入指針？最好入指針，需要保存數(shù)據(jù)或者節(jié)點的時候最好入指針。

          void LevelOrder()

          {

                   queue<Node*> q;

                   if (_root == NULL )

                   {

                             return;

                   }

                   q.push(_root);

                   while (!q.empty())

                   {

                             Node *front = q.front(); //取隊頭元素

                             q.pop();

                             cout << front->_data<< " ";

                             if (front->_left)//隊頭元素的左孩子不為空的時候，將它的左孩子壓入隊列

                             {

                                      q.push(front->_left);

                             }

                             if (front->_right)//隊頭元素的右孩子不為空的時候，將它的右孩子壓入隊列

                             {

                                      q.push(front->_right);

                             }

                   }

          }

          size_t _Depth(Node *root )//思想：當(dāng)前深度=（左子樹和右子樹中深度較大的一個）+1；

          {

                   if（root == NULL）

                   {

                 return 0；

             }

                   int left = _Depth(root->_left);

                   int right = _Depth(root ->_right);

                   return left > right ? left + 1 : right + 1;

          }

          size_t _GetKLevel(Node *root , size_t K)//取第K層結(jié)點,遞歸寫法。

          {

                   if (root == NULL)

                   {

                             return 0;

                   }

                   if (K == 1)

                   {

                             return 1;

                   }

                   return _GetKLevel(root ->_left, K - 1) + _GetKLevel(root->_right, K - 1);

          }

          Node* _Find(Node * root, const T& x)//查找結(jié)點為x的結(jié)點

          {

                   if (root == NULL)

                   {

                             return NULL ;

                   }

                   if (root ->_data == x)

                   {

                             return root ;

                   }

                   Node *ret = _Find( root->_left, x );

                   if (ret)

                   {

                             return ret;

                   }

                   else

                   {

                             return _Find(root ->_right, x);

                   }

          }

          size_t _leafsize(Node *root )//求葉子節(jié)點的個數(shù),思想：左子樹的葉子結(jié)點數(shù)目+右子樹的葉子結(jié)點的數(shù)目。

          {

                   if (root == NULL)

                   {

                             return 0;

                   }

                   if (root ->_left == NULL&& root->_right == NULL )

                   {

                             return 1;

                   }

                   return _leafsize(root ->_left) + _leafsize(root->_right);

          }

          //遞歸即是=子問題+返回條件

          //方法一：

          size_t _size(Node *root )//結(jié)點的數(shù)目

          {

                   if (root == NULL)

                   {

                             return 0;

                   }

                   return _size(root ->_left) + _size(root->_right) + 1;

          }

          //方法二：遍歷法

          size_t _size(Node *root)

          {

                   static size_t sSize = 0;//此句代碼會讓程序有線程安全問題

                   if (root == NULL )

                   {

                             return sSize;

                   }

                   ++sSize;

                   _size(root->_left);

                   _size(root->_right);

                   return sSize;６

          }

};

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

本文標(biāo)題：二叉樹常考面試題-創(chuàng)新互聯(lián)
當(dāng)前地址：http://muchs.cn/article46/dddgeg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計、移動網(wǎng)站建設(shè)、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、企業(yè)建站、用戶體驗

廣告

聲明：本網(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)