数据结构树与二叉树的实现

目录

一、普通树的存储结构

1、双亲表示法

2.孩子表示法

二、二叉树

1.二叉树的顺序存储（必须是完全二叉树，否则很浪费空间）

1）结构体

2.二叉树的链式存储

1）结构体

2）操作

1.创建一颗二叉树

2.创建一个结点

3.二叉树的前序遍历

a.递归实现

b.非递归，使用栈

4.二叉树的中序遍历

a.递归实现

b.非递归实现

5.二叉树的后序遍历

a.递归实现

b.非递归实现

6.二叉树的层次遍历：使用队列

三、线索二叉树

1.先序线索化

2.中序线索化

3.后序线索化

4.拓展，中序线索二叉树中

1）找到以p为根，第一个为中序遍历的结点，其实就是最左边的叶节点

2）找到p的后继

3）能找到后继，就可以不使用递归来遍历了，能得到中序遍历结果

4）找到以p为根结点，最后一个被中序遍历的结点，也就是p最右边的叶子结点

5）找到p的前驱

6）逆序中序遍历

5.拓展，先序二叉树中

1)寻找后继

2）不能知道找到前驱，除非能直接找到父节点，然后再讨论

6.拓展，后续二叉树中

1）寻找前驱

2）找不到后继，除非能找到父节点，再讨论

四、二叉排序树

1.结构体

2.操作函数

1）创建一颗二叉排序树

2）创建一颗二叉排序结点

3）查找关键值所对应结点

a.递归

b.非递归

4）插入关键值

5）构造一颗二叉排序树，其实就是不断插入的过程

一、普通树的存储结构

1、双亲表示法

typedef  struct{
    ElemType data;
    int parent;
}PTNode;

typedef  struct{
    PTNode nodes[MAXSIZE];
    int n;  //结点数
}PTree;

2.孩子表示法

struct CTNode{
    int child; //孩子在数组中的下标
    CTNode *next;
};

typedef  struct {
    ElemType data;
    CTNode *firstChild;
}CTBox;

typedef  struct{
    CTBox nodes[MAXSIZE];
    int n,r;//结点数、根的下标
}CTree;

二、二叉树

1.二叉树的顺序存储（必须是完全二叉树，否则很浪费空间）

1）结构体

struct TreeNode{
    ElemType value;
    bool isEmpty;
};

TreeNode t[MAXSIZE]; //一般从下标为1开始存储，为了和下标对应起来，方便查找孩子

//顺序存储初始化将所有的isEmpty变为TRUE

//左孩子为2i 右孩子为2i+1  父节点为i/2

//i>n/2就是叶子结点

2.二叉树的链式存储

1）结构体

//二叉树的链式存储
typedef  struct BiTNode{
    ElemType data;
    BiTNode *lchild,*rchild;
}BiTNode,*BTree;

2）操作

1.创建一颗二叉树

BTree CreatBTree(ElemType rootdata)
{
    BiTNode *root = (BiTNode*)malloc(sizeof(BiTNode));
    root->data=rootdata;
    root->lchild=NULL;
    root->rchild=NULL;
    return  root;
}

2.创建一个结点

BiTNode *CreatBiTNode(ElemType data)
{
    BiTNode* NewNode = (BiTNode*)malloc(sizeof(BiTNode));
    NewNode->data=data;
    NewNode->lchild=NULL;
    NewNode->rchild=NULL;
    return  NewNode;
}

3.二叉树的前序遍历

a.递归实现
void PreOrder(BTree T)
{
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}
b.非递归，使用栈
//会使用栈
void PreOrder1(BTree T)
{
    SqStack s;
    InitStack(s);
    BTree p =T;
    while (p||!StackEmpty(s)) {
        if(p){
            visit(p);
            push(s,p);
            p=p->lchild;
        }
        else {
            pop(s,p);
            p=p->rchild;
        }
    }
}

4.二叉树的中序遍历

a.递归实现
void InOrder(BTree T)
{
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}
b.非递归实现
void InOrder1(BTree T)
{
    SqStack s;
    InitStack(s);
    BTree p = T;
    while (p||!StackEmpty(s)) {
        if(p){
            push(s,p);
            p=p->lchild;
        }
        else {
            pop(s,p);
            visit(p);
            p=p->rchild;
        }
    }
}

5.二叉树的后序遍历

a.递归实现
void PostOrder(BTree T)
{
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}
b.非递归实现
void PostOrder1(BTree T)
{
    SqStack s;
    InitStack(s);
    BTree p = T;
    BTree r=NULL;
    while (p||!StackEmpty(s)) {
        if(p){
            push(s,p);
            p=p->lchild;
        }
        else {
          GetTop(s,p);
          if(p->rchild!=r&&p->rchild)
              p=p->rchild;
          else {
              pop(s,p);
              visit(p);
              r=p;
              p=NULL;
          }
        }
    }
}

6.二叉树的层次遍历：使用队列


void LevelOrder(BTree T)
{
    LinkQueue Q;
    InitLinkQueue(Q);
    BTree p;
    EnLinkQueue(Q,T);
    while (!LinkQueueEmpty(Q)) {
        DeLinkQueue(Q,p);
        visit(p);
        if(p->lchild!=NULL)
            EnLinkQueue(Q,p->lchild);
        if(p->rchild!=NULL)
            EnLinkQueue(Q,p->rchild);
    }
}

三、线索二叉树

1.先序线索化

void PreThread(ThreadTree T, ThreadTree &pre)
{
    if(T!=NULL){
        if(T->lchild==NULL){
            T->lchild=pre;
            T->ltag=1;
        }
        if(pre!=NULL and pre->rchild==NULL){
            pre->rchild=T;
            pre->rtag=1;
        }
        pre=T;
        if(T->ltag==0)
            PreThread(T->lchild,pre);
        PreThread(T->rchild,pre);

    }
}

void CreatPreThread(ThreadTree T)
{
    ThreadTree pre= NULL;
    if(T!=NULL){
        PreThread(T,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

2.中序线索化

void InThread(ThreadTree T,ThreadTree &pre)
{
    if(T!=NULL){
        InThread(T->lchild,pre);

        if(T->lchild==NULL){
            T->lchild=pre;
            T->ltag=1;
        }
        if(pre!=NULL and pre->rchild==NULL){
            pre->rchild=T;
            pre->rtag=1;
        }
        pre=T;

        InThread(T->rchild,pre);
    }

}

void CreatInThread(ThreadTree T)
{
    ThreadTree pre= NULL;
    if(T!=NULL){
        InThread(T,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

3.后序线索化

void PostThread(ThreadTree T, ThreadTree &pre)
{
    if(T!=NULL){
    PostThread(T->lchild,pre);
    PostThread(T->rchild,pre);

        if(T->lchild==NULL){
            T->lchild=pre;
            T->ltag=1;
        }
        if(pre!=NULL and pre->rchild==NULL){
            pre->rchild=T;
            pre->rtag=1;
        }
        pre=T;
    }
}

void CreatPostThread(ThreadTree T)
{
    ThreadTree pre= NULL;
    if(T!=NULL){
        PostThread(T,pre);
        pre->rchild=NULL;
        pre->rtag=1;
    }
}

4.拓展，中序线索二叉树中

1）找到以p为根，第一个为中序遍历的结点，其实就是最左边的叶节点

ThreadNode *FirstNode(ThreadNode *p)
{
    //找到最左边叶节点
    while (p->ltag==0) {
        p=p->lchild;
    }
    return  p;
}

2）找到p的后继

ThreadNode *NextNode(ThreadNode *p)
{
    if(p->rtag==0)
        return FirstNode(p->rchild);
    else {
        return p->rchild;
    }
}

3）能找到后继，就可以不使用递归来遍历了，能得到中序遍历结果

void InOrder1(ThreadTree T)
{
    for(ThreadNode *p = FirstNode(T);p!=NULL;p=NextNode(p)){
        visit_Thread(p);
    }
}

4）找到以p为根结点，最后一个被中序遍历的结点，也就是p最右边的叶子结点

ThreadNode *LastNode(ThreadNode *p)
{
    while (p->rtag==0) {
        p=p->rchild;
    }
    return  p;
}

5）找到p的前驱

ThreadNode *preNode(ThreadNode *p){
    if (p->ltag==0) {
        return LastNode(p->lchild);
    }
    else {
        return p->lchild;
    }
}

6）逆序中序遍历

void RevInOrder(ThreadTree T)
{
    for(ThreadNode *p = LastNode(T);p!=NULL;p=preNode(p)){
        visit_Thread(p);
    }
}

5.拓展，先序二叉树中

1)寻找后继

ThreadNode *NextNode_pre(ThreadNode *p)
{
    if(p->rtag==0){
        if(p->lchild!=NULL)
            return p->lchild;
        if(p->rchild!=NULL)
            return p->rchild;
    }
    else {
        return p->rchild;
    }
}

2）不能知道找到前驱，除非能直接找到父节点，然后再讨论

6.拓展，后续二叉树中

1）寻找前驱

ThreadNode *preNode_post(ThreadNode *p)
{
    if(p->ltag==1){
        return p->lchild;
    }
    else {
        if(p->rchild!=NULL)
            return p->rchild;
        else {
            return p->lchild;
        }
    }
}

2）找不到后继，除非能找到父节点，再讨论

四、二叉排序树

1.结构体

typedef  struct BSTNode{
    ElemType data;
    BSTNode *lchild,*rchild;
}BSTNode,*BSTree;

2.操作函数

1）创建一颗二叉排序树

BSTree CreatBSTree(ElemType rootdata)
{
    BSTNode *NewNode = (BSTNode*)malloc(sizeof (BSTNode));
    NewNode->data=rootdata;
    NewNode->lchild=NULL;
    NewNode->rchild=NULL;
    return  NewNode;
}

2）创建一颗二叉排序结点

BSTNode *CreatBSTNode(ElemType data)
{
    BSTNode *NewNode = (BSTNode*)malloc(sizeof (BSTNode));
    NewNode->data=data;
    NewNode->lchild=NULL;
    NewNode->rchild=NULL;
    return  NewNode;
}

3）查找关键值所对应结点

a.递归
BSTNode *BSTSearch(BSTree bt, ElemTpye key)
{
    if(bt==NULL)
        return  NULL;
    if(bt->data==key)
        return bt;
    else if (bt->data>key) {
        return BSTSearch(bt->lchild,key);
    }
    else {
        return  BSTSearch(bt->rchild,key);
    }
}
b.非递归
BSTNode *BSTSearch(BSTree bt, ElemType key)
{
    while(bt!=NULL and key!=bt->data){
        if(key<bt->data)
            bt=bt->lchild;
        else {
            bt=bt->rchild;
        }
    }
    return bt;
}

4）插入关键值

bool BSTInsert(BSTree &bt, ElemType key)
{
    if(bt==NULL){
        BSTNode *Newnode = CreatBSTNode(key);
        bt=Newnode;
        return true;
    }
    if(bt->data==key){
        return false;
    }
    else if(bt->data>key){
        return BSTInsert(bt->lchild,key);
    }
    else {
        return BSTInsert(bt->rchild,key);
    }

}

5）构造一颗二叉排序树，其实就是不断插入的过程

void CreatBST(BSTree &bt, int key[], int n)//key[] 关键字数组，n 关键字数组长度
{
    bt = NULL;
    for (int i=0;i<n;i++) {
        BSTInsert(bt,key[i]);
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/158769.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

window 搭建 MQTT 服务器并使用

window 搭建 MQTT 服务器并使用

1. 下载 安装 mosquitto 下载地址&#xff1a; http://mosquitto.org/files/binary/ win 使用 win32 看自己电脑下载相应版本&#xff1a; 一直安装&#xff1a; 记住安装路径&#xff1a;C:\Program Files\mosquitto 修改配置文件&#xff1a; allow_anonymous false 设置…
阅读更多...
Express.js 与 Nest.js对比

Express.js 与 Nest.js对比

Express.js 与 Nest.js对比 自从 Node.js 发布以来&#xff0c;Javascript 在后端领域的使用有所增加。由于 Node.js 的使用越来越多&#xff0c;每天都会有新的框架和工具发布。Express 和 Nest 是使用 Node.js 创建后端应用程序的最著名的框架之一&#xff0c;在本文中&…
阅读更多...
【入门篇】1.1 redis 基础数据类型详解和示例

【入门篇】1.1 redis 基础数据类型详解和示例

文章目录 1. 简介2. Redis基础数据类型2.1 String类型场景示例常用命令示例 2.2 List类型场景示例 2.3 Set类型场景示例 2.4 Hash类型场景示例 2.5 Sorted Set类型 3. 使用Redis存储数据的注意事项1. 内存管理2. 数据持久化3. 高并发下的性能考量 4. 参考资料 1. 简介 Redis概…
阅读更多...
app在线客服系统怎么对接

app在线客服系统怎么对接

随着移动互联网的快速发展&#xff0c;越来越多的企业开始意识到在线客服系统的重要性。而对于一个App来说&#xff0c;一个高效的在线客服系统更是必不可少的。本文将介绍如何对接App在线客服系统&#xff0c;提高用户体验和客户满意度。 一、在线客服系统的作用和优势 1. 提供…
阅读更多...
【Linux】：进程间通信

【Linux】：进程间通信

进程间通信 一.基本概念二.简单的通信-管道1.建立通信信道2.通信接口 一.基本概念 是什么 两个或多个进程实现数据层面的交互。 因为进程独立性的存在&#xff0c;导致进程间的通信成本比较高。 为什么 因为我们有多进程协同的需求。 怎么办 a.进程间通信的本质:必须让不…
阅读更多...
TMS320F28335使用多个串口时，SCIRXST Register出现错误

TMS320F28335使用多个串口时，SCIRXST Register出现错误

TMS320F28335使用多个串口时&#xff0c;SCIRXST Register出现错误 void ClearErrorState(void) {if((SciaRegs.SCIRXST.bit.FE 1)||(SciaRegs.SCIRXST.bit.BRKDT 1)){SciaRegs.SCICTL1.bit.SWRESET 0;SciaRegs.SCICTL1.bit.SWRESET 1;}if((ScibRegs.SCIRXST.bit.FE 1)||(S…
阅读更多...
反转链表（图解）

反转链表（图解）

LCR 024. 反转链表 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给定单链表的头节点 head &#xff0c;请反转链表&#xff0c;并返回反转后的链表的头节点。 样例输入 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1]示例 2&…
阅读更多...
【漏洞复现】NUUO摄像头存在远程命令执行漏洞

【漏洞复现】NUUO摄像头存在远程命令执行漏洞

漏洞描述 NUUO摄像头是中国台湾NUUO公司旗下的一款网络视频记录器&#xff0c;该设备存在远程命令执行漏洞&#xff0c;攻击者可利用该漏洞执行任意命令&#xff0c;进而获取服务器的权限。 免责声明 技术文章仅供参考&#xff0c;任何个人和组织使用网络应当遵守宪法法律&…
阅读更多...
leetcode栈和队列三剑客

leetcode栈和队列三剑客

用队列实现栈 队列是先进先出的&#xff0c;而栈是只能在栈顶进行出栈和入栈&#xff0c;那我们这道题要用队列来实现栈的话&#xff0c;这里给的思路是两个队列&#xff0c;因为两个队列的话就可以相互导数据&#xff0c;比如我们来实现这个题目的push函数&#xff0c;我们的栈…
阅读更多...
根据店铺ID/店铺链接/店铺昵称获取京东店铺所有商品数据接口|京东店铺所有商品数据接口|京东API接口

根据店铺ID/店铺链接/店铺昵称获取京东店铺所有商品数据接口|京东店铺所有商品数据接口|京东API接口

要获取京东店铺的所有商品数据&#xff0c;您需要使用京东开放平台提供的API接口。以下是一些可能有用的API接口&#xff1a; 商品SKU列表接口&#xff1a;该接口可以获取指定店铺下的所有商品SKU列表&#xff0c;包括商品ID、名称、价格等信息。您可以使用该接口来获取店铺中…
阅读更多...
springMvc中的拦截器【巩固】

springMvc中的拦截器【巩固】

先实现下想要的拦截器功能 package com.hmdp.utils;import com.hmdp.entity.User; import org.springframework.web.servlet.HandlerInterceptor;import javax.servlet.http.HttpServletRequest; import javax.servlet.http.HttpServletResponse; import javax.servlet.http.Ht…
阅读更多...
python_主动调用其他类的成员

python_主动调用其他类的成员

# 主动调用其他类的成员 # 方式一: class Base(object):def f1(self):print("5个功能") class Foo(object):def f1(self):print("3个功能")# Base.实例方法(自己传self),与继承无关Base.f1(self)obj Foo() obj.f1()print("#"*20)# 方式二:按照类…
阅读更多...
jbase虚拟M层的设计

jbase虚拟M层的设计

对于只是自己产品内部使用的打印程序来说&#xff08;比如打印收费单&#xff0c;打印结算单等&#xff09;&#xff0c;打印逻辑写在js&#xff0c;获取其他层都是没毛病的。但是对于类型检验报告这种打印来说&#xff0c;打印格式控制逻辑写在js层是百分百不行的。因为检验报…
阅读更多...
【proverif】proverif的语法-各种密码原语的介绍和具体编码

【proverif】proverif的语法-各种密码原语的介绍和具体编码

proverif-系列文章目录 【proverif】proverif的下载安装和初使用【proverif】proverif的语法-解决中间人攻击-代码详解【proverif】proverif的语法2-各种密码原语的编码 &#xff08;本文&#xff09; 文章目录 proverif-系列文章目录前言铺垫知识一、对称加密二、非对称加密三…
阅读更多...
大模型幻觉成应用落地难题 最新评测文心一言解决幻觉能力最好

大模型幻觉成应用落地难题 最新评测文心一言解决幻觉能力最好

大模型中的幻觉问题 “林黛玉倒拔垂杨柳”、“月球上面有桂树”、“宋江字武松”……相信经常使用大语言模型都会遇到这样“一本正经胡说八道”的情况。这其实是大模型的“幻觉”问题&#xff0c;是大模型行业落地的核心挑战之一。例如幻觉会影响生成内容的可靠性&#xff0c;…
阅读更多...
大数据基础设施搭建 - Hadoop

大数据基础设施搭建 - Hadoop

文章目录 一、下载安装包二、上传压缩包三、解压压缩包四、配置环境变量五、测试Hadoop5.1 测试hadoop命令5.2 测试wordcount案例5.2.1 创建wordcount输入文本信息5.2.2 执行程序5.2.3 查看结果 六、分发压缩包到集群中其他机器6.1 分发压缩包6.2 解压压缩包6.3 配置环境变量 七…
阅读更多...
TDengine Restful Authorization 自定义Token

TDengine Restful Authorization 自定义Token

Restful 接口是 TDengine 最常用的接口&#xff0c;仅次于 JDBC。TDengine 支持 HTTP 和 HTTPS&#xff0c;但通常情况下&#xff0c;大家不想搞证书&#xff0c;又在内网环境中&#xff0c;采用 HTTP 方式比较多。但 HTTP 是明文传输&#xff0c;只要抓个包就知道账号密码了。…
阅读更多...
2.4 矩阵的运算法则

2.4 矩阵的运算法则

矩阵是数字或 “元素” 的矩形阵列。当矩阵 A A A 有 m m m 行 n n n 列&#xff0c;则是一个 m n m\times n mn 的矩阵。如果矩阵的形状相同&#xff0c;则它们可以相加。矩阵也可以乘上任意常数 c c c。以下是 A B AB AB 和 2 A 2A 2A 的例子&#xff0c;它们都是 …
阅读更多...
YOLOv5项目实战（4）— 简单三步，教你按比例划分数据集

YOLOv5项目实战（4）— 简单三步，教你按比例划分数据集

前言：Hello大家好，我是小哥谈。本节课就教大家如何去按照比例去划分数据集，希望大家学习之后可以有所收获！~🌈 前期回顾： YOLOv5项目实战（1）— 如何去训练模型 YOLOv5项目
阅读更多...
万字长文：从 C# 入门学会 RabbitMQ 消息队列编程

万字长文：从 C# 入门学会 RabbitMQ 消息队列编程

RabbitMQ 简介 RabbitMQ 是一个实现了 AMQP 协议的消息队列&#xff0c;AMQP 被定义为作为消息传递中间件的开放标准的应用层协议。它代表高级消息队列协议&#xff0c;具有消息定位、路由、队列、安全性和可靠性等特点。 目前社区上比较流行的消息队列有 kafka、ActiveMQ、Pul…
阅读更多...
最新文章

Copyright @ 2022~2023