计算机应用 | 古代文学 | 市场营销 | 生命科学 | 交通物流 | 财务管理 | 历史学 | 毕业 | 哲学 | 政治 | 财税 | 经济 | 金融 | 审计 | 法学 | 护理学 | 国际经济与贸易
计算机软件 | 新闻传播 | 电子商务 | 土木工程 | 临床医学 | 旅游管理 | 建筑学 | 文学 | 化学 | 数学 | 物理 | 地理 | 理工 | 生命 | 文化 | 企业管理 | 电子信息工程
计算机网络 | 语言文学 | 信息安全 | 工程力学 | 工商管理 | 经济管理 | 计算机 | 机电 | 材料 | 医学 | 药学 | 会计 | 硕士 | 法律 | MBA
现当代文学 | 英美文学 | 通讯工程 | 网络工程 | 行政管理 | 公共管理 | 自动化 | 艺术 | 音乐 | 舞蹈 | 美术 | 本科 | 教育 | 英语 |

二叉树的遍历研究及还原研究(2)

2013-08-25 01:04
导读:2还原方法的确定依据 二叉树遍历过程中,在中序序列中,根结点的左子树中的所有结点都在根结点的左侧,根结点的右子树中的所有结点都在根结点的右

  2还原方法的确定依据
  二叉树遍历过程中,在中序序列中,根结点的左子树中的所有结点都在根结点的左侧,根结点的右子树中的所有结点都在根结点的右侧,这个特点恰好与二叉排序树具有相同的性质;在读入序列时,前序序列则从左向右读,这恰好与遍历二叉树的顺序相同;后序序列从右向左读,则按照根结点、右子树、左子树的顺序还原。
  (1)设二叉树共有N个结点(N为大于1的正整数),我们按照还原方法给中序序列中的这N个结点分别赋予权值1,2…N,设根结点的权值为M(1  (2)由二叉树的遍历规则可知,权值为1,2…M-1的结点为根结点的左子树中的结点,而权值为M+1,…N的结点为根结点的右子树中的结点。
  (3)将这N个结点划分成3个子集AA=(1,2…M-1)BB=(M)CC=(M+1,…N),由于前序序列第一个读入的结点必定为二叉根的根结点,所以BB为根结点,AA集为左子树,CC集为右子树。
  (4)同理不断读入前序序列中的结点,依次递归还原BB对应的左子树和CC对应的右子树,最后将三棵子树合并成以BB为根结点、AA的根结点为BB的左子树、CC的根结点为BB的右子树的一棵二叉排序树。
  (5)同理可以得出,由中序序列和后序序还原二叉树的规则也成立。
  (6)在还原过程中,读入序列的顺序也遵循也先根结点,后子树的。
  3
  在二叉树的一些应用中,如平衡二叉树、红黑树等,常常要观察二叉树的形态,对其进行判断并调整。根据遍历序列和二叉排序树的性质快速还原出二叉树对于研究相关的问题有很大的帮助。
  
  [1]@严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1996.

上一篇:永不停息的单摆网 下一篇:没有了