【数据结构】| 王道考研——树的前世今生

这篇具有很好参考价值的文章主要介绍了【数据结构】| 王道考研——树的前世今生。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一. 🦁 前言

根据王道考研数据结构总结出的知识点,以下是文章整体大纲:

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

二. 🦁 各种树的知识点

1. 树

1.1 概念

树是n个结点的有限集合,n = 0时称为空树,这是一种特殊情况。任意一棵非空树中应满足:

  • 有且仅有一个特定的称为根的节点
  • 当n>1时,其余结点可分为m个互不相交的有限集合T1、T2、T3……Tm;每个集合又称为根结点的子树。

1.2 属性

  • 结点的深度:从上往下数;

  • 结点的高度:从下往上数;

  • 树的高度:总共多少层

  • 结点的度:有几个孩子

  • 树的度:树中结点的度的最大值

1.3 常考性质

  • 结点数 = 总度数+1
  • 度为m的树和m叉树

度为m的树是一定存在一个结点,它的度为m,且树非空;m叉树是指任意结点的度≤m,可以为空;

  • 度为m的树第i层至多有m的i-1次方个结点(i>=1)
  • 【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研
  • 高度为h的m叉树至少有h个结点;高度为h,度为m的树至少有h+m-1个结点。
  • 【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

1.4 树转换成二叉树

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

树转换成二叉树的画法:

  • 在兄弟结点之间加一条线;
  • 对每个结点,只保留它与第一个孩子的连线,抹去与其他孩子的连线;
  • 以树根为轴心,顺时针旋转 45°

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

1.5 森林转换为二叉树

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

森林转换成二叉树的画法:

  • 将森林中的每棵树转换成相应的二叉树
  • 每棵树的根也可视为兄弟结点,在每棵树之间加一根连线
  • 以第一棵树的根为轴心顺时针旋转 45°

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

1.6 二叉树转换为森林

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

就是将森林转换为二叉树的逆做法

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

1.7 树的遍历

树的遍历: 用某种方式访问树中的每个结点,且仅访问一次

先序遍历:先根后子树

后根遍历:先子树后根

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

先根遍历序列为:ABEFCDG 对应二叉树中的先序遍历

后根遍历序列为:EFBCGDA 对应二叉树中的中序遍历

1.8 森林的遍历

先序遍历:先根后子树

中序遍历:先子树后根

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

先序遍历序列为:ABCDEFGHI 对应二叉树的先序遍历

中序遍历序列为:BCDAFEHIG 对应二叉树的中序遍历

2. 二叉树

二叉树是n个结点的有限集合;

2.1满二叉树

一棵高度为h,且含有2的h次方-1个结点的二叉树;

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

特点:

  • 只有最后一层有叶子结点;
  • 不存在度为1的结点;
  • 按层序从1开始编号,结点为i的左孩子结点为2i;右孩子为2i+1;结点i的父结点为i/2;

2.2 完全二叉树

当且仅当每个结点都与高度为h的满二叉树中编号为1~n的结点一一对应时,称为完全二叉树;

特点:

  • 只有最后两层可能有叶子结点;
  • 最多只有一个度为1的结点;
  • i ≤ n/2为分支结点,i > n/2为叶子结点;
  • 如果一个完全二叉树某结点只有一个孩子,则这个一定是左孩子;

2.3二叉排序树

  • 左子树的所有结点均小于根结点;
  • 右子树的所有结点均大于根结点;
  • 左子树和右子树又各是一棵二叉排序树

2.4 平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过1;

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

2.5 二叉树常考性质

  • 设非空二叉树中度为0、度为1、度为2的结点个数分别为n0、n1、n2,则n0 = n2 +1(叶子结点永远比二分支结点多一个);
  • 【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研
  • 【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研
  • 【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

2.6 二叉树存储结构

1. 顺序存储

使用数组实现顺序存储。一定要把二叉树的结点编号与完全二叉树对应起来。

  • i 的左孩子 — 2i+1
  • i 的右孩子 — 2i+2
  • i 的父节点 — 『(i-1)/2』
2. 链式存储
struct ElemType{
	int value;
}
typedef struct BiTNode{
	ElemType data;		//数据域
	struct BiTNode *lchild;		//左孩子指针
	struct BiTNode *rchild;		//右孩子指针
}BiTNode,*BiTree;

假设二叉树有n个结点,那么一定会有2n个指针,共有n+1个空链域;

二叉树操作:

// 定义一棵空树
BiTree root = null;
// 插入根节点
root = (BiTree) malloc(sizeof(BiTNode));
root->data = {1};
root->lchild = NULL;
root->rchild = NULL;

//插入新结点
BiTNode * p = (BiTNode *)malloc(sizeof(BiTNode));
p->data = {2};
p->lchild = NULL;
p->rchild = NULL;
root->lchild = p;		//作为根节点的左孩子

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

2.7二叉树的遍历

1. 先序遍历

先序遍历(preOrder)的操作过程如下:

  • 若二叉树为空,则什么也不做

  • 若二义树非空:

    • 访问根结点
    • 先序遍历左子树
    • 先序遍历右子树
    void preOrder(BiTree root){
    	if(root != null){
    		visit(root);			//访问根节点操作
    		preOrder(root->lchild);
    		preOrder(root->rchild);
    	}
    }
    
    void preOrder(BiTree root){
    	if(root != null){
    		visit(root);			//访问根节点操作
    		preOrder(root->lchild);
    		preOrder(root->rchild);
    	}
    }
    

    【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

    如下: 每个结点都会被访问三次。

    【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

2. 中序遍历

中序遍历(inOrder)的操作过程如下:

  • 若二叉树为空,则什么也不做
  • 若二义树非空:
    • 中序遍历左子树
    • 访问根结点
    • 中序遍历右子树
void inOrder(BiTree root){
	if(root != null){
		inOrder(root->lchild);
        visit(root);			//访问根节点操作
		inOrder(root->rchild);
	}
}
3. 后序遍历

后序遍历(postOrder)的操作过程如下:

  • 若二叉树为空,则什么也不做
  • 若二义树非空:
    • 后序遍历左子树
    • 后序遍历右子树
    • 访问根节点
void postOrder(BiTree root){
	if(root != null){
		postOrder(root->lchild);
		postOrder(root->rchild);
        visit(root);			//访问根节点操作
	}
}

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

应用:求树的深度

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

4. 层序遍历

算法思想:

  • 初始化一个辅助队列
  • 根结点入队
  • 若队列非空,则队头结点p出队,访问p,并将其左右孩子插入队尾(如果有的话)
  • 重复步骤3,直到队列为空。

// 层序遍历

void levelOrder(BiTree root){
	LinkQueue queue;			
	InitQueue(queue);			//初始化队列
	BiTree p;
	enQueue(root);				//根节点入队
	while(!isEmpty(queue)){		//队列不为空则循环
		deQueue(queue,p);		//队头结点出队
		visit(p);
		if(p->lchild != NULL) enQueue(queue,p->lchild);
		if(p->rchild != NULL) enQueue(queue,p->rchild);
	}
}

队列定义如下:

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

3. 线索二叉树

4. 哈夫曼树与哈夫曼编码

权: 树中结点常被赋予一个代表某种意义的数值;

结点带权路径长度: 从树的根到任意结点的路径长度与该结点上权值的乘积;

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

哈夫曼树: 带权路径长度最小的二叉树

4.1 哈夫曼树的构造

构造哈夫曼树的步骤:

  • 将所有结点分别作为仅含一个结点的二叉树;
  • 构造一个新结点,从中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和;(意思即 每次找出两个权值最小的组成一棵二叉树
  • 从中删除刚才选出的两棵树,同时将新得到的树加入森林中;
  • 重复步骤(2) 和 (3),直至剩下一棵树为止

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

  1. 【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研
  2. 求哈夫曼编码就是在哈夫曼树的基础上将左子树的路径变成0,右子树的路径变成1,如下:

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

a的哈夫曼编码为:011

b的哈夫曼编码为:10

c的哈夫曼编码为:00

d的哈夫曼编码为:010

e的哈夫曼编码为:11

  1. ecabcbbe
  2. WPL = 5×2 + 2×3 + 4×3 + 7×2 + 9×2

5. 并查集

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

5.1 初始版本

public class unionFind{
	// 初始化并查集
	public void init(int[] nums){
		Arrays.fill(nums,-1);
	}
	// 查操作:找x所属集合,返回x所属根节点
	int find(int[] nums,int x){
		while(s[x] >= 0){
            x = s[x];
        }
        return x;
	}
	// 并操作:将两个集合合并为一体
	public void union(int[] nums,int rootX,int rootY){
		if(rootX == rootY) return;
		nums[rootY] = rootX;
	}
}

5.2 优化版本

public class unionFind{
	// 初始化并查集
	public void init(int[] nums){
		Arrays.fill(nums,-1);
	}
    
	 /**
     * 并操作:使用根节点记录树的节点数目,让小树合并到大树上
     * 该方法构造的树高不超过log2n]+1
     * @param s
     * @param x
     * @param y
     */
	public void union(int[] nums,int x,int y){
        int root1 = find(nums,x);
        int root2 = find(nums,y);
		if (root1 == root2) return;
        if(s[root2]>s[root1]){      //root2节点更少(负数)
            s[root1] += s[root2];   //将小树的根节点数目加到大树根节点上
            s[root2]  = root1;      //小树合并到大树
        }else{
            s[root2] += s[root1];
            s[root1] = root2;
        }
	}
    /**
     * 查操作:压缩路径
     * @param s
     * @param x
     * @return
     */
    int find1(int[] s,int x){
        int root = x;
        while(s[root] >= 0) root = s[root];     //循环找到根节点
        while (x != root){      //压缩路径
            int t = s[x];       //t指向x的父节点
            s[x] = root;        //x直接挂到根节点下
            x = t;
        }
        return root;
    }
}

本质上表示集合的一种逻辑关系。

【数据结构】| 王道考研——树的前世今生,面经系列,数据结构,考研

三. 🦁 总结

根据王道视频课总结的数据结构知识点,对于期末考、考研、面试的宝子有帮助哦!!!文章来源地址https://www.toymoban.com/news/detail-605892.html

到了这里,关于【数据结构】| 王道考研——树的前世今生的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】24王道考研笔记——串

    串(字符串)是由零个或多个字符组成的有限序列。 子串:串中任意个连续的字符组成的子序列 主串:包含子串的串 字符在主串中的位置:字符在串中的序号 子串在主串中的位置:子串的第一个字符在主串中的位置 串的基本操作: 其中串执行比较操作时,从第一个字符开

    2024年02月15日
    浏览(63)
  • 【数据结构】24王道考研笔记——图

    图的定义 有向图以及无向图 简单图以及多重图 度 顶点-顶点间关系 连通图、强连通图 子图 (有向图也一样) 连通分量 强连通分量 生成树 生成森林 边的权、带权网/图 特殊形态的图 总结: 邻接矩阵 存储带权图(网): 对角线处可以填0或∞ 空间复杂度为O(|V| 2 )只和顶

    2024年02月17日
    浏览(47)
  • 数据结构笔记(王道考研) 第一章:绪论

    大部分内容基于中国大学MOOC的2021考研数据结构课程所做的笔记,该课属于付费课程(不过盗版网盘资源也不难找。。。)。后续又根据23年考研的大纲对内容做了一些调整,将二叉排序树和平衡二叉树的内容挪到了查找一章,并增加了并查集、平衡二叉树的删除、红黑树的内

    2024年02月14日
    浏览(47)
  • 一篇学完:王道考研408数据结构(全)

    PDF版本附在  lengyueling.cn 对应 文章结尾,欢迎下载访问交流 数据结构在学什么 如何用程序代码把现实世界的问题信息化 如何用计算机高效地处理这些信息从而创造价值 数据结构的基本概念 什么是数据: 数据是信息的载体,是描述客观事物属性的数、字符及所有能输入到

    2023年04月08日
    浏览(44)
  • 王道考研数据结构第五章知识点

    5.1.1 树的定义和基本术语   祖先节点:(对于你来说),父亲和爷爷都是祖先节点 子孙节点:对于父亲来说,父亲下面所有的节点都叫子孙节点 双亲节点(父节点):一个节点的直接前驱就是它的父节点  兄弟节点:例如二叔,三叔都是父亲的兄弟节点 堂兄弟节点:对于你来说,

    2024年02月15日
    浏览(51)
  • 【数据结构】24王道考研笔记——栈、队列和数组

    基本概念 栈是 只允许在一端进行插入或删除操作 的线性表。 栈顶:线性表允许进行插入删除的那一端 栈底:固定的,不允许进行插入删除的那一端 空栈:不含任何元素的空表 特点: 先进后出 基本操作: 常考题型: [外链图片转存失败,源站可能有防盗链机制,建议将图片

    2024年02月09日
    浏览(68)
  • 【数据结构】24王道考研笔记——树与二叉树

    树是n个结点的有限集合,n=0时,称为空树。非空树满足: 除了根节点外,任何一个结点都有且仅有一个前驱 结点的层次(深度):从上往下数 结点的高度:从下往上数 树的高度(深度):总共有多少层 结点的度:有几个孩子(分支) 树的度:各节点的度的最大值 森林:

    2024年02月13日
    浏览(46)
  • 王道计算机考研 数据结构C语言复现-第六章-队列

     这篇文章收录了王道考研课程中涉及的数据结构的所有代码。此外,本博客可能会添加一些额外的代码(不仅限于王道考研),因为408考试中会频繁考察一些冷门的知识点,所以这篇博客会涵盖所有相关的代码。这也是我数据结构的第一轮复习,希望能与大家共同进步。由

    2024年01月21日
    浏览(40)
  • 【23考研】计算机408数据结构代码题强化阶段划重点(王道书)

    视频链接:【23考研】10分钟带你整理408数据结构强化阶段代码题复习重点 本篇只适合考408的同学,请自主命题的同学自觉右上角×掉 因为王道书为了照顾自主命题的同学,所以很多算法也给出了代码实现,实际上对于考408的同学,很多代码是不需要掌握的,毕竟408的代码题没

    2024年02月15日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包