seo网站建设时文章频率,网站刷收益是怎么做的,wordpress 主题 瀑布流,百度关键词seo年度费用二叉树遍历
所谓遍历(Traversal)是指沿着某条搜索路线#xff0c;依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一#xff0c;是二叉树上进行其它运算之基础。 从二叉树的递归定义可知#xff0c;一…二叉树遍历
所谓遍历(Traversal)是指沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问 题。 遍历是二叉树上最重要的运算之一是二叉树上进行其它运算之基础。 从二叉树的递归定义可知一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此在任一给定结点上可以按某种次序执行三个操作
⑴访问结点本身N
⑵遍历该结点的左子树L
⑶遍历该结点的右子树R。
以上三种操作有六种执行次序
NLR、LNR、LRN、NRL、RNL、RLN。
注意
前三种次序与后三种次序对称故只讨论先左后右的前三种次序。 遍历命名
根据访问结点操作发生位置命名
① NLR前序遍历(Preorder Traversal 亦称先序遍历
——访问根结点的操作发生在遍历其左右子树之前。
② LNR中序遍历(Inorder Traversal)
——访问根结点的操作发生在遍历其左右子树之中间。
③ LRN后序遍历(Postorder Traversal)
——访问根结点的操作发生在遍历其左右子树之后。
注意
由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 给出某棵树的先序遍历结果和中序遍历结果无重复值求后序遍历结果。
比如
先序序列为124536789
中序序列为425163798
方法1我们可以重建整棵树
https://blog.csdn.net/hebtu666/article/details/84322113
建议好好看这个网址对理解这个方法有帮助。 如图
然后后序遍历得出后序序列。 方法2我们可以不用重建直接得出
过程
1根据当前先序数组设置后序数组最右边的值
2划分出左子树的先序、中序数组和右子树的先序、中序数组
3对右子树重复同样的过程
4对左子树重复同样的过程 原因我们的后序遍历是左右中的也就是先左子树再右子树再根
举个例子
比如这是待填充序列 我们确定了根并且根据根和中序序列划分出了左右子树黄色部分为左子树 先处理右子树其实左右中反过来就是中右左顺着填就好了 我们又确定了右子树的右子树为黑色区域然后接着填右子树的右子树的根N)即可。 举例说明
a[]先序序列为124536789
b[]中序序列为425163798
c[]后序序列为0000000000代表未确定
我们根据先序序列知道根一定是1所以后序序列000000001
从b[]中找到1并划分数组 左子树的先序245 中序425 右子树的先序36789 中序63798 我们继续对右子树重复相同的过程 图示为当前操作的树我们是不知道这棵树的样子的我是为了方便叙述图片表达一下当前处理的位置
当前树的根一定为先序序列的第一个元素3所以我们知道后序序列000000031
我们继续对左右子树进行划分中序序列为63798我们在序列中找到2并划分为左右子树
左子树
先序序列6
中序序列6
右子树
先序序列789
中序序列798
我们继续对右子树重复相同的过程也就是如图所示的这棵树 现在我们的后序序列为000000031
这时我们继续取当前的根先序第一个元素放在下一个后序位置000000731
划分左右子树
左子树空也就是它
右子树先序89中序98也就是这个树
我们继续处理右子树先序序列为89所以根为8我们继续填后序数组000008731
然后划分左右子树
左子树先序9中序9
右子树空
对于左子树一样我们取头填后序数组000098731然后发现左右子树都为空.
我们就把这个小框框处理完了
然后这棵树的右子树就处理完了处理左子树发现为空。这棵树也处理完了。
这一堆就完了。我们处理以3为根的二叉树的左子树。继续填后序数组
000698731 整棵树的右子树处理完了左子树同样重复这个过程。
最后452698731 好累啊。。。。。。挺简单个事写了这么多。
回忆一下过程
1根据当前先序数组设置后序数组最右边的值
2划分出左子树的先序、中序数组和右子树的先序、中序数组
3对右子树重复同样的过程
4对左子树重复同样的过程
就这么简单 先填右子树是为了数组连续填充容易理解先处理左子树也可以。
最后放上代码吧
a[1,2,4,5,3,6,7,8,9]
b[4,2,5,1,6,3,7,9,8]
l[0,0,0,0,0,0,0,0,0]def f(pre,tin,x,y):#x,y为树在后序数组中对应的范围if pre[]:returnl[y]pre[0]#根postin.index(pre[0])#左子树元素个数f(pre[pos1:],tin[pos1:],xpos,y-1)#处理右子树f(pre[1:pos1],tin[:pos],x,xpos-1)#处理左子树f(a,b,0,len(l)-1)
print(l)
