二叉树的创建和中序及后序遍历
二叉的先序创建
使用#号来表示该结点为null
实现代码
先进行先序创建然后进行先序遍历
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
//#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef struct BiNode {
char data;//数据域
struct BiNode *lchild;//左孩子指针
struct BiNode *rchild;//右孩子指针
} BiNode, *BiTree;//定义二叉树结点
/*
按照先序创建
*/
void CreateBiTree(BiTree &T) {
char ch;
cin >> ch;
if (ch == '#') {
T = NULL;
return;
} else {
T = new BiNode;//开辟结点
T->data = ch; //对数据域赋值
CreateBiTree(T->lchild);//建立左子树
CreateBiTree(T->rchild);//建立右子树
}
}
/*
前序遍历
*/
void DLR(BiTree T) {
if (T == NULL) {
return ;
} else {
char ch = T->data;
cout << ch;
DLR(T->lchild);
DLR(T->rchild);
}
}
/*
中序遍历
*/
void LDR(BiTree T) {
if (T == NULL) {
return ;
} else {
char ch = T->data;
LDR(T->lchild);//先访问左子树
cout << ch;//再访问根结点
LDR(T->rchild);//再访问右子树
}
}
/*
后序遍历
*/
void LRD(BiTree T) {
if (T == NULL) {
return ;
} else {
char ch = T->data;
LRD(T->lchild);//先访问左子树
LRD(T->rchild);//再访问右子树
cout << ch;//再访问根结点
}
}
int main () {
BiTree root = NULL;
CreateBiTree(root);
DLR(root);
cout << '\n';
// LDR(root);
// cout<<'\n';
// LRD(root);
return 0;
}
/*
abc##de#g##f###
*/
二叉树的中序遍历
1.先访问左子树
2.再访问根结点
3.最后访问右子树
中序遍历示意图
中序遍历算法实现
二叉树的后序遍历
-
先访问左子树
-
再访问右子树
-
最后访根结点
后序遍历的示意图
后序遍历的算法实现
一道例题
第二道例题
完整的代码实现
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
using namespace std;
typedef struct BiNode {
struct BiNode *lchild, *rchild;//左孩子右孩子
char data;//数据域
} BiNode, *BiTree;
/*
二叉树的先序创建
*/
void CreateBitree(BiTree &T) {
char ch;
cin >> ch;
if (ch == ',') {
T = NULL; //,表示该结点为空
} else {
T = new BiNode; //创建一个新结点
T->data = ch; //给数据域赋值
CreateBitree(T->lchild);//建立左子树
CreateBitree(T->rchild);//建立右子树
}
}
/*
二叉树的先序遍历
*/
void DLR(BiTree T) {
if (T == NULL) {
return;
} else {
cout << T->data; //先访问根
DLR(T->lchild);//访问左子树
DLR(T->rchild);//访问右子树
}
}
/*
二叉树的中序遍历
*/
void LDR(BiTree T) {
if (T == NULL) {
return;
} else {
LDR(T->lchild);//访问左子树
cout << T->data; //访问根
LDR(T->rchild);//访问右子树
}
}
/*
二叉树的后序遍历
*/
void LRD(BiTree T) {
if (T == NULL) {
return;
} else {
LRD(T->lchild);//访问左子树
LRD(T->rchild);//访问右子树
cout << T->data; //访问根
}
}
signed main () {
BiTree root = NULL; //创建根结点
cout << "请输入需要建立的二叉树的数值\n";
CreateBitree(root);//创建二叉树
cout << "下面是二叉树先序遍历结果\n";
DLR(root);
cout << "\n下面是二叉树中序遍历结果\n";
LDR(root);
cout << "\n下面是二叉树后序遍历结果\n";
LRD(root);
return 0;
}
/*
abc,,de,g,,f,,,
中序:
cbegdfa
后序:
cgefdba
*/