树和二叉树的运行与操作
创建,遍历,转化,复制,删除等。
遍历:前中后三种顺序的遍历,已经是各数据结构与算法教程的最基础内容,在此不重复。
创建:大多数据结构教程当中的二叉树创建程序,都是采用的递归方式,递归方式创建的二叉树与遍历的过程相似,所创建的二叉树,也是采用左右子节点方式,后续进行遍历操作十分方便。
转化:直觉上,最简单的二叉树存储方式。
首先,提供个满二叉树大小的数组,然后其中数值按完全二叉树存储。显然,此种顺序存储方法:第i号(这里编号指对应的完全二叉树的位序)结点的左右孩子一定保存在第2i及2i+1号单元中。故此,为兼顾存储的直观与遍历等操作的方便,从顺序数组向左右子节点存储方式的转化也就十分重要。
1-转化方法
分为几个步骤:
(1)准备原始数组
(2)分析数组中的有效值,对应二叉树节点非空;
(3)创建二叉树节点;
(4)计算除最后一层子节点外,构造节点间父子关系时的循环次数;
(5)构造二叉树节点间的父子关系;
(6)确实二叉树根节点;