C++ 手动创建二叉树，并实现前序、中序、后序、层次遍历
2024-10-21 06:35:59
二叉树的创建是个麻烦事，我的思路是：首先将一个普通的二叉树转化为满二叉树，其中的空节点用一些标识数据来代替，如此一来，就可以用数组索引来描述数据在二叉树的什么位置了。
比如，数组[2,4,3,1,5,-1,-1] 就可以表示一个三层的二叉树，具体长这样：
对于四种遍历方法，前序、中序、后序、层次遍历方法，给出了递归和迭代两种方式
具体代码如下：
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
using namespace std;
/*实现普通二叉树的创建，以及四种遍历方法*/
template <typename T>
class Node {
public:
T val = 0;
Node<T>* lchild = nullptr;
Node<T>* rchild = nullptr;
Node(T& a): val(a){}
};
template <typename T>
class BinTree {
public:
Node<T>* root = nullptr;
BinTree(vector<T>& value, int n);
void creatTree(Node<T>*& p, vector<T>& value, int n, const int len);
void preOrder1(Node<T>* p); //递归
void preOrder2(); //迭代
void inOrder1(Node<T>* p); //递归
void inOrder2(); //迭代
void postOrder1(Node<T>* p); //递归
void postOrder2(); //迭代
void levelOrder();
void visit(Node<T>* p);
};
template <typename T>
BinTree<T>::BinTree(vector<T>& value, int n) {
if ( value.size() != pow(2, n)-1 ) {//树的高度与元素个数不匹配
cout << " elements not match to level " << endl;
return;
}
creatTree(root, value, 0, pow(2, n)-1 );
}
template <typename T>
void BinTree<T>::creatTree(Node<T>*& p, vector<T>& value, int n, const int len) {
if ( n < len && value[n] != -1 ) {
p = new Node<T> (value[n]);
creatTree(p->lchild, value, 2*n+1, len); //创建左子树
creatTree(p->rchild, value, 2*(n+1), len); //创建you子树
}
}
template <typename T>
void BinTree<T>::visit(Node<T>* p) {
cout << p->val << " ";
}
template <typename T>
void BinTree<T>::preOrder1(Node<T>* p) {
if (p) {
visit(p);
preOrder1(p->lchild);
preOrder1(p->rchild);
}
}
template <typename T>
void BinTree<T>::inOrder1(Node<T>* p) {
if (p) {
inOrder1(p->lchild);
visit(p);
inOrder1(p->rchild);
}
}
template <typename T>
void BinTree<T>::postOrder1(Node<T>* p) {
if (p) {
postOrder1(p->lchild);
postOrder1(p->rchild);
visit(p);
}
}
template <typename T>
void BinTree<T>::preOrder2() {
stack<Node<T>*> st;
Node<T>* p = this->root;
st.push(p->rchild);
visit(p);
while ( !st.empty() ) {
if ( p->lchild )
p = p->lchild;
else {
p = st.top();
st.pop();
}
visit(p);
if ( p->rchild )
st.push(p->rchild);
}
}
template <typename T>
void BinTree<T>::inOrder2() {
stack<Node<T>*> st;
Node<T>* p = this->root;
while ( p || !st.empty() ) {
if (p) {
st.push(p);
p = p->lchild;
}
else {
p = st.top();
st.pop();
visit(p);
p = p->rchild;
}
}
}
template <typename T>
void BinTree<T>::postOrder2() {
//太难了，cpu快想炸了，摆了
}
template <typename T>
void BinTree<T>::levelOrder() {
queue<Node<T>*> Q;
Node<T>* p = this->root;
Q.push(p);
while ( !Q.empty() ) {
p = Q.front();
Q.pop();
visit(p);
if ( p->lchild )
Q.push(p->lchild);
if ( p->rchild )
Q.push(p->rchild);
}
}
void sets(int* n) {
n = new int (3);
}
int main() {
vector<int> a = {2,4,3,1,5,-1,-1};
a.shrink_to_fit();
BinTree<int> *b = new BinTree<int> (a, 3);
cout << b->root->val << " ";
cout << b->root->lchild->val << " ";
cout << b->root->rchild->val << " ";
cout << b->root->lchild->lchild->val << " ";
cout << b->root->lchild->rchild->val << endl;
cout << "前序遍历(递归): ";
b->preOrder1(b->root);
cout << "\n中序遍历(递归): ";
b->inOrder1(b->root);
cout << "\n后序遍历(递归): ";
b->postOrder1(b->root);
cout << "\n前序遍历(迭代): ";
b->preOrder2();
cout << "\n中序遍历(迭代): ";
b->inOrder2();
cout << "\n层次遍历: ";
b->levelOrder();
cout << endl;
var code = "93e77dd0-c6ba-4c8a-bc02-31555a7fa65d"
}
最新文章
- 在ubuntu/deepin/mint等系统中使用命令删除文件或文件夹
- HttpHander与httpModel配置与应用
- 基于openssl的单向和双向认证
- liux环境下配置jdk
- js浮点数运算需要注意的问题
- Yii中CDbCriteria常用方法
- OpenGL ES 3.0 基础知识
- Android学习之路——简易版微信为例（三）
- ASPNETMVC多语言方案
- Java基础知识强化84：System类之exit()方法和currentTimeMillis()方法
- windows服务器性能监控工具、方法及关键指标
- 50道java线程面试题
- Oracle COMMIT语句的处理顺序
- java基础小项目练习之1----3天做出飞机大战
- Linux挖矿病毒 khugepageds详细解决步骤
- mssql sqlserver 表增加列后，视图不会自动更新相关列的两种解决方法分享
- unity最基本操作
- DOM随时记
- SPA页面初试
- oracle逐步学习总结之oracle数字函数和日期函数（基础四）