首页 > 其他分享 >数据结构-树与二叉树

数据结构-树与二叉树

时间:2024-08-08 21:59:53浏览次数:18  
标签:pre 结点 遍历 中序 BT 二叉树 数据结构

王道章节内容

知识框架

考纲内容

引入

因为要用到查找的部分知识,故简要引入。

要从数据中找到一个值,有静态查找(未发生插入和删除)和动态查找(发生插入和删除)两种方式。而静态查找有两种方法,一种是逐个按顺序查找,一种是高中就有介绍的二分查找

自然而然,我们可以类似地有这样子的判定树:

ASL

“平均搜索长度”(Average Search Length),指在树中找到一个元素所需的平均比较次数。

 这不禁启发我们,在计算机有没有类似的存储数据的方式?


定义

补充:

树与非树的判定

森林的定义

森林

  • 森林是一组互不相交的树的集合。
  • 森林中的每一棵树都是独立的,即不存在任何两棵树之间有边相连的情况。
  • 森林中的所有节点和边构成了一个更大的图,但这个图本身不是一棵树,因为它包含了多棵树。

基本术语

存储结构

那么, 这样的结构在计算机中该如何表示呢?

双亲表示法

/* 树的双亲表示法结点结构定义 */
#define MAX_TREE_SIZE 100

typedef int TElemType;				/* 树结点的数据类型,目前暂定为整型 */

typedef struct PTNode				/* 结点结构 */
{
	TElemType data;					/* 结点数据 */
	int parent;						/* 双亲位置 */
} PTNode;

typedef struct						/* 树结构 */
{
	PTNode nodes[MAX_TREE_SIZE];	/* 结点数组 */
	int r,n;						/* 根的位置和结点数 */
} PTree;

关于 nodes[MAX_TREE_SIZE] 的解释

  • 数组定义PTNode nodes[MAX_TREE_SIZE]; 定义了一个固定大小的数组,该数组可以容纳最多 MAX_TREE_SIZE 个 PTNode 类型的结构体。数组的大小在编译时确定,不能更改。
  • 数组元素: 数组中的每个元素都是一个 PTNode 类型的结构体实例,因此每个元素都有自己的 data 和 parent 成员变量。
  • 数组用途: 这个数组用于存储树的所有节点。每个节点都有一个对应的索引位置,这个位置就是节点在数组中的位置。例如,根节点可能位于数组的第一个位置(假设从 0 开始计数),而其他节点根据它们在树中的位置和关系存储在数组的不同位置上。

孩子表达法

有两种“孩子法”:一种“指针域个数 = 树的度”,另一种“指针域个数 = 结点的度”(图中给出的是后者),前者会造成空间浪费,后者则需要区分“长子”与“兄弟”,这就要求有不同的结点结构:

/* 树的孩子表示法结构定义 */
#define MAX_TREE_SIZE 100

typedef int TElemType;			/* 树结点的数据类型,目前暂定为整型 */

typedef struct CTNode			/* 孩子结点 */
{
	int child;	
	struct CTNode *next;	
} *ChildPtr;

typedef struct 					/* 表头结构 */
{
	TElemType data;	
	ChildPtr firstchild;	
} CTBox;

typedef struct	     			/* 树结构 */
{
	CTBox nodes[MAX_TREE_SIZE];	/* 结点数组 */
	int r,n;					/* 根的位置和结点数 */
} CTree;

 这里涉及到的struct用法:

当你使用 typedef 关键字与 struct 结合时,可以简化结构体的声明和使用。typedef 允许你为现有的类型定义一个新的名称,这样可以让你避免在每次声明结构体变量时都要写出完整的 struct 关键字和结构体定义。

struct CTNode *next;

这一行代码定义了一个结构体成员,这个成员是一个指向 CTNode 类型结构体的指针,通常用于链表中的节点连接。这里的 next 指向下一个 CTNode 类型的节点。

孩子兄弟表达法

有个人由根结点和子结点的关系得到启发,提出来“最左长子与最亲兄弟”的表示方法,如下图所示:

/* 树的孩子兄弟表示法结构定义 */
typedef struct CSNode
{
	TElemType data;	
	struct CSNode *firstchild,*rightsib;	
} CSNode,*CSTree;

二叉树表达法

当然,在树中识别“儿子”和“兄弟”还是有点烦的,我们考虑把它转个角度,变为“左和右”

这就是二叉树的由来。

树、森林与二叉树的转换

树转换成二叉树

森林转换为二叉树

森林转换为二叉树

树、森林的遍历

树的遍历

森林的遍历

遍历关系


二叉树

定义

特殊二叉树

完全二叉树的判定:

判定原则:按层次从左到右编号,若出现空档,则不为完全二叉树。

性质

  1. 叶 = 支 + 1;
  2. k 层 <= 2^(k - 1);
  3. 树最多 2^h - 1;
  4. 太多不记;
  5. log2(n + 1)or log2(n)+1 。

抽象数据类型定义

顺序存储结构

链式存储结构

//结果代码实现
typedef struct BiTNode  /* 结点结构 */
{
   TElemType data;		/* 结点数据 */
   struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;

 重要结论:在含有 n 个结点的二叉链表中,含有 n + 1 个空链域,验证如下:

遍历

二叉树的遍历

  • 指按照某种次序依次访问二叉树中的所有结点;
  • 使得每个结点被访问一次且仅被访问一次

递归算法

遍历操作往往要设计到“递归”,这里贴一个链接帮助理解:http://t.csdnimg.cn/wraXX 

递归“三要素”:

  1. 定义函数功能;
  2. 设定结束条件( if 语句);
  3. 寻找递进关系( return )。

先序遍历(根左右)

遍历过程为: ① 访问根结点; ② 先序遍历其左子树; ③ 先序遍历其右子树。

void PreOrderTraversal( BinTree BT )        //函数定义
{
     if( BT ) {                            //结束条件
         printf(“%d”, BT->Data);

         PreOrderTraversal( BT->Left );    //递进
         PreOrderTraversal( BT->Right );
     }
}

中序遍历(左根右)

遍历过程为: ① 中序遍历其左子树; ② 访问根结点; ③ 中序遍历其右子树。

void InOrderTraversal( BinTree BT )
{
     if( BT ) {
         InOrderTraversal( BT->Left );
         printf(“%d”, BT->Data);    //访问根结点
     InOrderTraversal( BT->Right );
     }
}

后序遍历(左右根)

遍历过程为: ① 后序遍历其左子树; ② 后序遍历其右子树; ③ 访问根结点。

void PostOrderTraversal( BinTree BT )
{
     if( BT ) {
         PostOrderTraversal( BT->Left );
         PostOrderTraversal( BT->Right);
         printf(“%d”, BT->Data);
     }
}

非递归算法

先序、中序和后序遍历过程:遍历过程中经过结点的路线一 样,只是访问各结点的时机不同。

图中,在从入口到出口的曲线上用三角形、圆形和方形三种符号,分别标记出了先序、中序和后序访问各结点的时刻。

使用非递归算法,最关键的是什么时候访问根结点,有时候需要“摁住”不访问或者先进行访问,自然而然我们可以想象到栈的知识。(回顾:http://t.csdnimg.cn/wjT1k

中序遍历:

算法思路:

  1. 遇到一个结点,就把它压栈,并去遍历它的左子树;
  2. 当左子树遍历结束后,从栈顶弹出这个结点并访问它;
  3. 然后按其右指针再去中序遍历该结点的右子树。
void InOrderTraversal( BinTree BT )
{ BinTree T=BT;
    Stack S = CreatStack( MaxSize );     /*创建并初始化堆栈S*/
    while( T || !IsEmpty(S) ){
         while(T){        /*一直向左并将沿途结点压入堆栈*/
             Push(S,T);
             T = T->Left;
         }
         if(!IsEmpty(S)){
             T = Pop(S);     /*结点弹出堆栈*/
             printf(“%5d”, T->Data);     /*(访问)打印结点*/
             T = T->Right;     /*转向右子树*/
         }
    }
}

先序遍历:

void LeftOrderTraversal( BinTree BT )
{ BinTree T BT;
    Stack S = CreatStack( MaxSize );     /*创建并初始化堆栈S*/
    while( T || !IsEmpty(S) ){
         while(T){     /*一直向左并将沿途结点压入堆栈*/
             printf(“%5d”, T->Data);     /*(访问)打印根结点*/
             Push(S,T);
             T = T->Left;
         }
         if(!IsEmpty(S)){    
             T = Pop(S);     /*结点弹出堆栈*/
             T = T->Right;     /*转向右子树*/
         }
    }
}

层次遍历

队列回顾:http://t.csdnimg.cn/wjT1k

 算法思路:

  1. 先根节点入队;
  2. 从队列中取出一个元素;
  3. 访问该元素所指结点;
  4. 若该结点的左右非空, 则将其左右指针顺序入队。
void LevelOrderTraversal ( BinTree BT )
{ Queue Q; BinTree T;
    if ( !BT ) return;     /* 若是空树则直接返回 */
    Q = CreatQueue( MaxSize );     /*创建并初始化队列Q*/
    AddQ( Q, BT );
    while ( !IsEmptyQ( Q ) ) {
        T = DeleteQ( Q );
        printf(“%d\n”, T->Data);     /*访问取出队列的结点*/
        if ( T->Left ) AddQ( Q, T->Left );
        if ( T->Right ) AddQ( Q, T->Right );
    }
}

应用-二叉树构造

问题:已知四种遍历序列中的最少几种,才能确定唯一的一棵树?

答案:最少两种,且必须要有中序遍历。

先序和中序:

(ppt这张图很好,帮助理解) 

后序和中序:

层序与后序:

线索二叉树

定义

前驱与后继:类似双向链表里的 pre 和 next;

左右孩子:左子树根和右子树根。

typedef char TElemType;
typedef enum {Link,Thread} PointerTag;	/* Link=0表示指向左右孩子指针, */
										/* Thread=1表示指向前驱或后继的线索 */
typedef  struct BiThrNode	/* 二叉线索存储结点结构 */
{
	TElemType data;	/* 结点数据 */
	struct BiThrNode *lchild, *rchild;	/* 左右孩子指针 */
	PointerTag LTag;
	PointerTag RTag;		/* 左右标志 */
} BiThrNode, *BiThrTree;

} BiThrNode, *BiThrTree;: 结束BiThrNode结构体的定义,并定义BiThrTree为指向BiThrNode类型的指针,通常用作树根节点的指针。

enum 是 C 语言中的一个关键字,用于定义枚举类型。枚举类型是一种用户定义的类型,它由一组命名的整数常量组成,这些常量通常用来表示一组相关的值。枚举类型提供了一种更加清晰的方式来处理一组固定的选项,而不是直接使用整数值 。用法示例如下: 

enum enumeration_name {
    enumerator1,
    enumerator2,
    ...
};

 每个 enumerator 都是一个标识符,它代表一个整数值。默认情况下,第一个枚举器的值是 0,后续的枚举器的值依次递增 1。

构造

中序线索二叉树

/* 中序遍历进行二叉树线索化 */
void InThread(ThrTree &p, ThrTree &pre)
{ 
	if(p)
	{
		InThread(p->lchild,pre); /* 递归,左子树线索化 */
		if(!p->lchild) /* 当前结点左子树为空 */
		{
			p->LTag=1; /* 前驱线索 */
			p->lchild=pre; /* 左孩子指针指向前驱 */
		}
		if(pre->rchild && !pre->Rchild) /* 前驱结点非空且其右子树为空 */
		{
			pre->RTag=1; /* 后继线索 */
			pre->rchild=p; /* 前驱右孩子指针指向后继(当前结点p) */
		}
		pre=p; /* 保持pre指向p的前驱 */
		InThread(p->rchild); /* 递归,右子树线索化 */
	}
}
//中序遍历建立线索二叉树
void CreatInThread(ThreadTree T){
    ThreadTree pre=NULL;
    if(T!=NULL){    //非空二叉树,线索化
        InThread(T,pre);
        pre->rchild = NULL;    //处理最后一个结点
        pre->Rtag = 1;
    }
}

遍历

中序线索二叉树

不带头结点:

对于不带头结点的中序线索二叉树,其特点是:

  1. 每个叶子节点的左右指针可能被用作线索。
  2. 每个非叶子节点的左指针指向其左孩子或者指向其中序前驱。
  3. 每个非叶子节点的右指针指向其右孩子或者指向其中序后继。

​​​​​​​

算法步骤:

  1. 初始化:设置一个指针current指向根节点,并设置一个指针pre用于保存上一个访问过的节点。
  2. 寻找最左下节点:如果current的左子树存在且不是线索,则递归地向左移动直到找到最左下的节点。
  3. 访问节点:当current不再有左子树时,访问current节点,并将pre指向current
  4. 处理右子树:如果current的右子树存在且不是线索,则重复步骤2;否则,继续到下一个节点(即中序后继)。
  5. 重复步骤3和4:直到current为空。

懒得打又没得找哈哈:

带头结点:

/* 中序遍历二叉线索树T(头结点)的非递归算法 */
Status InOrderTraverse_Thr(BiThrTree T)
{ 
	BiThrTree p;
	p=T->lchild; /* p指向根结点 */
	while(p!=T)
	{ /* 空树或遍历结束时,p==T */
		while(p->LTag==Link)
			p=p->lchild;
		if(!visit(p->data)) /* 访问其左子树为空的结点 */
			return ERROR;
		while(p->RTag==Thread&&p->rchild!=T)
		{
			p=p->rchild;
			visit(p->data); /* 访问后继结点 */
		}
		p=p->rchild;
	}
	return OK;
}

先序和后序线索二叉树


树与二叉树的应用

哈夫曼树

引入

那么,怎么提高查找效率,降低这个数呢?我们考虑先判定比例相对高的:

定义

特点

构造 

应用-哈夫曼编码

并查集

定义

存储结构

基本实现

实现的优化

标签:pre,结点,遍历,中序,BT,二叉树,数据结构
From: https://blog.csdn.net/weixin_73417081/article/details/140953121

相关文章

  • C++ 根据层序遍历数组 构造二叉树
    说明该层序遍历数组中空节点会使用-1代替,即该层序遍历数组可以理解为一个完全二叉树代码利用队列实现左右子节点的存储,每次通过获取队列头部元素即为当前头节点,然后在数组中i和i+1对应该头结点下的左右子节点,如果不为-1,那么说明可以入队。structTreeNode{intval;Tree......
  • 【探索数据结构与算法】——深入了解双向链表(图文详解)
    目录一、双向链表的基本概念 ​​​二、双向链表的结构三、双向链表的基本操作实现方法 1.双向链表的初始化2.双向链表的头插3.双向链表的尾插6.查找节点7.在指定位置之前插入节点8.删除指定位置节点9.打印链表数据  10.双向链表销毁四、完整代码实现 LIst.h......
  • LeetCode144 二叉树的前序遍历
    前言题目:144.二叉树的前序遍历文档:代码随想录——二叉树的递归遍历编程语言:C++解题状态:基础知识不了解思路两种思路,第一是递归。递归算法有三个要素。每次写递归,都按照这三要素来写!确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就......
  • 【数据结构】汇总五、树
    一、树Tree【注意】本章是树的知识点汇总,全文6万多字,含有大量代码和图片,建议点赞收藏(doge.png)!!文章目录一、树Tree1.逻辑结构1.1定义1.2术语1.2.1结点之间的关系描述1)亲戚描述2)路径和路径长度1.2.2结点&树的属性描述1)层次2)高度3)==度==1.2.3有序树&无序树1.2.4森林1.......
  • 数据结构 分块 & 莫队
    分块一种优化暴力的思想。通常是将原数据划分成适当块(一般为\(\sqrt{n}\)),对每块数据进行预处理,进而达到比暴力更优的时间复杂度。划分确定块长后,一般需要开两个数组存储每一块的右边界与原数据所属块序号,更加方便后续操作。intsq=sqrt(n);for(inti=1;i<=sq;i++)ed[i]=n/......
  • 二叉树的递归套路
    二叉树的递归套路二叉树结构二叉树是一个将数据组织成头尾相连的特殊链表,每一个数据单元与链表一样有一个指向其的指针,但与链表不同的是其可以有两个指向其他单元的指针,分别是其左孩子与右孩子。采用该这种结构,最终数据的呈现形式会与“链”不一样,而呈现出了一种树的结构。对......
  • 算法与数据结构——初识
    算法初识算法定义:算法(algorithm)是在有限时间内解决特定问题的一组指令或操作步骤,它具有以下特性。问题是明确的,包含清晰的输入和输出定义。具有可行性,能够在有限步骤、时间和内存空间完成。各步骤都有确定的定义,在相同的输入和运行条件下,输出始终相同。数据结构定义:数据......
  • 重学数据结构
    重学数据结构了解不同的数据存储类型线性表顺序表:顺序表是线性表的一种物理存储结构,它将元素存储在一块连续的内存空间中。每个元素占用固定大小的空间,并通过下标(或索引)来唯一确定其位置。访问、插入和删除操作的时间复杂度主要取决于操作的位置和数组的实现方式。具体特点......
  • C语言菜鸟入门·数据结构·链表超详细解析
     目录1. 单链表1.1 什么是单链表1.1.1  不带头节点的单链表1.1.2 带头结点的单链表1.2 单链表的插入1.2.1 按位序插入(1)带头结点(2)不带头结点1.2.2 指定结点的后插操作1.2.3 指定结点的前插操作1.3 单链表的删除1.3.1 按位序删除1.3.2 指......
  • Java数据结构 | 二叉树基础及基本操作
    二叉树一、树型结构1.1树的概念1.2关于树的一些常用概念(很重要!!!)1.3树的表示形式1.4树的应用二、二叉树2.1二叉树的概念2.2两种特殊的二叉树2.3二叉树的性质2.4二叉树的存储2.5二叉树的基本操作2.5.1代码说明2.5.2二叉树的遍历2.5.3二叉树的基本操作1、获取树......