目录
一、顺序存储二叉树
1.基本说明
从数据储存来看，数组储存方式和树的存储方式可以相互转换，即数组可以转换为树，树也可以转换成数组
要求:
1)下图的二叉树的结点，要求以数组的方式来存放arr : [1,2,3,4,5,6,6]
2要求在遍历数组arr时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历
顺序存储二叉树的特点:
1)顺序二叉树通常只考虑完全二叉树
2)第n个元素的左子节点为2*n+ 1
3)第n个元素的右子节点为2 *n+2
4)第n个元素的父节点为(n-1)/ 2
5) n:表示二叉树中的第几个元素(按О开始编号如图所示)
2.代码实现
需求:给你一个数组{1,2.3.4.5,6,7})，要求以二叉树前序遍历的方式进行遍历。前序遍历的结果应当为1,2,4,5,3,6,7
class ArrBinaryTree{
private int[] arr; // 储存数据结点的数组
public ArrBinaryTree(int[] arr){
super();
this.arr = arr;
}
//重载preOrder
public void preOder(){
this.preOder(0);
}
//编写一个方法，完成顺序存储二叉树的前序遍历
/**
*
* @param index 数组的下标
*/
public void preOder(int index) {
//如果数组为空，或者arr.length = 0
if (arr == null || arr.length == 0) {
System.out.println("数组为空，不能按照二叉树的前序遍历！");
}
//输出当前这个元素
System.out.println(arr[index]);
//向左递归遍历
if (index * 2 + 1 < arr.length) {
preOder(2 * index + 1);
}
//向右递归
if (index * 2 + 2 < arr.length) {
preOder(2 * index + 2);
}
}
}测试：
public static void main(String[] args) {
int[] arr = {1,2,3,4,5,6,7};
//创建一个ArrayBinaryTree
ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
arrBinaryTree.preOder(); //1,2,4,5,3,6,7
}二、线索化二叉树
- n个结点的二叉链表中含有n+1【公式2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域,存放指该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索")【类似双向链表理解】
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
- 一个结点的前一个结点，称为前驱结点
- 一个结点的后一个结点，称为后继结点
说明：
当线索化二叉树后，Node节点的属性 left 和 right ,有如下情况:
1) left 指向的是左子树，也可能是指向的前驱节点.比如①节点 left 指向的左子树,而⑩节点的 left 指向的就是前驱节点。
2) right指向的是右子树，也可能是指向后继节点，比如①节点 right 指向的是右子树，而⑩节点的right 指向的是后继节点。
代码实现
1.在节点类中增加新的节点属性（以及对应的get 和 set 方法）
private HeroNode left; //默认为null
private HeroNode right; //默认为null
//说明：
//1.如果leftType = 0 表示指向的式左子树
//2.如果LeftType = 1 编辑室指向前驱节点
//rightType同理
private int LeftType;
private int RightType;2.再在定义二叉树时，实现二叉树的线索化
1）首先定义一个前驱指针
//为了实现线索化，需要创建给指向当前结点的前驱节点的指针
//pre总是保留前一个结点
private HeroNode preNode = null;2）编写对二叉树进行线索化（中序）
public void threadeNodes(HeroNode node){ //对节点进行线索化
//1.判断当前结点是否为空,若为空，则无法线索化
if(node == null){
return;
}
//2.1 先线索化左子树
threadeNodes(node.getLeft());
//2.2 再线索化当前节点【!!!】
//2.2.1处理当前节点的前驱节点
if (node.getLeft() == null){
//使当前结点的左指针指向前驱节点
node.setLeft(preNode);
//修改当前节点的left指针类型,指向前驱节点的类型
node.setLeftType(1);
}
//2.2.2 处理后序结点
if (preNode != null && preNode.getRight() == null){
//使当前结点的左指针指向前驱节点
preNode.setRight(node);
//修改当前节点的left指针类型,指向前驱节点的类型
preNode.setRightType(1);
}
//!!!2.2.3 每处理一个结点后，让当前节点是下一个结点的前驱系欸但
preNode = node;
//2.3 最后线索化右子树
threadeNodes(node.getRight());
}3.在测试调用threadeNodes方法时，为了方便，可以重载threadeNodes方法，从而直接使用结点对象调用该方法
//重载 threadeBinaryNode 方法
public void threadeNodes() {
this.threadeNodes(root);
}三、遍历线索化二叉树
可以直接在定义二叉树类中实现
//遍历线索化二叉树的方法
public void TreadeList(HeroNode heroNode){
//定义一个变量，临时存储当前遍历的结点
HeroNode node = root;
while (node != null){
//循环找到 LeftType = 1 的结点
//后面随着遍历而变化,因为当 LeftType = 1 的时候，说明该结点按照线索化处理后的有效结点
while(node.getLeftType() == 0){
node = node.getLeft();
}
//打印当前结点
System.out.println(node);
//如果当前结点的右指针指向的是后继结点，则说明是该结点的父结点
while(node.getRightType() == 1){
node = node.getRight();
System.out.println(node);
}
//不等于1时就替换遍历结点
node = node.getRight();
}
}可以debug来做一个解析过程。
本文含有隐藏内容，请 开通VIP 后查看