【数据结构---26】树以及二叉树的基本概念

文章目录

树的概念：与树相关的基本概念:树的表示方式：二叉树：二叉树的五条特性:二叉树的存储：堆序堆的实现:调整堆序:堆的删除操作:堆的插入操作:扩容:用堆的思想进行排序TOP K问题(海量数据)二叉树的链式存储方式求二叉树的节点个数:二叉树的创建方式:二叉树的销毁方式:二叉树的拷贝:查看二叉树中的叶子节点:

树的概念：

一种非线性的数据结构,它是由n个(n>=0)有限节点组成的一个具有层次关系的集合

与树相关的基本概念:

深度:树中节点的最大层次 双亲:若一个节点含有子节点,则这个节点是这个子节点的双亲节点 子节点:一个节点含有的子树的根节点被称为这个节点的子节点 兄弟:具有相同双亲节点的被称为兄弟节点 叶节点:度为0的节点被称为叶节点

树的表示方式：

孩子表示法，双亲表示法，孩子双亲表示法，孩子兄弟表示法

二叉树：

空树，根+根的左子树+根的右子树

特殊的二叉树：

满二叉树:每一层的节点数都达到最大值,这个二叉树就是满二叉树 完全二叉树:从上之下从左至右一次填满的二叉树,不可能存在只有右孩子没有左孩子

二叉树的五条特性:

1.若规定根节点的层次为1,则一颗非空二叉树的第i层最多有2^(i-1)个节点 2.若规定只有根节点的二叉树深度为1,则深度为k的二叉树最大节点数是2^k-1 3.对任意一颗二叉树,如果其叶节点个数为n0,度为2的非叶节点个数为n2,则有n0=n2+1 4.具有n个节点的完全二叉树的深度k为log2(n+1)向上取整 5.对于有n个节点的完全二叉树,如果按照从上至下从左至右的顺序对所有节点从0进行编号 则对于序号为i的节点有: <1>.若i>0,双亲序号:(i-1)/2i=0,i为根节点编号,无双亲节点 <2>.若2i+1<n,左孩子序号:2i+1,否则无左孩子 <3>.若2i+2<n,右孩子序号:2i+2,否则无右孩子

二叉树的存储：

顺序结构：完全二叉树（基本不会增加删除） 链式结构：通过指针来表示节点与其孩子及双亲之间的关系,常用孩子表示法，孩子双亲表示法

二叉树顺序存储： 堆（是一棵完全二叉树），堆中的元素存储到一维数组中，对于任意节点如果该节点中小于（大于）其左右孩子，就把这种结构称为小堆（大堆）

堆的特性： 堆顶元素一定是堆中所有元素最大的（最小的）

堆序堆的实现:

结构类似于顺序表

调整堆序:

int child=parent*2+1；默认child标记parent的左孩子 因为完全二叉树某个节点只有一个孩子，该孩子一定是其双亲的左孩子 向下调整:(调整的是以parent为根的子树) 找出较小的孩子---左右孩子比较（左右孩子必须都存在，child+1<size） 左孩子比右孩子大的话，child+=1 双亲比较小的孩子大的话，交换双亲和孩子的顺序 更新parent=child；chil=parent*2+1； 2i+1已经大于size（数组节点个数），说明孩子不存在

创建堆的时间复杂度Nlog2(N)

堆的删除操作:

堆里没有元素不删除 有的话就删除堆顶元素----- 堆顶元素和末尾元素交换 size的值要更新-----对堆顶元素进行向下调整 AdjustDown(heapdatatype*array,heapdatatype*size,0)

堆的插入操作:

考虑空间是否放得下-----插入之后需要调整堆序-----向上调整,传的参数是孩子 孩子小于双亲,需要交换-----child=parent;parent=(child-1)/2; 循环终止条件child!=0; AdjusUp(hp->array,hp->size,hp->size-1);

扩容:

申请新空间-----拷贝元素

用堆的思想进行排序

降序是小堆,升序是大堆-----HeapSort(array,sizeof(array)/sizeof(array[0]))

TOP K问题(海量数据)

冒泡和堆排的话必须一次拿到所有的数据-----100亿数据需要40G内存空间 直接遍历K次,需要多次IO,性能太差-----堆-----取前K个数据,建小堆 从剩余的N-K个数据一次与堆顶的元素进行比较,然后选择是否替换 比堆顶元素大的替换掉,最后堆里的K个元素都是最大的

堆的应用需要做到正背如流!!!!!!!!

二叉树的链式存储方式

二叉树的遍历: 按照某种特定的规则,对二叉树中的每一个节点进行相应的操作,并且每个节点只能操作一次

前序遍历: 根--->根的左子树--->根的右子树 中序遍历: 根的左子树--->根--->根的右子树 后序遍历: 根的左子树--->根的右子树--->根

递归遍历,先遍历根,然后继续调用,传的参数是root根节点的左子树,然后继续调用,传root的右子树

求二叉树的节点个数:

(根据二叉树的概念) 空树---0个 非空就递归求解 int Getsize(Node*Root) { if(Root==NULL) { return 0; } return Getsize(Root->left)+Getsize(Root->right)+1; }

二叉树的创建方式:

索引必须给地址,因为要把索引的值带出函数外!!!!!!

创建链式二叉树—>递归跳出条件(*index<size)—>先创建根节点,在创建根的左子树,在创建根的右子树

要把创建的二叉树补全ABDCEF--->ABD###CE##F## #是我们给的空的节点的标记 修改跳出条件为(*index<size&&array[*index]!='#') `跳出条件有先后顺序,不可以写错!!!!!` 索引遇到#之后还需要往后面走 //创建根节点 //(*index++),创建根的左子树 //(*index++),创建根的右子树 递归之后其实创建的都是根节点,所有根节点创建写(*index++);

把创建的函数封装起来,方便用户调用,参数加一个无效参数,避免你设置为#,他输入$

Q:根据两个遍历的结果,要求还原出来的二叉树 A:TO DO

二叉树的销毁方式:

最后才可以销毁根节点,所以采用后序遍历规则 销毁完所有的节点之后要把Root节点置空函数体内部修改形参的值,要传形参的地址 所以销毁函数中传Root的地址!!!!!

二叉树的拷贝:

根据二叉树的概念,和创建的方法一样

查看二叉树中的叶子节点:

左右子树没有孩子的节点称为叶子节点 if(Root==NULL) { return 0; } if(Root->left==NULL&&Root->right==NULL) { return 1; } return GetLeatCount(Root->left)+GetLeatCount(Root->right);