c++經典例題之先序二元樹的構建

little bottle
發布: 2019-04-20 17:31:36
轉載
3167 人瀏覽過

這篇文章小編將帶大家一起回顧經典C 之建構先序二叉樹,有興趣的小夥伴一起來複習一下吧!

二元樹首先要解決建構問題,才能考慮後續的遍歷,這裡貼出透過先序建構二元樹,同時包含四種二元樹的遍歷方法(先序,中序,後序,逐層)

第一、定義BinaryTreeNode 類別

#include  #include  #include  using namespace std; templateclass BinaryTree; template  class BinaryTreeNode { public: friend class BinaryTree; BinaryTreeNode() { data = NULL; lChild = rChild = NULL; } BinaryTreeNode(T newdata) { this->data = newdata; lChild = rChild = NULL; } T getData() { return data; } BinaryTreeNode * getLeftNode() { return lChild; } BinaryTreeNode * getRightNode() { return rChild; } T data; BinaryTreeNode* lChild; BinaryTreeNode* rChild; private: };
登入後複製

View Code

第二、定義BinaryTree 類別

template  class BinaryTree { public: BinaryTreeNode *root; char* p; BinaryTree() { root = NULL; } BinaryTree(T data) { root = new BinaryTreeNode(data); root->lChild = NULL; root->rChild = NULL; } ~BinaryTree() { delete root; } //构建二叉树并返回 BinaryTreeNode* CreateTree() { BinaryTreeNode* bt = NULL; char t; cin >> t; if (t == '#') { return NULL; } else { int num = t - '0'; bt = new BinaryTreeNode(num); bt->lChild = CreateTree(); bt->rChild = CreateTree(); } return bt; } //先序构建二叉树 BinaryTreeNode* PreCreateTree() { BinaryTreeNode* bt = NULL; if (this->root == NULL) { cout << "请输入根节点(#代表空树):"; } else { cout << "请输入节点(#代表空树):"; } char t; cin >> t; if (t == '#') { return NULL; } else { int num = t - '0'; bt = new BinaryTreeNode(num); if (this->root == NULL) { this->root = bt; } cout << bt->data << "的左孩子"; bt->lChild = PreCreateTree(); cout << bt->data << "的右边孩子"; bt->rChild = PreCreateTree(); } return bt; } void preOderTraversal(BinaryTreeNode *bt); //先序遍历 void inOrderTraversal(BinaryTreeNode *bt); //中序遍历 void postOrderTraversal(BinaryTreeNode *bt);//后序遍历 void levelTraversal(BinaryTreeNode *bt); //逐层遍历 private: }; template  void BinaryTree::preOderTraversal(BinaryTreeNode *bt) { if (bt) { cout << bt->data; BinaryTree::preOderTraversal(bt->getLeftNode()); BinaryTree::preOderTraversal(bt->getRightNode()); } } template  void BinaryTree::inOrderTraversal(BinaryTreeNode *bt) { if (bt) { BinaryTree::inOrderTraversal(bt->getLeftNode()); cout << bt->data; BinaryTree::inOrderTraversal(bt->getRightNode()); } } template  void BinaryTree::postOrderTraversal(BinaryTreeNode *bt) { if (bt) { BinaryTree::postOrderTraversal(bt->getLeftNode()); BinaryTree::postOrderTraversal(bt->getRightNode()); cout << bt->data; } } template  void BinaryTree::levelTraversal(BinaryTreeNode *bt) { queue*> que; que.push(bt); while (!que.empty()) { BinaryTreeNode* proot = que.front(); que.pop(); cout << proot->data; if (proot->lChild != NULL) { que.push(proot->lChild);//左孩子入队 } if (proot->rChild != NULL) { que.push(proot->rChild);//右孩子入队 } } }
登入後複製

View Code

#

第三、主程式執行

#
#include "pch.h" #include  #include "BinaryTree.h" int main() { //场景测试2 BinaryTree btree; btree.PreCreateTree();//先序构建二叉树 cout << "先序遍历:"; btree.preOderTraversal(btree.root); cout << endl;//先序遍历 cout << "中序遍历:"; btree.inOrderTraversal(btree.root); cout << endl;//中序遍历 cout << "后序遍历:"; btree.postOrderTraversal(btree.root); cout << endl;//后序遍历 cout << "逐层序遍历:"; btree.levelTraversal(btree.root); }
登入後複製

View Code

最終測試運行截圖

# 相關教學:C 影片教學

以上是c++經典例題之先序二元樹的構建的詳細內容。更多資訊請關注PHP中文網其他相關文章!

相關標籤:
c++
來源:cnblogs.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
作者最新文章
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板
關於我們 免責聲明 Sitemap
PHP中文網:公益線上PHP培訓,幫助PHP學習者快速成長!