亚洲乱码中文字幕综合,中国熟女仑乱hd,亚洲精品乱拍国产一区二区三区,一本大道卡一卡二卡三乱码全集资源,又粗又黄又硬又爽的免费视频

C++實現(xiàn)二叉樹基本操作詳解

 更新時間：2017年12月06日 11:30:34   作者：tttjp  
這篇文章主要為大家詳細介紹了C++實現(xiàn)二叉樹基本操作，具有一定的參考價值，感興趣的小伙伴們可以參考一下

樹是一種重要的非線性數(shù)據(jù)結(jié)構(gòu)，二叉樹是樹型結(jié)構(gòu)的一種重要類型。本學(xué)年論文介紹了二叉樹的定義，二叉樹的存儲結(jié)構(gòu)，二叉樹的相關(guān)術(shù)語，以此引入二叉樹這一概念，為展開二叉樹的基本操作做好理論鋪墊。二叉樹的基本操作主要包含以下幾個模塊：二叉樹的遍歷方法，計算二叉樹的結(jié)點個數(shù)，計算二叉樹的葉子結(jié)點個數(shù)，二叉樹深度的求解等內(nèi)容。

前序遍歷（遞歸&非遞歸）

  • 訪問根節(jié)點
  • 前序訪問左子樹
  • 前序訪問右子樹
//前序非遞歸
  void PrevOrder()
  {
    stack<Node*> s;
    Node *cur = _root;

    while (cur || !s.empty())
    {
      while (cur)
      {
        cout << cur->_data << " ";
        s.push(cur);
        cur = cur->_left;
      }
      //此時當(dāng)前節(jié)點的左子樹已遍歷完畢
      Node *tmp = s.top();
      s.pop();
      cur = tmp->_right;
    }
    cout << endl;
  }

  //前序遞歸
  void PrevOrderR()
  {
    _PrevOrder(_root);

    cout << endl;
  }

  void _PrevOrder(Node *root)
  {
    if (root == NULL) //必須有遞歸出口?。?！
      return;

    cout << root->_data << " ";
    _PrevOrder(root->_left);
    _PrevOrder(root->_right);
  }

中序遍歷（遞歸&非遞歸）

  • 中序訪問左子樹
  • 訪問根節(jié)點
  • 中序訪問右子樹
//中序非遞歸
  void InOrder()
  {
    stack<Node*> s;
    Node *cur = _root;

    while (cur || !s.empty())
    {
      while (cur)
      {
        s.push(cur);
        cur = cur->_left;
      }
      //此時當(dāng)前節(jié)點的左子樹已遍歷完畢
      Node *tmp = s.top();
      cout << tmp->_data << " ";
      s.pop();
      cur = tmp->_right;
    }
    cout << endl;
  }

  //中序遞歸
  void InOrderR()
  {
    _InOrder(_root);

    cout << endl;
  }

  void _InOrder(Node *root)
  {
    if (root == NULL)
      return;

    _InOrder(root->_left);
    cout << root->_data << " ";
    _InOrder(root->_right);
  }

后序遍歷（遞歸&非遞歸）

  //后序非遞歸
  //后序遍歷可能會出現(xiàn)死循環(huán)，所以要記錄下前一個訪問的節(jié)點
  void PostOrder()
  {
    stack<Node*> s;
    Node *cur = _root;
    Node *prev = NULL;

    while (cur || !s.empty())
    {
      while (cur)
      {
        s.push(cur);
        cur = cur->_left;
      }
      Node *tmp = s.top();
      if (tmp->_right && tmp->_right != prev)
      {
        cur = tmp->_right;
      }
      else
      {
        cout << tmp->_data << " ";
        prev = tmp;
        s.pop();
      }
    }
    cout << endl;
  }

  //后序遞歸
  void PostOrderR()
  {
    _PostOrder(_root);

    cout << endl;
  }

  void _PostOrder(Node *root)
  {
    if (root == NULL)
      return;

    _PostOrder(root->_left);
    _PostOrder(root->_right);
    cout << root->_data << " ";
  }

層序遍歷

從根節(jié)點開始，依次訪問每層結(jié)點。
利用隊列先進先出的特性，把每層結(jié)點從左至右依次放入隊列。

 void LevelOrder() //利用隊列?。?！
  {
    queue<Node*> q;
    Node *front = NULL;

    //1.push根節(jié)點
    if (_root)  
    {
      q.push(_root);
    }
    //2.遍歷當(dāng)前節(jié)點，push當(dāng)前節(jié)點的左右孩子，pop當(dāng)前節(jié)點
    //3.遍歷當(dāng)前節(jié)點的左孩子，再遍歷右孩子，循環(huán)直至隊列為空
    while (!q.empty())
    {

      front = q.front();
      cout << front->_data << " ";

      if (front->_left)
        q.push(front->_left);
      if (front->_right)
        q.push(front->_right);

      q.pop();
    }

    cout << endl;
  }

求二叉樹的高度

  size_t Depth()
  {
    return _Depth(_root);
  }

  size_t _Depth(Node *root)
  {
    if (root == NULL)
      return 0;
    else if (root->_left == NULL && root->_right == NULL)
      return 1;
    else
    {
      size_t leftDepth = _Depth(root->_left) + 1;
      size_t rightDepth = _Depth(root->_right) + 1;
      return leftDepth > rightDepth ? leftDepth : rightDepth;
    }
  }

求葉子節(jié)點的個數(shù)

size_t LeafSize()
  {
    return _LeafSize(_root);
  }

  size_t _LeafSize(Node *root)
  {
    if (root == NULL)
      return 0;
    else if (root->_left == NULL && root->_right == NULL)
      return 1;
    else
      return _LeafSize(root->_left) + _LeafSize(root->_right);
  }

求二叉樹第k層的節(jié)點個數(shù)

size_t GetKLevel(int k)
  {
    return _GetKLevel(_root, k);
  }

  size_t _GetKLevel(Node *root, int k)
  {
    if (root == NULL)
      return 0;
    else if (k == 1)
      return 1;
    else
      return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
  }

完整代碼如下：

template<class T>
struct BinaryTreeNode
{
  T _data;
  BinaryTreeNode *_left;
  BinaryTreeNode *_right;

  BinaryTreeNode(const T& d)
    :_data(d)
    , _left(NULL)
    , _right(NULL)
  {}
};

template<class T>
class BinaryTree
{
public:
  typedef BinaryTreeNode<T> Node;

  BinaryTree()
    :_root(NULL)
  {}

  BinaryTree(T *arr, size_t n, const T& invalid)
  {
    size_t index = 0;
    _root = _CreateBinaryTree(arr, n, invalid, index);
  }

  BinaryTree(const BinaryTree<T>& t)
    :_root(NULL)
  {
    _root = _CopyTree(t._root);
  }

  BinaryTree<T>& operator=(const BinaryTree<T>& t)
  {
    if (this != t)
    {
      Node *tmp = new Node(t._root);
      if (tmp != NULL)
      {
        delete _root;
        _root = tmp;
      }
    }
    return *this;
  }

  ~BinaryTree()
  {
    _DestroyTree(_root);
    cout << endl;
  }

  //前序非遞歸
  void PrevOrder()
  {
    stack<Node*> s;
    Node *cur = _root;

    while (cur || !s.empty())
    {
      while (cur)
      {
        cout << cur->_data << " ";
        s.push(cur);
        cur = cur->_left;
      }
      //此時當(dāng)前節(jié)點的左子樹已遍歷完畢
      Node *tmp = s.top();
      s.pop();
      cur = tmp->_right;
    }
    cout << endl;
  }

  //前序遞歸
  void PrevOrderR()
  {
    _PrevOrder(_root);

    cout << endl;
  }

  //中序非遞歸
  void InOrder()
  {
    stack<Node*> s;
    Node *cur = _root;

    while (cur || !s.empty())
    {
      while (cur)
      {
        s.push(cur);
        cur = cur->_left;
      }
      //此時當(dāng)前節(jié)點的左子樹已遍歷完畢
      Node *tmp = s.top();
      cout << tmp->_data << " ";
      s.pop();
      cur = tmp->_right;
    }
    cout << endl;
  }

  //中序遞歸
  void InOrderR()
  {
    _InOrder(_root);

    cout << endl;
  }

  //后序非遞歸
  //后序遍歷可能會出現(xiàn)死循環(huán)，所以要記錄下前一個訪問的節(jié)點
  void PostOrder()
  {
    stack<Node*> s;
    Node *cur = _root;
    Node *prev = NULL;

    while (cur || !s.empty())
    {
      while (cur)
      {
        s.push(cur);
        cur = cur->_left;
      }
      Node *tmp = s.top();
      if (tmp->_right && tmp->_right != prev)
      {
        cur = tmp->_right;
      }
      else
      {
        cout << tmp->_data << " ";
        prev = tmp;
        s.pop();
      }
    }
    cout << endl;
  }

  //后序遞歸
  void PostOrderR()
  {
    _PostOrder(_root);

    cout << endl;
  }

  void LevelOrder() //利用隊列！??！
  {
    queue<Node*> q;
    Node *front = NULL;

    //1.push根節(jié)點
    if (_root)  
    {
      q.push(_root);
    }
    //2.遍歷當(dāng)前節(jié)點，push當(dāng)前節(jié)點的左右孩子，pop當(dāng)前節(jié)點
    //3.遍歷當(dāng)前節(jié)點的左孩子，再遍歷右孩子，循環(huán)直至隊列為空
    while (!q.empty())
    {

      front = q.front();
      cout << front->_data << " ";

      if (front->_left)
        q.push(front->_left);
      if (front->_right)
        q.push(front->_right);

      q.pop();
    }

    cout << endl;
  }

  size_t Size()
  {
    return _Size(_root);
  }

  size_t LeafSize()
  {
    return _LeafSize(_root);
  }

  size_t GetKLevel(int k)
  {
    return _GetKLevel(_root, k);
  }

  size_t Depth()
  {
    return _Depth(_root);
  }

  Node* Find(const T& d)
  {
    return _Find(_root, d);
  }

protected:
  Node* _CreateBinaryTree(T *arr, size_t n, const T& invalid, size_t& index)
  {
    Node *root = NULL;
    if (index < n && arr[index] != invalid)
    {
      root = new Node(arr[index]);
      index++;
      root->_left = _CreateBinaryTree(arr, n, invalid, index);
      index++;
      root->_right = _CreateBinaryTree(arr, n, invalid, index);
    }
    return root;
  }

  Node* _CopyTree(Node *root)
  {
    Node *newRoot = NULL;

    if (root)
    {
      newRoot = new Node(root->_data);
      newRoot->_left = _CopyTree(root->_left);
      newRoot->_right = _CopyTree(root->_right);
    }

    return newRoot;
  }

  void _DestroyTree(Node *root)
  {
    if (root)
    {
      _Destroy(root->_left);
      _Destroy(root->_right);
      delete root;
    }
  }

  void _PrevOrder(Node *root)
  {
    if (root == NULL) //必須有遞歸出口?。?！
      return;

    cout << root->_data << " ";
    _PrevOrder(root->_left);
    _PrevOrder(root->_right);
  }

  void _InOrder(Node *root)
  {
    if (root == NULL)
      return;

    _InOrder(root->_left);
    cout << root->_data << " ";
    _InOrder(root->_right);
  }

  void _PostOrder(Node *root)
  {
    if (root == NULL)
      return;

    _PostOrder(root->_left);
    _PostOrder(root->_right);
    cout << root->_data << " ";
  }

  size_t _Size(Node *root)
  {
    if (root == NULL)
      return 0;
    else
      return _Size(root->_left) + _Size(root->_right) + 1;
  }

  size_t _LeafSize(Node *root)
  {
    if (root == NULL)
      return 0;
    else if (root->_left == NULL && root->_right == NULL)
      return 1;
    else
      return _LeafSize(root->_left) + _LeafSize(root->_right);
  }

  size_t _GetKLevel(Node *root, int k)
  {
    if (root == NULL)
      return 0;
    else if (k == 1)
      return 1;
    else
      return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
  }

  size_t _Depth(Node *root)
  {
    if (root == NULL)
      return 0;
    else if (root->_left == NULL && root->_right == NULL)
      return 1;
    else
    {
      size_t leftDepth = _Depth(root->_left) + 1;
      size_t rightDepth = _Depth(root->_right) + 1;
      return leftDepth > rightDepth ? leftDepth : rightDepth;
    }
  }

  Node* _Find(Node *root, const T& d)
  {
    if (root == NULL)
      return NULL;
    else if (root->_data == d)
      return root;
    else if (Node *ret = _Find(root->_left, d))
      return ret;
    else
      _Find(root->_right, d);
  }

protected:
  Node *_root;
};

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

相關(guān)文章

  • c++動態(tài)內(nèi)存管理與智能指針的相關(guān)知識點

    c++動態(tài)內(nèi)存管理與智能指針的相關(guān)知識點

    為了更容易同時也更安全地使用動態(tài)內(nèi)存,新的標(biāo)準庫提供了兩種智能指針（smart pointer）類型來管理對象,下面這篇文章主要給大家介紹了關(guān)于c++動態(tài)內(nèi)存管理與智能指針的相關(guān)知識點,需要的朋友可以參考下
    2022-03-03
  • C++超詳細講解auto與nullptr的使用

    C++超詳細講解auto與nullptr的使用

    C++11提供了nullptr用來取代0或者NULL。在C++11之前，使用NULL為空指針賦初值，但NULL其實就是0，這時會把NULL當(dāng)成0來用；在C++11中，我們在聲明一個變量或?qū)ο螅付ㄋ念愋蜁r，可以不使用變量本身的類型而使用auto替代
    2022-05-05
  • c#中實現(xiàn)退出程序后自動重新啟動程序的方法

    c#中實現(xiàn)退出程序后自動重新啟動程序的方法

    下面小編就為大家?guī)硪黄猚#中實現(xiàn)退出程序后自動重新啟動程序的方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • c語言小游戲程序之彈跳小球的實現(xiàn)代碼

    c語言小游戲程序之彈跳小球的實現(xiàn)代碼

    這篇文章主要介紹了c語言小游戲程序之彈跳小球的實現(xiàn)代碼,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下
    2020-12-12
  • C語言小游戲之簡易版三子棋(棋盤可自由擴展)

    C語言小游戲之簡易版三子棋(棋盤可自由擴展)

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)三子棋游戲，還可以自由擴展棋盤大小，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2021-11-11
  • C語言實現(xiàn)大數(shù)值金額大寫轉(zhuǎn)換的方法詳解

    C語言實現(xiàn)大數(shù)值金額大寫轉(zhuǎn)換的方法詳解

    這篇文章主要為大家詳細介紹了如何利用C語言實現(xiàn)大數(shù)值金額大寫轉(zhuǎn)換的功能，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起了解一下
    2023-03-03
  • Qt實現(xiàn)UI界面純代碼示例

    Qt實現(xiàn)UI界面純代碼示例

    這篇文章主要給大家介紹了關(guān)于Qt實現(xiàn)UI界面的相關(guān)資料,使用Qt純代碼,實現(xiàn)了基本的界面,對大家學(xué)習(xí)或者使用Qt具有一定的參考借鑒價值,需要的朋友可以參考下
    2024-01-01
  • C語言實現(xiàn)反彈球消磚塊游戲

    C語言實現(xiàn)反彈球消磚塊游戲

    這篇文章主要為大家詳細介紹了C語言實現(xiàn)反彈球消磚塊游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
    2022-03-03
  • C++中string替換所有指定字符串的方法

    C++中string替換所有指定字符串的方法

    這篇文章主要介紹了C++中string替換所有指定字符串的實例代碼，本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2020-05-05
  • C 語言中strstr函數(shù)實例詳解

    C 語言中strstr函數(shù)實例詳解

    這篇文章主要介紹了C 語言中strstr函數(shù)實例詳解的相關(guān)資料,需要的朋友可以參考下
    2017-07-07

最新評論