当前位置：网站首页>树形结构：二叉树的递归非递归遍历、BST
树形结构：二叉树的递归非递归遍历、BST
2022-07-30 19:57:00 【@布响丸辣】
目录
一、二叉树递归遍历
二叉树介绍：
二叉树
1.有序树
2.树中包含的节点度不超过2，只能是0、1、2
二叉树的性质
一个深度为n的二叉树结点最多为 2^n - 1 最少为n个
二叉树中，第n层最多有 2^（n-1）个
二叉树中，度为0（n0）的结点数量等于 n0 = n2 + 1
满二叉树
除了叶子结点，所有结点的度都为2的二叉树
一个深度为n的满二叉树结点最多为 2^n - 1
满二叉树中不存在度为1的结点，且叶子结点都在最底层
n个结点的满二叉树的深度为 log2（n+1）
完全二叉树
除去最后一层结点为满二叉树，且最后一层结点从左到右依次分布
n个结点的完全二叉树的深度为 [log2n] + 1
将一颗n个结点的 完全二叉树 从上到下，从左到右依次编号对于任意一个结点（i）有如下结论：
i > 1 父亲结点为 i/2
-----------------------------------
2 * i > n 结点i没有左孩子
否则 左孩子为 2 * i
------------------------------------
2 * i + 1 > n 结点没有右孩子
否则 右孩子为 2 * i + 1
------------------------------------
下面请看详细代码
#include <iostream>
using namespace std;
struct BinaryTree
{
int value;
BinaryTree* pLeft;
BinaryTree* pRight;
};
// 递归
//前序打印
void PerOrderTraversal(BinaryTree* pRoot)
{
if (pRoot == NULL)
{
return;
}
//根
cout << pRoot->value <<" ";
//左
PerOrderTraversal(pRoot->pLeft);
//右
PerOrderTraversal(pRoot->pRight);
}
//中序打印
void InOrderTraversal(BinaryTree* pRoot)
{
if (pRoot == NULL)
{
return;
}
//左
InOrderTraversal(pRoot->pLeft);
//根
cout << pRoot->value << " ";
//右
InOrderTraversal(pRoot->pRight);
}
//后序打印
void PostOrderTraversal(BinaryTree* pRoot)
{
if (pRoot == NULL)
{
return;
}
//左
PostOrderTraversal(pRoot->pLeft);
//右
PostOrderTraversal(pRoot->pRight);
//根
cout << pRoot->value << " ";
}
int main()
{
//根
BinaryTree* pRoot = new BinaryTree;
pRoot->value = 1;
//-------------------------------------------------------
//根的左
pRoot->pLeft = new BinaryTree;
pRoot->pLeft->value = 2;
//左的左
pRoot->pLeft->pLeft = new BinaryTree;
pRoot->pLeft->pLeft->value = 4;
pRoot->pLeft->pLeft->pLeft = nullptr;
pRoot->pLeft->pLeft->pRight = nullptr;
//左的右
pRoot->pLeft->pRight = new BinaryTree;
pRoot->pLeft->pRight->value = 5;
pRoot->pLeft->pRight->pLeft = nullptr;
pRoot->pLeft->pRight->pRight = nullptr;
// ------------------------------------------------------
//根的右
pRoot->pRight = new BinaryTree;
pRoot->pRight->value = 3;
//右的左
pRoot->pRight->pLeft = nullptr;
//右的右
pRoot->pRight->pRight = new BinaryTree;
pRoot->pRight->pRight->value = 6;
pRoot->pRight->pRight->pLeft = nullptr;
pRoot->pRight->pRight->pRight = nullptr;
PerOrderTraversal(pRoot);
cout << endl;
InOrderTraversal(pRoot);
cout << endl;
PostOrderTraversal(pRoot);
cout << endl;
return 0;
}
输出：
1 2 4 5 3 6
4 2 5 1 3 6
4 5 2 6 3 1
D:\数据结构\树形结构\x64\Debug\树形结构.exe (进程 6220)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .
二、二叉树的非递归
#include <iostream>
using namespace std;
#include <stack>
#include <queue>
struct BinaryTree
{
int value;
BinaryTree* pLeft;
BinaryTree* pRight;
};
//递归
//前序打印
void PerOrderTraversal(BinaryTree* pRoot)
{
if (pRoot == NULL)
{
return;
}
//根
cout << pRoot->value <<" ";
//左
PerOrderTraversal(pRoot->pLeft);
//右
PerOrderTraversal(pRoot->pRight);
}
//中序打印
void InOrderTraversal(BinaryTree* pRoot)
{
if (pRoot == NULL)
{
return;
}
//左
InOrderTraversal(pRoot->pLeft);
//根
cout << pRoot->value << " ";
//右
InOrderTraversal(pRoot->pRight);
}
//后序打印
void PostOrderTraversal(BinaryTree* pRoot)
{
if (pRoot == NULL)
{
return;
}
//左
PostOrderTraversal(pRoot->pLeft);
//右
PostOrderTraversal(pRoot->pRight);
//根
cout << pRoot->value << " ";
}
//-------------------------------------------------------------------------------------------------------
// 非递归
// 前序
void UnRecPerOrderTraversal(BinaryTree* pRoot)
{
if (pRoot == NULL)
{
return;
}
stack<BinaryTree*> st;
loop
//while (1)
//{
// //loop
// while (pRoot != NULL)
// {
// //打印根
// cout << pRoot->value <<" ";
// //入栈（容器）
// st.push(pRoot);
// //向左走
// pRoot = pRoot->pLeft;
// }
// if (st.empty() == true)
// break;
// //出栈
// pRoot = st.top();
// st.pop();
// //向右走
// pRoot = pRoot->pRight;
//}
//cout << endl;
}
// 中序
void UnRecInOrderTraversal(BinaryTree* pRoot)
{
//if (pRoot == NULL)
//{
// return;
//}
//stack<BinaryTree*> st;
loop
//while (1)
//{
// //loop
// while (pRoot != NULL)
// {
// //入栈（容器）
// st.push(pRoot);
// //向左走
// pRoot = pRoot->pLeft;
// }
// if (st.empty() == true)
// break;
// //出栈
// pRoot = st.top();
// st.pop();
// //打印根
// cout << pRoot->value << " ";
// //向右走
// pRoot = pRoot->pRight;
//}
//cout << endl;
}
// 后序
void UnRecPostOrderTraversal(BinaryTree* pRoot)
{
//if (pRoot == NULL)
//{
// return;
//}
//stack<BinaryTree*> st;
//BinaryTree* pMark = NULL;
loop
//while (1)
//{
// //loop
// while (pRoot != NULL)
// {
// //入栈（容器）
// st.push(pRoot);
// //向左走
// pRoot = pRoot->pLeft;
// }
// if (st.empty() == true)
// break;
// //判断当前栈顶元素是否有右 或者 当前栈顶元素的右是否被标记过
// if (st.top()->pRight == NULL || st.top()->pRight == pMark)
// {
// pMark = st.top();
// st.pop();
// cout << pMark->value << " ";
// }
// else
// {
// pRoot = st.top();
// pRoot = pRoot->pRight;
// }
//}
//cout << endl;
}
//----------------------------------------------------------------------------------------------------
// 深度遍历
void LevelTraversal(BinaryTree* pRoot)
{
// if (pRoot == NULL)
//{
// return;
//}
//queue<BinaryTree*> que;
//que.push(pRoot);
//while (que.empty() != true)
//{
// //出队
// pRoot = que.front();
// que.pop();
// //非空
// //{
// //打印
// //左入队 右入队
// //}
// if (pRoot != NULL)
// {
// cout << pRoot->value << " ";
// que.push(pRoot->pLeft);
// que.push(pRoot->pRight);
// }
//}
//cout << endl;
}
int main()
{
//根
BinaryTree* pRoot = new BinaryTree;
pRoot->value = 1;
//-------------------------------------------------------
//根的左
pRoot->pLeft = new BinaryTree;
pRoot->pLeft->value = 2;
//左的左
pRoot->pLeft->pLeft = new BinaryTree;
pRoot->pLeft->pLeft->value = 4;
pRoot->pLeft->pLeft->pLeft = nullptr;
pRoot->pLeft->pLeft->pRight = nullptr;
//左的右
pRoot->pLeft->pRight = new BinaryTree;
pRoot->pLeft->pRight->value = 5;
pRoot->pLeft->pRight->pLeft = nullptr;
pRoot->pLeft->pRight->pRight = nullptr;
// ------------------------------------------------------
//根的右
pRoot->pRight = new BinaryTree;
pRoot->pRight->value = 3;
//右的左
pRoot->pRight->pLeft = new BinaryTree;
pRoot->pRight->pLeft->value = 6;
pRoot->pRight->pLeft->pLeft = nullptr;
pRoot->pRight->pLeft->pRight = nullptr;
//右的右
pRoot->pRight->pRight = new BinaryTree;
pRoot->pRight->pRight->value = 7;
pRoot->pRight->pRight->pLeft = nullptr;
pRoot->pRight->pRight->pRight = nullptr;
cout << "前序" << endl;
PerOrderTraversal(pRoot);
cout << endl;
UnRecPerOrderTraversal(pRoot);
cout << "-------------------------------------------" << endl;
cout << "中序" << endl;
InOrderTraversal(pRoot);
cout << endl;
UnRecInOrderTraversal(pRoot);
cout << "-------------------------------------------" << endl;
cout << "后序" << endl;
PostOrderTraversal(pRoot);
cout << endl;
UnRecPostOrderTraversal(pRoot);
cout << "-------------------------------------------" << endl;
cout << "深度遍历" << endl;
LevelTraversal(pRoot);
cout << "-------------------------------------------" << endl;
return 0;
system("pause");
return 0;
}
输出：
前序
1 2 4 5 3 6 7
-------------------------------------------
中序
4 2 5 1 6 3 7
-------------------------------------------
后序
4 5 2 6 7 3 1
-------------------------------------------
深度遍历
-------------------------------------------
D:\数据结构\树形结构\x64\Debug\树形结构.exe (进程 16244)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .
三、BST
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势；所以应用十分广泛，例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。
#include <iostream>
using namespace std;
typedef struct BST
{
int value;
BST* pleft;
BST* pright;
}List;
void Addbst(BST*& rpRoot, int value)
{
BST* ptemp = new BST;
ptemp->value = value;
ptemp->pleft = nullptr;
ptemp->pright = nullptr;
//判断是否有结点
if (rpRoot == nullptr)
{
rpRoot = ptemp;
return;
}
BST* pmark = rpRoot;
//寻找添加位置
//比较添加结点的值和标记的值
while (pmark != nullptr)
{
if (value < pmark->value) //小于 向左走
{
if (pmark->pleft == nullptr)
{
pmark->pleft = ptemp;
return;
}
pmark = pmark->pleft;
}
else if(value > pmark->value) //大于 向右走
{
if (pmark->pright == nullptr)
{
pmark->pright = ptemp;
return;
}
pmark = pmark->pright;
}
else //等于 数据有误结束
{
cout << "数据有误" << endl;
delete ptemp;
ptemp = nullptr;
return;
}
}
}
void Inordertraversal(BST*& rpRoot)
{
if (rpRoot == nullptr)
{
return;
}
Inordertraversal(rpRoot->pleft);
cout << rpRoot->value << " ";
Inordertraversal(rpRoot->pright);
}
BST* SearchBST(BST* pRoot, int value, BST*& rpfather)
{
while (pRoot != nullptr)
{
if (pRoot->value > value)
{
rpfather = pRoot;
pRoot = pRoot->pleft;
}
else if(pRoot->value < value)
{
rpfather = pRoot;
pRoot = pRoot->pright;
}
else
{
return pRoot;
}
}
rpfather = nullptr;
return nullptr;
}
void DeleteBST(BST*& rpRoot, int value)
{
BST* pFather = nullptr;
//找到要删除的结点和他的父亲
BST* pDel = SearchBST(rpRoot, value, pFather);
if (pDel == nullptr)
{
cout << "没有找到要删除的结点" << endl;
return;
}
//分析孩子情况
//两个孩子
if (pDel->pleft != nullptr && pDel->pright != nullptr)
{
//找左的最右 或者 右的最左 替换掉要删除的结点
BST* pMark = pDel;
pFather = pDel;
pDel = pDel->pleft;
while (pDel->pright != nullptr)
{
pFather = pDel;
pDel = pDel->pright;
}
//替换
pMark->value = pDel->value;
}
//一个孩子
//没有孩子
//判断是不是根
if (pFather == nullptr)
{
rpRoot = pDel->pleft != nullptr ? pDel->pleft : pDel->pright;
}
//非根
//判断删除结点是父亲的左还是右
if (pFather->pleft == pDel)
{
pFather->pleft = pDel->pleft != nullptr ? pDel->pleft : pDel->pright;
}
else
{
pFather->pright = pDel->pleft != nullptr ? pDel->pleft : pDel->pright;
}
//删除
delete pDel;
pDel = nullptr;
}
void BSTtoList(BST* pRoot,List*& rpHead,List*& rpEnd)
{
if (pRoot == nullptr)
{
return;
}
BSTtoList(pRoot->pleft, rpHead, rpEnd);
if (rpHead == nullptr)
{
rpHead = pRoot;
}
else
{
rpEnd->pright = pRoot;
pRoot->pleft = rpEnd;
}
rpEnd = pRoot;
BSTtoList(pRoot->pright, rpHead, rpEnd);
}
int main()
{
BST* pRoot = nullptr;
Addbst(pRoot, 34);
Addbst(pRoot, 12);
Addbst(pRoot, 50);
Addbst(pRoot, 40);
Addbst(pRoot, 17);
Addbst(pRoot, 8);
/*Inordertraversal(pRoot);
cout << endl;*/
/*BST* pfather = nullptr;
BST* ptemp = SearchBST(pRoot, 8, pfather);*/
DeleteBST(pRoot, 12);
Inordertraversal(pRoot);
cout << endl;
/*DeleteBST(pRoot, 21);
Inordertraversal(pRoot);
cout << endl;*/
List* pHead = nullptr;
List* pEnd = nullptr;
BSTtoList(pRoot, pHead, pEnd);
return 0;
}
输出：
8 17 34 40 50
D:\数据结构\树形结构\x64\Debug\树形结构.exe (进程 18648)已退出，代码为 0。
要在调试停止时自动关闭控制台，请启用“工具”->“选项”->“调试”->“调试停止时自动关闭控制台”。
按任意键关闭此窗口. . .
边栏推荐
- How to install and use PostgreSQL 14.4
- 【flink】报错整理 Could not instantiate the executor. Make sure a planner module is on the classpath
- ERROR 1045 (28000) Access denied for user 'root'@'localhost'Solution
- LeetCode 0952.按公因数计算最大组件大小：建图 / 并查集
- coming!Dongfang Selection brings goods to the live broadcast of Longjiang agricultural products
- [Private Series] All kinds of strange problems encountered in daily PHP
- MySQL性能优化（硬件，系统配置，表结构，SQL语句）
- 时间复杂度与空间复杂度
- DCM 中间件家族迎来新成员
- Recommended system: cold start problem [user cold start, item cold start, system cold start]
猜你喜欢
推荐系统：实时性【特征实时性：客户端实时特征（秒级，实时）、流处理平台（分钟级，近实时）、分布式批处理平台（小时/天级，非实时）】【模型实时性：在线学习、增量更新、全量更新】
LeetCode 0952. Calculate Maximum Component Size by Common Factor: Mapping / Union Search
ELK日志分析系统
TensorFlow2: Overview
Ordinary int main(){} does not write return 0; what will happen?
Linux下安装MySQL教程
VBA runtime error '-2147217900 (80040e14): Automation error
360杜跃进：太空安全风险加剧，需打造一体化防御体系
Database indexes: indexes are not a panacea
18.客户端会话技术Cookie
随机推荐
【flink】报错整理 Could not instantiate the executor. Make sure a planner module is on the classpath
Redisson 的分布式锁找不到？
4年测试经验去面试10分钟就被赶出来了，面试官说我还不如应届生？都这么卷吗...
el-input can only input integers (including positive numbers, negative numbers, 0) or only integers (including positive numbers, negative numbers, 0) and decimals
LeetCode 0952.按公因数计算最大组件大小：建图 / 并查集
FFmpeg —— 裁剪视频(含音视频)，不需编解码（附完整源码）
试写C语言三子棋
Brush questions record----string
Install Mysql5.7 under Linux, super detailed and complete tutorial, and cloud mysql connection
Frog jumping steps (recursive and non-recursive) ------- Xiaolele walks the steps
MySQL Functions (Classic Collection)
MySQl数据库————DQL数据查询语言
DCM 中间件家族迎来新成员
Different lower_case_table_names settings for server (‘1‘) and data dictionary (‘0‘) 解决方案
为单行查询设置JDBC Statement.setFetchSize()为1的方法指南
【私人系列】日常PHP遇到的各种稀奇古怪的问题
推荐系统：概述【架构：用户/物品特征工程----＞召回层----＞排序层----＞测试/评估】【冷启动问题、实时性问题】
Linux下载安装mysql5.7版本教程最全详解
MySQL大总结
英文字母间隔突然增大（全角与半角转换）