免费网站推广网站在线,金蝶erp,网站分类表,网站建设制作报价文章目录 DP 树叶的度树的度节点的层次节点的祖先节点的子孙双亲节点或父节点 树的表示孩子兄弟表示法双亲表示法树和非树树的应用 二叉树满二叉树完全二叉树推论二叉树的存储以数组的方式以链表的方式堆(Heap)堆的分类大根堆和小根堆的作用 二叉树的遍历DFS和BFS DP
动态规划… 文章目录 DP 树叶的度树的度节点的层次节点的祖先节点的子孙双亲节点或父节点 树的表示孩子兄弟表示法双亲表示法树和非树树的应用 二叉树满二叉树完全二叉树推论二叉树的存储以数组的方式以链表的方式堆(Heap)堆的分类大根堆和小根堆的作用 二叉树的遍历DFS和BFS DP
动态规划英语Dynamic programming简称 DP是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题并且记录所有子问题的结果因此动态规划方法所耗时间往往远少于朴素解法。
动态规划有自底向上和自顶向下两种解决问题的方式。自顶向下即记忆化递归自底向上就是递推。
使用动态规划解决的问题有个明显的特点一旦一个子问题的求解得到结果以后的计算过程就不会修改它这样的特点叫做无后效性求解问题的过程形成了一张有向无环图。动态规划只解决每个子问题一次具有天然剪枝的功能从而减少计算量。
树
树是所有节点的集合最上面的节点是根最下面的节点是叶。树的集合就是森林。树是递归定义的因为每一个节点都可以拆成根子树。子树又可以拆分一直拆分也就是递归了。
叶的度
该节点下面直接相连的节点个数
树的度
整个树中最大的叶的度
节点的层次
从根开始定义起根为第1层根的子节点为第2层以此类推如果一个树的根为0层的话那空树只能用-1来表示了。这就是复数了。为了方便表示让空树等于0根为1层比较好。本片所用的理论就是根为1层。
节点的祖先
从根到该节点所经分支上的所有节点
节点的子孙
以某节点为根的子树中任一节点都称为该节点的子孙
双亲节点或父节点
若一个节点含有子节点则这个节点称为其子节点的父节点 如上图A是B 的父节点
树的表示
树结构相对线性表就比较复杂了要存储表示起来就比较麻烦了实际中树有很多种表示方式 如双亲表示法孩子表示法、孩子兄弟表示法等等。我们这里就简单的了解其中最常用的孩子 兄弟表示法。
孩子兄弟表示法
typedef int DataType;
struct Node
{struct Node* _firstChild1; // 第一个孩子结点struct Node* _pNextBrother; // 指向其下一个兄弟结点DataType _data; // 结点中的数据域
};这个树的结构叫左孩子右兄弟。
什么意思呢就是如果这个节点有子节点也就是该节点的孩子就让这个节点的左孩子指针保存孩子的地址如果该节点没用孩子就指向空如果该节点的父节点除了该节点还有其他的子节点就让该节点的右兄弟指向兄弟节点。这里的兄弟只算亲兄弟也就是同一个父亲的兄弟。 对于一个正常的树状结构来说需要进一步的转换才能用左孩子右兄弟的方法来表示。就像左边这个树BCD是A的孩子A只需要指向他最左边的孩子B就行然后用B的右兄弟指针连接C再让C的右兄弟连接D。发现B没有孩子就让B的左孩子指向空。C的孩子是E就让左孩子指向E。E既没有孩子也没有兄弟左孩子和右兄弟指针都指向空。然后返回上一节点C再通过C去找DD有孩子FD的左孩子就指向FF还有一个兄弟就让F的右兄弟指向G。到这里就都连接完了其他没用的指针都指向空。
双亲表示法
因为一个父亲可以有多个孩子但是一个孩子只能有一个父亲所以可以逆向思考让孩子存父亲节点。
这里的树的结构体要全部存在数组中就是定义一个指针数组数组的每个元素都是指针每个指针指向一个树的节点。
优点是寻找父节点的题
缺点是找孩子节点要变量整个数组也就是整个树。 树和非树
子树不可相交每个子树仅有一个父节点一颗树有N个节点有N-1条边。不能有孤立的点。比如5个节点的树一定有4条边。
就是树不能成环不能有回路以后学的图的可能有回路等等
树的应用
目录树C盘D盘了文件夹就是节点文件可能是节点可能是叶子 二叉树
二叉树是特殊的树就是度为2的树。每个节点最多两个孩子也可以是空节点那就是叶子
满二叉树
就是每个节点都是满的除了叶子。根节点为1
结论一个完全二叉树的层次为k那么总的节点个数就是(2k-1),等比数列求和
每一层的节点个数就是2k-1 个 完全二叉树
完全二叉树的最底层可以不完整但是必须从左到右连续。最后一层不满但连续。满二叉树是特殊的完全二叉树。
树–二叉树–完全二叉树–满二叉树
推论
二叉树的叶子节点的个数是度为2的节点的个数1。叶节点的个数是有俩孩子节点个数的多一个。
如果一个二叉树有N个节点高度是h。
对于满二叉树来说2*h-1Nhlog2(N1)对于完全二叉树来说2*h -1-XN。0x2h-1-1) ,log2N h log2(N 1)
例题
1. 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 B
A 不存在这样的二叉树
B 200
C 198
D 199
2.在具有 2n 个结点的完全二叉树中叶子结点个数为 A
A n
B n1
C n-1
D n/2
3.一棵完全二叉树的节点数位为531个那么这棵树的高度为 B
A 11
B 10
C 8
D 12二叉树的存储
以数组的方式
从根节点开始在数组下标为0的地方然后从左到右依次填入数组对于完全二叉树来说。
若一个父节点的下标是i那么孩子的下标分别是2i1和2i2。i4.2i19,2i210。若一个子节点的下标是i那么父节点下标是i-1)/2。(6-1)/25/22. (5-1)/24/22。
以链表的方式
链表的方式大概有两种二叉链表三叉链表。
二叉链表就是有两个子节点指针的链表三叉链表就是有两个子节点child指针还有一个父节点parent指针。二叉链表应用的比较多。三叉树一般应用在平衡树红黑树等等。
// 二叉链
struct BinaryTreeNode
{struct BinTreeNode* pLeft; // 指向当前节点左孩子struct BinTreeNode* pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点的值
}
// 三叉链
struct BinaryTreeNode
{struct BinTreeNode* pParent; // 指向当前节点的父亲struct BinTreeNode* pLeft; // 指向当前节点左孩子struct BinTreeNode* pRight; // 指向当前节点右孩子BTDataType _data; // 当前节点的值
}堆(Heap)
堆就是完全二叉树用数组来储存。
堆的分类
大堆大根堆
每个父节点都大于等于子节点。左右孩子大小不规定。
小堆小根堆
每个父节点都小于等于子节点。左右孩子大小不规定。
大根堆和小根堆的作用
根堆顶是最大值或最小值。应用在堆排序中。
例题
1.下列关键字序列为堆的是:A)
A 100,60,70,50,32,65
B 60,70,65,50,32,100
C 65,100,70,32,50,60
D 70,65,100,32,50,60
E 32,50,100,70,65,60
F 50,100,70,65,60,32二叉树的遍历
由于二叉树是一个非线性结构不同于以往的单链表或者数组只能从头到尾或者从尾到头的遍历顺序。
二叉树可分为左子树、右子树、根三部分。根据三个部分的先后顺序划分有三种分法
前序先根遍历根-左子树-右子树中序中根遍历左子树-根-右子树后序后根遍历左子树-右子树-根
DFS和BFS
深度优先搜索算法英语Depth-First-SearchDFS是一种用于遍历或搜索树或图的算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止而且每个结点只能访问一次.
因发明「深度优先搜索算法」约翰 · 霍普克洛夫特与罗伯特 · 塔扬在1986年共同获得计算机领域的最高奖图灵奖。
广度优先搜索算法Breadth-First Search缩写为 BFS又称为宽度优先搜索是一种图形搜索算法。简单的说BFS 是从根结点开始沿着树的宽度遍历树的结点。如果所有结点均被访问则算法中止。
又因为二叉树结构的特殊性有层数之分根据探索的层数有两种分法深度优先遍历广度优先遍历
其中深度优先遍历就是前中后序这三种方式
广度优先遍历是层序。所谓的层序就是一层层的挨着访问。从左到右。 举个例子 前序A-B-D-NULL-NULL-E-NULL-NULL-C-NULL-NULL 一般方便表示不会写NULL也就是ABDEC. 中序NULL-D-NULL-B-NULL-E-NULL-A-NULL-C-NULL 后序NULL-NULL-D-NULL-NULL-E-B-NULL-NULL-C-A 层序A-B-C-D-E-NULL-NULL-NULL-NULL-NULL-NULL 大概是什么意思呢拿中序来说拿到这棵树第一个节点也就是根但是不会访问他的值因为中序访问就是先访问左子树对于A这棵树而言左子树是以B为根的子树但是这时候不能访问B的值因为对于B而言D才是B的左子树对于D而言左子树为空返回NULL这也就是中序第一个NULL的来源。然后返回D节点D是以D为根的子树的根D的左子树已经访问完了所以要访问D然后访问D这棵树的右子树右子树还是空返回NULL。以D为根的子树才彻底访问完毕。D又是B的左子树以B为根的子树的左子树访问完才访问根B的值。接着是B的右子树E。以E为根的子树还要先访问左子树。。。。。。。
不难发现中序是先沿着左子树这条路一直找到了D的左子树NULL才停止访问。然后返回上级D这条岔路口走右子树。再返回D的上级B岔路口走右子树。
随着程序的运行一开始就先找最深的地方也就是深度优先遍历。走到空无路可走了才退回来。
所以深度优先适合数组、图这种量大的遍历。
实现深度优先一般用递归栈。
实现广度优先用队列。
