上期的答案在最下面，没有看过的小伙伴可以戳这里:COMP预习课（基础算法与数据结构）
Part3
不熬夜教育
本期大纲Tree(树)树是什么树的概念树的遍历Tree(树)什么是树树这个数据结构很像我们生活中的树,想象一颗真正的树在每个树枝分叉处都存上一个node,就是我们的数据结构了，我们可以从树根开始顺着枝干找到每一个节点以及最外层的叶片
树的概念父节点每个非根节点都会有一个更靠近根部的父节点，上上图中，B的父节点是A,F的父节点是B。
子节点每个节点会有零到多个的子节点，A的子节点是B,C,D，C的子节点是G和H，D有零个节点
我们通常把一个树的节点分成三类:root(根),Internalnode(内部节点)，External/leafnode(外部节点)
root(根)没有父节点的节点，例如A
Internalnode(内部节点)有子节点的节点，例如A，B，C，F
External/leafnode(外部节点)没有子节点的节点，例如：E，D，I，J，K，G，H
Ancestors（祖先节点）
找到一个节点的祖先节点和看家谱是一样的，节点X的祖先节点=节点X的父节点+节点X的父节点的祖先节点，例如图中F的祖先节点是B，A
Descendants（后裔节点）节点X的后裔节点=节点X的子节点+节点X的子节点的后裔节点，例如图中B的后裔节点是E，F，I，J，K
Depthofanode（一个点的深度）该节点祖先节点数量
LevelE，F，G，H都在同意level，因为他们的深度都是2，所以他们在level2中
Heightofatree(树的高度)最大深度，图中的树的高度是3
树的遍历我们讲基于DFS（深度优先）对普通的树的几种遍历
pre-orderdefpre_order(v)visit(v)foreachchildwofvpre_order(w)
这样遍历的顺序就是:A,B,E,F,I,J,K,C,G,H,D
post-orderdefpre_order(v)foreachchildwofvpre_order(w)visit(v)
这样遍历的顺序就是E,I,J,K,F,B,G,H,C,D,A
试着做一做写一个单个树节点的结构，用任意语言的class表示出来classnode:思考树储存什么数据比较好上期答案想想stack和queue分别有什么用途
stack和queue都适用于储存具有不同优先级的元素，一些交易软件会用queue来储存买卖的请求，dequeue的永远是优先级最高的请求。
用两个queue来实现一个stack的功能，用伪代码简洁的表示出你的逻辑。defpush(e):queue1.enqueue(e)defpop():foriin(0,queue1.size()-2):queue2.enqueue(queue1.dequeue())r=q1.dequeue()foriin(0,queue2.size()):queue1.enqueue(queue2.dequeue())returnr预览时标签不可点收录于话题#个上一篇下一篇