《数据结构》-二叉树(三叉链表实现)

2023-12-10 20:30
文章标签 二叉树 实现 链表 数据结构 三叉

本文主要是介绍《数据结构》-二叉树(三叉链表实现)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

静态数组实现二叉树

二叉链表实现二叉树

三叉链表实现二叉树

线索二叉树

三叉链表存储结构

数据结构

//二叉树的三叉链表存储表示
typedef struct BiTPNode
{TElemType data;BiTPNode *parent, *lchild, *rchild; // 双亲、左右孩子指针
} BiTPNode, *BiPTree

存储示例

在这里插入图片描述

代码实现

main.c

/** Change Logs:* Date           Author       Notes* 2021-07-22     tyustli      first version*/#include "tree.h"void visitT(BiPTree T)
{if (T) // T非空printf("%d ", T->data);
}int main(int argc, char *argv[])
{printf("this bitree\r\n");int i;BiPTree T, c, q;TElemType e1, e2;InitBiTree(&T);printf("构造空二叉树后,树空否？%d(1:是 0:否)树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));e1 = Root(T);if (e1)printf("二叉树的根为: %d \n", e1);elseprintf("树空，无根\n");printf("请按先序输入二叉树(如:1 2 0 0 0表示1为根结点,2为左子树的二叉树)\n");CreateBiTree(&T);printf("建立二叉树后,树空否？%d(1:是 0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T));e1 = Root(T);if (e1)printf("二叉树的根为: %d \n", e1);elseprintf("树空，无根\n");printf("\n先序递归遍历二叉树:\n");PreOrderTraverse(T, visitT);printf("\n中序递归遍历二叉树:\n");InOrderTraverse(T, visitT);printf("\n后序递归遍历二叉树:\n");PostOrderTraverse(T, visitT);printf("\n层序遍历二叉树:\n");LevelOrderTraverse(T, visitT);
}/***************** end of file ******************/

tree.c

/** Change Logs:* Date           Author       Notes* 2021-07-22     tyustli      first version*/#include "tree.h"// 二叉树的三叉链表存储的基本操作#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样TElemType Nil = 0; // 设整型以0为空// 操作结果：构造空二叉树T
void InitBiTree(BiPTree *T)
{*T = NULL;
}// 初始条件：二叉树T存在。
// 操作结果：销毁二叉树T
void DestroyBiTree(BiPTree *T)
{if (*T) // 非空树{if ((*T)->lchild)                 // 有左孩子DestroyBiTree(&(*T)->lchild); // 销毁左孩子子树if (&(*T)->rchild)                // 有右孩子DestroyBiTree(&(*T)->rchild); // 销毁右孩子子树free(*T);                         // 释放根结点*T = NULL;                        // 空指针赋0}
}// 按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造三叉链表表示的二叉树T
void CreateBiTree(BiPTree *T)
{TElemType ch;scanf("%d ", &ch);if (ch == Nil) // 空{*T = NULL;}else{*T = (BiPTree)malloc(sizeof(BiTPNode)); // 动态生成根结点if (!*T)exit(-1);(*T)->data = ch;               // 给根结点赋值(*T)->parent = NULL;           // 根结点无双亲CreateBiTree(&(*T)->lchild);   // 构造左子树if ((*T)->lchild)              // 有左孩子(*T)->lchild->parent = *T; // 给左孩子的双亲域赋值CreateBiTree(&(*T)->rchild);   // 构造右子树if ((*T)->rchild)              // 有右孩子(*T)->rchild->parent = *T; // 给右孩子的双亲域赋值}
}// 初始条件：二叉树T存在。
// 操作结果：若T为空二叉树，则返回TRUE，否则FALSE
Status BiTreeEmpty(BiPTree T)
{if (T)return FALSE;elsereturn TRUE;
}// 初始条件：二叉树T存在。
// 操作结果：返回T的深度
int BiTreeDepth(BiPTree T)
{int i, j;if (!T)return 0; // 空树深度为0if (T->lchild)i = BiTreeDepth(T->lchild); // i为左子树的深度elsei = 0;if (T->rchild)j = BiTreeDepth(T->rchild); // j为右子树的深度elsej = 0;return i > j ? i + 1 : j + 1; // T的深度为其左右子树的深度中的大者+1
}// 初始条件：二叉树T存在。
// 操作结果：返回T的根
TElemType Root(BiPTree T)
{if (T)return T->data;elsereturn Nil;
}// 初始条件：二叉树T存在，p指向T中某个结点。
// 操作结果：返回p所指结点的值
TElemType Value(BiPTree p)
{return p->data;
}// 给p所指结点赋值为value
void Assign(BiPTree p, TElemType value)
{p->data = value;
}#if 1typedef BiPTree QElemType; // 设队列元素为二叉树的指针类型typedef struct QNode
{QElemType data;     /* 数据域 */struct QNode *next; /* 指针域 */
} QNode, *QueuePtr;typedef struct LinkQueue
{QueuePtr front; // 队头指针QueuePtr rear;  // 队尾指针
} LinkQueue;void InitQueue(LinkQueue *Q);
void DestroyQueue(LinkQueue *Q);
void ClearQueue(LinkQueue *Q);
Status QueueEmpty(LinkQueue Q);
int QueueLength(LinkQueue Q);
Status GetHead(LinkQueue Q, QElemType *e);
void EnQueue(LinkQueue *Q, QElemType e);
Status DeQueue(LinkQueue *Q, QElemType *e);
void QueueTraverse(LinkQueue Q, void (*vi)(QElemType));
void print(QElemType i);
void InitQueue(LinkQueue *Q)
{Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));if (Q->front == NULL)exit(-1);Q->front->next = NULL;
}void DestroyQueue(LinkQueue *Q)
{while (Q->front){Q->rear = Q->front->next;free(Q->front);Q->front = Q->rear;}
}void ClearQueue(LinkQueue *Q)
{QueuePtr p, q;Q->rear = Q->front;p = Q->front->next;Q->front->next = NULL;while (p){q = p;p = p->next;free(q);}
}
Status QueueEmpty(LinkQueue Q)
{if (Q.front->next == NULL)return TRUE;elsereturn FALSE;
}
int QueueLength(LinkQueue Q)
{int i = 0;QueuePtr p;p = Q.front;while (Q.rear != p){i++;p = p->next;}return i;
}
Status GetHead(LinkQueue Q, QElemType *e)
{QueuePtr p;if (Q.front == Q.rear)return ERROR;p = Q.front->next;*e = p->data;return OK;
}
void EnQueue(LinkQueue *Q, QElemType e)
{QueuePtr p;if (!(p = (QueuePtr)malloc(sizeof(QNode))))exit(-1);p->data = e;p->next = NULL;Q->rear->next = p;Q->rear = p;
}
Status DeQueue(LinkQueue *Q, QElemType *e)
{QueuePtr p;if (Q->front == Q->rear)return ERROR;p = Q->front->next;*e = p->data;Q->front->next = p->next;if (Q->rear == p)Q->rear = Q->front;free(p);return OK;
}
void QueueTraverse(LinkQueue Q, void (*vi)(QElemType))
{QueuePtr p;p = Q.front->next;while (p){vi(p->data);p = p->next;}printf("\n");
}
void print(QElemType i)
{// printf("%s ", i);
}
#endif// typedef BiPTree QElemType; // 设队列元素为二叉树的指针类型// 返回二叉树T中指向元素值为e的结点的指针
BiPTree Point(BiPTree T, TElemType e)
{LinkQueue q;QElemType a;if (T) // 非空树{InitQueue(&q);         // 初始化队列EnQueue(&q, T);        // 根结点入队while (!QueueEmpty(q)) // 队不空{DeQueue(&q, &a); // 出队，队列元素赋给aif (a->data == e)return a;if (a->lchild)              // 有左孩子EnQueue(&q, a->lchild); // 入队左孩子if (a->rchild)              // 有右孩子EnQueue(&q, a->rchild); // 入队右孩子}}return NULL;
}// 初始条件：二叉树T存在，e是T中某个结点
// 操作结果：若e是T的非根结点，则返回它的双亲，否则返回＂空＂
TElemType Parent(BiPTree T, TElemType e)
{BiPTree a;if (T) // 非空树{a = Point(T, e);            // a是结点e的指针if (a && a != T)            // T中存在结点e且e是非根结点return a->parent->data; // 返回e的双亲的值}return Nil; // 其余情况返回空
}// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：返回e的左孩子。若e无左孩子,则返回"空"
TElemType LeftChild(BiPTree T, TElemType e)
{BiPTree a;if (T) // 非空树{a = Point(T, e);            // a是结点e的指针if (a && a->lchild)         // T中存在结点e且e存在左孩子return a->lchild->data; // 返回e的左孩子的值}return Nil; // 其余情况返回空
}// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：返回e的右孩子。若e无右孩子,则返回"空"
TElemType RightChild(BiPTree T, TElemType e)
{BiPTree a;if (T) // 非空树{a = Point(T, e);            // a是结点e的指针if (a && a->rchild)         // T中存在结点e且e存在右孩子return a->rchild->data; // 返回e的右孩子的值}return Nil; // 其余情况返回空
}// 初始条件：二叉树T存在，e是T中某个结点
// 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回＂空＂
TElemType LeftSibling(BiPTree T, TElemType e)
{BiPTree a;if (T) // 非空树{a = Point(T, e);                                                // a是结点e的指针if (a && a != T && a->parent->lchild && a->parent->lchild != a) // T中存在结点e且e存在左兄弟return a->parent->lchild->data;                             // 返回e的左兄弟的值}return Nil; // 其余情况返回空
}// 初始条件：二叉树T存在，e是T中某个结点
// 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回＂空＂
TElemType RightSibling(BiPTree T, TElemType e)
{BiPTree a;if (T) // 非空树{a = Point(T, e);                                                // a是结点e的指针if (a && a != T && a->parent->rchild && a->parent->rchild != a) // T中存在结点e且e存在右兄弟return a->parent->rchild->data;                             // 返回e的右兄弟的值}return Nil; // 其余情况返回空
}// 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空
// 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点
Status InsertChild(BiPTree p, int LR, BiPTree c) // 形参T无用
{//           的原有左或右子树则成为c的右子树if (p) // p不空{if (LR == 0){c->rchild = p->lchild;if (c->rchild) // c有右孩子(p原有左孩子)c->rchild->parent = c;p->lchild = c;c->parent = p;}else // LR==1{c->rchild = p->rchild;if (c->rchild) // c有右孩子(p原有右孩子)c->rchild->parent = c;p->rchild = c;c->parent = p;}return OK;}return ERROR; // p空
}// 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1
// 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树
Status DeleteChild(BiPTree p, int LR) // 形参T无用
{if (p) // p不空{if (LR == 0) // 删除左子树ClearBiTree(&p->lchild);else // 删除右子树ClearBiTree(&p->rchild);return OK;}return ERROR; // p空
}// 先序递归遍历二叉树T
void PreOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
{if (T){Visit(T);                           // 先访问根结点PreOrderTraverse(T->lchild, Visit); // 再先序遍历左子树PreOrderTraverse(T->rchild, Visit); // 最后先序遍历右子树}
}// 中序递归遍历二叉树T
void InOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
{if (T){InOrderTraverse(T->lchild, Visit); // 中序遍历左子树Visit(T);                          // 再访问根结点InOrderTraverse(T->rchild, Visit); // 最后中序遍历右子树}
}// 后序递归遍历二叉树T
void PostOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
{if (T){PostOrderTraverse(T->lchild, Visit); // 后序遍历左子树PostOrderTraverse(T->rchild, Visit); // 后序遍历右子树Visit(T);                            // 最后访问根结点}
}// 层序遍历二叉树T(利用队列)
void LevelOrderTraverse(BiPTree T, void (*Visit)(BiPTree))
{LinkQueue q;QElemType a;if (T){InitQueue(&q);EnQueue(&q, T);while (!QueueEmpty(q)){DeQueue(&q, &a);Visit(a);if (a->lchild != NULL)EnQueue(&q, a->lchild);if (a->rchild != NULL)EnQueue(&q, a->rchild);}}
}/***************** end of file ******************/

tree.h

/** Change Logs:* Date           Author       Notes* 2021-07-22     tyustli      first version*/#include <string.h>
#include <ctype.h>
#include <malloc.h> // malloc()等
#include <limits.h> // INT_MAX等
#include <stdio.h>  // EOF(=^Z或F6),NULL
#include <stdlib.h> // atoi()
#include <math.h>   // floor(),ceil(),abs()// 函数结果状态代码
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
// #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行
typedef int Status;  // Status是函数的类型,其值是函数结果状态代码，如OK等
typedef int Boolean; // Boolean是布尔类型,其值是TRUE或FALSEtypedef int TElemType;//二叉树的三叉链表存储表示
typedef struct BiTPNode
{TElemType data;struct BiTPNode *parent, *lchild, *rchild; // 双亲、左右孩子指针
} BiTPNode, *BiPTree;void InitBiTree(BiPTree *T);
void CreateBiTree(BiPTree *T);
void DestroyBiTree(BiPTree *T);
void ClearBiTree(BiPTree *T);
Status BiTreeEmpty(BiPTree T);
int BiTreeDepth(BiPTree T);
TElemType Root(BiPTree T);
TElemType Value(BiPTree p);
void Assign(BiPTree p, TElemType value);
BiPTree Point(BiPTree T, TElemType e);
TElemType Parent(BiPTree T, TElemType e);
TElemType LeftChild(BiPTree T, TElemType e);
TElemType RightChild(BiPTree T, TElemType e);
TElemType LeftSibling(BiPTree T, TElemType e);
TElemType RightSibling(BiPTree T, TElemType e);
Status InsertChild(BiPTree p, int LR, BiPTree c);
Status DeleteChild(BiPTree p, int LR);
void PreOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
void InOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
void PostOrderTraverse(BiPTree T, void (*Visit)(BiPTree));
void LevelOrderTraverse(BiPTree T, void (*Visit)(BiPTree));/***************** end of file ******************/

makefile

objects  = main.o tree.o
obj: $(objects)cc -o obj $(objects) -lmmain.o : tree.h
tree.o : tree.h.PHONY : clean
clean :-rm obj $(objects)

这篇关于《数据结构》-二叉树(三叉链表实现)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:https://blog.csdn.net/tyustli/article/details/118958146
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/478281。

相关文章

openCV中KNN算法的实现

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库，它提供了各
阅读更多...
OpenCV图像形态学的实现

OpenCV图像形态学的实现

《OpenCV图像形态学的实现》本文主要介绍了OpenCV图像形态学的实现,包括腐蚀、膨胀、开运算、闭运算、梯度运算、顶帽运算和黑帽运算,文中通过示例代码介绍的非常详细,需要的朋友们下面随着小编来一起... 目录一、图像形态学简介二、腐蚀（Erosion）1. 原理2. OpenCV 实现三、膨胀China编程（
阅读更多...
通过Spring层面进行事务回滚的实现

通过Spring层面进行事务回滚的实现

《通过Spring层面进行事务回滚的实现》本文主要介绍了通过Spring层面进行事务回滚的实现,包括声明式事务和编程式事务,具有一定的参考价值,感兴趣的可以了解一下... 目录声明式事务回滚：1. 基础注解配置2. 指定回滚异常类型3. ​不回滚特殊场景编程式事务回滚：1. ​使用 TransactionT
阅读更多...
Android实现打开本地pdf文件的两种方式

Android实现打开本地pdf文件的两种方式

《Android实现打开本地pdf文件的两种方式》在现代应用中,PDF格式因其跨平台、稳定性好、展示内容一致等特点,在Android平台上,如何高效地打开本地PDF文件,不仅关系到用户体验,也直接影响... 目录一、项目概述二、相关知识2.1 PDF文件基本概述2.2 android 文件访问与存储权限2.
阅读更多...
使用Python实现全能手机虚拟键盘的示例代码

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景：会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作？今天我要分享的Pyth... 目录一、项目概述：不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求
阅读更多...
Spring Shell 命令行实现交互式Shell应用开发

Spring Shell 命令行实现交互式Shell应用开发

《SpringShell命令行实现交互式Shell应用开发》本文主要介绍了SpringShell命令行实现交互式Shell应用开发,能够帮助开发者快速构建功能丰富的命令行应用程序,具有一定的参考价... 目录引言一、Spring Shell概述二、创建命令类三、命令参数处理四、命令分组与帮助系统五、自定义S
阅读更多...
SpringBatch数据写入实现

SpringBatch数据写入实现

《SpringBatch数据写入实现》SpringBatch通过ItemWriter接口及其丰富的实现,提供了强大的数据写入能力,本文主要介绍了SpringBatch数据写入实现,具有一定的参考价值,... 目录python引言一、ItemWriter核心概念二、数据库写入实现三、文件写入实现四、多目标写入
阅读更多...
Android Studio 配置国内镜像源的实现步骤

Android Studio 配置国内镜像源的实现步骤

《AndroidStudio配置国内镜像源的实现步骤》本文主要介绍了AndroidStudio配置国内镜像源的实现步骤,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录一、修改 hosts，解决 SDK 下载失败的问题二、修改 gradle 地址，解决 gradle
阅读更多...
SpringSecurity JWT基于令牌的无状态认证实现

SpringSecurity JWT基于令牌的无状态认证实现

《SpringSecurityJWT基于令牌的无状态认证实现》SpringSecurity中实现基于JWT的无状态认证是一种常见的做法,本文就来介绍一下SpringSecurityJWT基于令牌的无... 目录引言一、JWT基本原理与结构二、Spring Security JWT依赖配置三、JWT令牌生成与
阅读更多...
SpringBoot实现微信小程序支付功能

SpringBoot实现微信小程序支付功能

《SpringBoot实现微信小程序支付功能》小程序支付功能已成为众多应用的核心需求之一,本文主要介绍了SpringBoot实现微信小程序支付功能,文中通过示例代码介绍的非常详细,对大家的学习或者工作... 目录一、引言二、准备工作（一）微信支付商户平台配置（二）Spring Boot项目搭建（三）配置文件
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2