二叉树----顺序二叉树、线索二叉树
1、顺序二叉树
1.1、 顺序二叉树的特点
特点
-
顺序二叉树通常只考虑完全二叉树
-
第 n个元素的左子节点为 2 × n + 1
-
第 n个元素的右子节点为 2 × n + 2
-
第 n个元素的父节点为(n-1) ÷2
其中n 表示二叉树中的第几个元素(从0开始编号)
2.2、 顺序二叉树代码实现
注意点：和遍历二叉树类似、不同的地方，是递归的条件变成了2n + 1等，还要注意判断，防止在2n+1的时候，数组越界，所以要加上判断语句
class ArrBinaryTree {
int[] arr;
final int step = 2;
public ArrBinaryTree(int[] arr) {
this.arr = arr;
}
/**
* 数组的前序遍历
*/
public void preTraverse() {
preTraverse(0);
}
/**
* 数组的前序遍历
* home.php?mod=space&uid=952169 index 遍历到的数组元素下标
*/
private void preTraverse(int index) {
if(arr == null || arr.length == 0) {
System.out.println("数组为空！");
return;
}
System.out.print(arr[index] + " ");
//向左递归
if((index * step) + 1 < arr.length) {
preTraverse((index * step) + 1);
}
//向右递归
if((index * step) + 2 < arr.length) {
preTraverse((index * step) + 2);
}
}
public void midTraverse() {
midTraverse(0);
}
private void midTraverse(int index) {
if(arr == null || arr.length == 0) {
System.out.println("数组为空!");
}
//左递归
if((index * step) + 1 < arr.length) {
midTraverse((index * step) + 1);
}
System.out.print(arr[index] + " ");
//右递归
if((index * step) + 2 < arr.length) {
midTraverse((index * step) + 2);
}
}
public void lastTraverse() {
lastTraverse(0);
}
private void lastTraverse(int index) {
if(arr == null || arr.length == 0) {
System.out.println("数组为空!");
}
//左递归
if((index * step) + 1 < arr.length) {
lastTraverse((index * step) + 1);
}
//右递归
if((index * step) + 2 < arr.length) {
lastTraverse((index * step) + 2);
}
System.out.print(arr[index] + " ");
}
}
2、线索化二叉树
2.1、线索化二叉树的来源
因为一般的二叉树，叶子节点的左右指针都为空，这样就会造成空间的浪费。为了减少浪费，便有了线索化二叉树
2.2、线索化二叉树的特点
- n个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序(前序、中序、后序)下的前驱和后继结点的指针
- 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树
- 根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
- 如果一个节点已经有了左右孩子节点，那么该节点就不能被线索化了，所以线索化二叉树后，节点的left和right有如下两种情况
- left可能指向的是左孩子节点，也可能指向的是前驱节点
- right可能指向的是右孩子节点，也可能指向的是后继节点
2.3、线索化二叉树的问题解决
因为left和right可能指向左右节点，也可能指向前驱、后继节点，所以为了区分，给节点加上标志位
2.3、线索化二叉树代码实现
class ThreadedBinaryTree {
private Student root;
/**
* 指向当前节点的前一个节点
*/
private Student pre;
public void setRoot(Student root) {
this.root = root;
}
/**
* 中序线索化
* @param node 当前节点
*/
private void midThreaded(Student node) {
if(node == null) {
return;
}
//左线索化
midThreaded(node.getLeft());
//线索化当前节点
//如果当前节点的左指针为空，就指向前驱节点，并改变左指针类型
if(node.getLeft() == null) {
node.setLeft(pre);
node.setLeftType(1);
}
//通过前驱节点来将右指针的值令为后继节点
if(pre != null && pre.getRight() == null) {
pre.setRight(node);
pre.setRightType(1);
}
//处理一个节点后，让当前节点变为下一个节点的前驱节点
pre = node;
//右线索化
midThreaded(node.getRight());
}
public void midThreaded() {
midThreaded(root);
}
/**
* 遍历线索化后的二叉树
*/
public void midThreadedTraverse() {
//暂存遍历到的节点
Student tempNode = root;
//非递归的方法遍历，如果tempNode不为空就一直循环
while(tempNode != null) {
//一直访问二叉树的左子树，直到某个节点的左子树指向前驱节点
while(tempNode.getLeftType() != 1) {
tempNode = tempNode.getLeft();
}
//找到了第一个节点
System.out.println(tempNode);
//再访问该节点的右子树，看是否保存了后继节点
//如果是，则打印该节点的后继节点信息
while(tempNode.getRightType() == 1) {
tempNode = tempNode.getRight();
System.out.println(tempNode);
}
tempNode = tempNode.getRight();
}
}
}
@Data
class Student {
private int id;
private String name;
private Student left;
private Student right;
/**
* 左、右指针的类型，0-->指向的是左右孩子，1-->指向的是前驱、后续节点
*/
private int leftType = 0;
private int rightType = 0;
public Student(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "Student{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
}
| 
发表于 2021-3-25 21:20
|
发表于 2021-3-26 13:58
