当前位置：网站首页>二叉树的操作集：（二叉树的定义，遍历）
二叉树的操作集：（二叉树的定义，遍历）
2022-07-29 21:22:00 【疯疯癫癫才自由】
/**
二叉树的操作集：
bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
void Traversal(BinTree BT);//遍历BT树；
BinTree NewNode(int data) //新建一个结点
void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
//数据域修改为给定数据域。
void Insert(BinTree *&root,int x); //在二叉树中插入一个数据域为x的新节点；
BinTree CreateBinTree();//创建一棵二叉树；
*/
1)递归遍历
/**
二叉树的操作集：
bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
void Traversal(BinTree BT);//遍历BT树；
BinTree NewNode(int data) //新建一个结点
void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
//数据域修改为给定数据域。
void Insert(BinTree *&root,int x); //在二叉树中插入一个数据域为x的新节点；
BinTree CreateBinTree();//创建一棵二叉树；
1)递归遍历
*/
#include <iostream>
#include <queue>
using namespace std;
typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode
{
ElementType data;
BinTree left;
BinTree right;
};
typedef BinTree Position;
bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
void PreTraver(BinTree BT);//前序遍历
void MidTraver(BinTree BT); //中序遍历
void BehTraver(BinTree BT); //后序遍历
void LayTraver(BinTree BT); //层次遍历 layer:层次，阶层
void PrePrintLeaves(BinTree BT);//打印叶子结点
int GetHeight(BinTree BT); //获得树的高度
BinTree NewNode(int data); //新建一个结点
void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
//数据域修改为给定数据域。
void Insert(BinTree &root,int x); //在二叉树中插入一个数据域为x的新节点；
BinTree CreateBinTree(int data);//创建一棵二叉树；
int main()
{
cout << "Hello world!" << endl;
return 0;
}
bool IsEmpty(BinTree BT)//BT为空，则返回true，否则返回false；
{
return (BT==NULL);
}
void PreTraver(BinTree BT) //前序遍历
{
if(BT)
{
printf("%d ",BT->data);
PreTraver(BT->left);
PreTraver(BT->right);
}
}
void MidTraver(BinTree BT) //中序遍历
{
if(BT)
{
MidTraver(BT->left);
printf("%d ",BT->data);
MidTraver(BT->right);
}
}
void BehTraver(BinTree BT) //后序遍历
{
if(BT)
{
BehTraver(BT->left);
BehTraver(BT->right);
printf("%d ",BT->data);
}
}
void LayTraver(BinTree BT) //层次遍历
{
if(!BT)
return;
queue<BinTree> q;
q.push(BT);
BinTree top;
while(!q.empty())
{
top=q.front();
q.pop();
printf("%d ",top->data);
if(top->left)
q.push(top->left);
if(top->right)
q.push(top->right);
}
}
void PrePrintLeaves(BinTree BT) //打印叶子结点
{
if(BT)
{
if(!BT->left&&!BT->right)
printf("%d ",BT->data);
PrePrintLeaves(BT->left);
PrePrintLeaves(BT->right);
}
}
int GetHeight(BinTree BT) //获得树的高度
{
if(BT)
return max(GetHeight(BT->left),GetHeight(BT->right))+1;
else
return 0; //空树高度为0；
}
BinTree NewNode(int data) //新建一个结点
{
BinTree BT = (BinTree) malloc(sizeof(TNode));
BT->data=data;
BT->left=BT->right=NULL;
return BT;
}
void Search(BinTree BT,int x,int newdata)//在二叉树中将所有数据域为给定数据域的结点，并把他们的
//数据域修改为给定数据域。
{
if(BT) //递归边界
{
if(BT->data==x)
BT->data=newdata;
Search(BT->left,x,newdata);
Search(BT->right,x,newdata);
}
}
void Insert(BinTree &root,int x) //在二叉树中插入一个数据域为x的新节点；且root需定义为引用
{
if(root == NULL)
root=NewNode(x);
if(check(root->left,x)) // 如果x满足二叉树左孩子分支的特性
Insert(root->left,x);
else
Insert(root->right,x);
}
BinTree CreateBinTree(int data) //创建一棵二叉树；
{
BinTree BT=NULL;
Insert(BT,data);
return BT;
}2)非递归遍历
///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
void BehTraver(BinTree BT) //后序遍历
{
BinTree top=BT,sec;
stack<BinTree> st;
while(top||!st.empty())
{
while(top)
{
st.push(top);
st.push(top);
top=top->left;
}
top=st.top();
st.pop();
if(!st.empty())
sec=st.top();
else
{
printf("%d ",top->data);
break; //树根节点遍历后，可直接跳出循环，即结束程序
}
if(top==sec)
top=top->right;
else
{
printf("%d ",top->data);
top=NULL;
}
}
}
/**
二叉树的操作集：
bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
void Traversal(BinTree BT);//遍历BT树；
BinTree NewNode(int data) //新建一个结点
void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
//数据域修改为给定数据域。
void Insert(BinTree *&root,int x); //在二叉树中插入一个数据域为x的新节点；
BinTree CreateBinTree();//创建一棵二叉树；
2)非递归遍历
*/
/**
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode
{
ElementType data;
BinTree left;
BinTree right;
};
typedef BinTree Position;
bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
void PreTraver(BinTree BT);//前序遍历
void MidTraver(BinTree BT); //中序遍历
void BehTraver(BinTree BT); //后序遍历
void LevTraver(BinTree BT); //层次遍历
BinTree CreateBinTree();//创建一棵二叉树；
void PrePrintLeaves(BinTree BT);//打印叶子结点
BinTree NewNode(int data); //新建一个结点
void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
//数据域修改为给定数据域。
void Insert(BinTree &root,int x); //在二叉树中插入一个数据域为x的新节点；
BinTree CreateBinTree(int data);//创建一棵二叉树；
int main()
{
stack<int> st;
for(int i=0;i<3;++i)
st.push(i);
cout << st.top() << endl;
int top=st.top();
top=5;
cout << st.top() << endl;
st.top()=6;
cout << st.top() << endl;
cout << "Hello world!" << endl;
return 0;
}
bool IsEmpty(BinTree BT)//BT为空，则返回true，否则返回false；
{
return (BT==NULL);
}
void PreTraver(BinTree BT) //前序遍历
{
BinTree top=BT;
stack<BinTree> st;
while(top||!st.empty())
{
while(top)
{
printf("%d ",top->data);
st.push(top);
top=top->left;
}
top=st.top();
st.pop();
top=top->right;
}
}
void MidTraver(BinTree BT) //中序遍历
{
BinTree top=BT;
stack<BinTree> st;
while(top||!st.empty())
{
while(top)
{
st.push(top);
top=top->left;
}
top=st.top();
st.pop();
printf("%d ",top->data);
top=top->right;
}
}
///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
void BehTraver(BinTree BT) //后序遍历
{
BinTree top=BT,sec;
stack<BinTree> st;
while(top||!st.empty())
{
while(top)
{
st.push(top);
st.push(top);
top=top->left;
}
top=st.top();
st.pop();
if(!st.empty())
sec=st.top();
else
{
printf("%d ",top->data);
break; //树根节点遍历后，可直接跳出循环，即结束程序
}
if(top==sec)
top=top->right;
else
{
printf("%d ",top->data);
top=NULL;
}
}
}
void LevTraver(BinTree BT) //层次遍历
{
if(!BT)
return;
queue<BinTree> q;
q.push(BT);
BinTree top;
while(!q.empty())
{
top=q.front();
q.pop();
printf("%d ",top->data);
if(top->left)
q.push(top->left);
if(top->right)
q.push(top->right);
}
}
void PrePrintLeaves(BinTree BT) //打印叶子结点
{
if(BT)
{
if(!BT->left&&!BT->right)
printf("%d ",BT->data);
PrePrintLeaves(BT->left);
PrePrintLeaves(BT->right);
}
}
int GetHeight(BinTree BT) //获得树的高度
{
if(BT)
return max(GetHeight(BT->left),GetHeight(BT->right))+1;
else
return 0; //空树高度为0；
}
BinTree NewNode(int data) //新建一个结点
{
BinTree BT = (BinTree) malloc(sizeof(TNode));
BT->data=data;
BT->left=BT->right=NULL;
return BT;
}
void Search(BinTree BT,int x,int newdata)//在二叉树中将所有数据域为给定数据域的结点，并把他们的
//数据域修改为给定数据域。
{
if(BT) //递归边界
{
if(BT->data==x)
BT->data=newdata;
Search(BT->left,x,newdata);
Search(BT->right,x,newdata);
}
}
void Insert(BinTree &root,int x) //在二叉树中插入一个数据域为x的新节点；且root需定义为引用
{
if(root == NULL)
root=NewNode(x);
if(check(root->left,x)) // 如果x满足二叉树左孩子分支的特性
Insert(root->left,x);
else
Insert(root->right,x);
}
BinTree CreateBinTree(int data) //创建一棵二叉树；
{
BinTree BT=NULL;
Insert(BT,data);
return BT;
}
*/
边栏推荐
- Bug fix: Clipping input data to the valid range for imshow with RGB data ([0..1] for floats or [0..255]
- VSCode配置终端为系统命令行
- Numpy数组处理（二）
- 【Verilog】Verilog设计进阶
- mdnice-test
- LeetCode 593 Valid Squares [Math] HERODING's Road to LeetCode
- 初识网络的简单概念
- 南信大提出TIPCB，一个简单但有效的用于基于文本的人员搜索的基于部分的卷积baseline
- UDP协议详解
- 【AD】【持续更新ing】关于AD设计过程中一些小细节
猜你喜欢
全系都更换带T四缸，安全、舒适一个不落
SwiftUI CoreData 教程之如何加速搜索速度
HMS Core音频编辑服务音源分离与空间音频渲染，助力快速进入3D音频的世界
结合布林线理解现货白银走势图的方法
南信大提出TIPCB，一个简单但有效的用于基于文本的人员搜索的基于部分的卷积baseline
普洛斯荣获两项“数据中心绿色等级评估”5A级认证
WeChat Mini Program 30 Customizing Templates and Obtaining User Login Credentials
一文理解分布式开发中的服务治理
Docker 下 Oracle 安装与配置
第3章业务功能开发（线索关联市场活动，插入数据并查询）
随机推荐
解决报错 WARNING: IPv4 forwarding is disabled. Networking will not work.
PyQt5学习一（环境搭建）
三品牌下半年将带来多款新品，东风日产将迎来“产品大潮”
防火墙——SNAT和DNAT策略的原理及应用、防火墙规则的备份和还原
对不起，你很难赚到中年人的钱
GBASE 8s 通过临时表提升排序性能
容器网络硬核技术内幕 (小结-下)
7 行代码搞崩溃 B 站，原因令人唏嘘！
【无标题】
Verilog 加法器设计
针对自动识别大麦网滑块验证码，提出解决方案，并进行分析、总结
The cornerstone of distributed: reliability - What a tangled web we weave
sizeof和strlen的区别(strlen和sizeof的用法)
微信小程序如何开通支付功能？
Small program WeChat positioning is not accurate
使用脚本安装mysql
linux install redis using script
【AD】【持续更新ing】关于AD设计过程中一些小细节
APM电机输出逻辑(Motors类详解)
新库上线 | CnOpenData租赁和商务服务业工商注册企业基本信息数据