c++ 先序构建二叉树
程序员文章站
2022-04-14 09:39:18
二叉树首先要解决构建问题,才能考虑后续的遍历,这里贴出通过先序构建二叉树,同时包含四种二叉树的遍历方法(先序,中序,后序,逐层) 第一、定义BinaryTreeNode 类 1 #include 2 #include 3 #include 4 ......
二叉树首先要解决构建问题,才能考虑后续的遍历,这里贴出通过先序构建二叉树,同时包含四种二叉树的遍历方法(先序,中序,后序,逐层)
第一、定义binarytreenode 类
1 #include <iostream> 2 #include <string> 3 #include <queue> 4 using namespace std; 5 6 template<typename t >class binarytree; 7 template <typename t> class binarytreenode { 8 public: 9 friend class binarytree<t>; 10 binarytreenode() { 11 data = null; 12 lchild = rchild = null; 13 } 14 binarytreenode(t newdata) { 15 this->data = newdata; 16 lchild = rchild = null; 17 } 18 t getdata() { 19 return data; 20 } 21 binarytreenode<t> * getleftnode() { 22 return lchild; 23 } 24 binarytreenode<t> * getrightnode() { 25 return rchild; 26 } 27 t data; 28 binarytreenode<t>* lchild; 29 binarytreenode<t>* rchild; 30 private: 31 32 };
第二、定义binarytree 类
1 template <typename t> class binarytree { 2 public: 3 binarytreenode<t> *root; 4 char* p; 5 binarytree() { root = null; } 6 binarytree(t data) { 7 root = new binarytreenode<t>(data); 8 root->lchild = null; 9 root->rchild = null; 10 } 11 ~binarytree() { 12 delete root; 13 } 14 15 //构建二叉树并返回 16 binarytreenode<t>* createtree() { 17 binarytreenode<int>* bt = null; 18 char t; 19 cin >> t; 20 if (t == '#') 21 { 22 return null; 23 } 24 else { 25 int num = t - '0'; 26 bt = new binarytreenode<t>(num); 27 bt->lchild = createtree(); 28 bt->rchild = createtree(); 29 } 30 return bt; 31 } 32 33 //先序构建二叉树 34 binarytreenode<t>* precreatetree() { 35 binarytreenode<int>* bt = null; 36 if (this->root == null) 37 { 38 cout << "请输入根节点(#代表空树):"; 39 } 40 else { 41 cout << "请输入节点(#代表空树):"; 42 } 43 char t; 44 cin >> t; 45 if (t == '#') 46 { 47 return null; 48 } 49 else { 50 int num = t - '0'; 51 bt = new binarytreenode<t>(num); 52 if (this->root == null) 53 { 54 this->root = bt; 55 } 56 cout << bt->data << "的左孩子"; 57 bt->lchild = precreatetree(); 58 59 cout << bt->data << "的右边孩子"; 60 bt->rchild = precreatetree(); 61 } 62 return bt; 63 } 64 65 void preodertraversal(binarytreenode<t> *bt); //先序遍历 66 void inordertraversal(binarytreenode<t> *bt); //中序遍历 67 void postordertraversal(binarytreenode<t> *bt);//后序遍历 68 void leveltraversal(binarytreenode<t> *bt); //逐层遍历 69 70 private: 71 72 }; 73 74 template <typename t> 75 void binarytree<t>::preodertraversal(binarytreenode<t> *bt) { 76 if (bt) 77 { 78 cout << bt->data; 79 binarytree<t>::preodertraversal(bt->getleftnode()); 80 binarytree<t>::preodertraversal(bt->getrightnode()); 81 } 82 } 83 84 template <typename t> 85 void binarytree<t>::inordertraversal(binarytreenode<t> *bt) { 86 if (bt) 87 { 88 binarytree<t>::inordertraversal(bt->getleftnode()); 89 cout << bt->data; 90 binarytree<t>::inordertraversal(bt->getrightnode()); 91 } 92 } 93 94 template <typename t> 95 void binarytree<t>::postordertraversal(binarytreenode<t> *bt) { 96 if (bt) 97 { 98 binarytree<t>::postordertraversal(bt->getleftnode()); 99 binarytree<t>::postordertraversal(bt->getrightnode()); 100 cout << bt->data; 101 } 102 } 103 104 template <typename t> 105 void binarytree<t>::leveltraversal(binarytreenode<t> *bt) { 106 107 queue<binarytreenode<t>*> que; 108 que.push(bt); 109 while (!que.empty()) 110 { 111 binarytreenode<t>* proot = que.front(); 112 que.pop(); 113 cout << proot->data; 114 115 if (proot->lchild != null) 116 { 117 que.push(proot->lchild);//左孩子入队 118 } 119 if (proot->rchild != null) 120 { 121 que.push(proot->rchild);//右孩子入队 122 } 123 } 124 }
第三、主程序运行
1 #include "pch.h" 2 #include <iostream> 3 #include "binarytree.h" 4 5 int main() 6 { 7 //场景测试2 8 binarytree<int> btree; 9 btree.precreatetree();//先序构建二叉树 10 cout << "先序遍历:"; 11 btree.preodertraversal(btree.root); cout << endl;//先序遍历 12 cout << "中序遍历:"; 13 btree.inordertraversal(btree.root); cout << endl;//中序遍历 14 cout << "后序遍历:"; 15 btree.postordertraversal(btree.root); cout << endl;//后序遍历 16 cout << "逐层序遍历:"; 17 btree.leveltraversal(btree.root); 18 19 }
最终测试运行截图