文章目录
数据结构之顺序储存二叉树1. 顺序储存二叉树1.1 顺序存储二叉树的概念1.2 顺序存储二叉树的特点☆1.3 顺序存储二叉树遍历1.3.1 代码实现
2. 线索化二叉树2.1 线索二叉树应用案例2.2 代码实现2.2.1 `HeroNode` 部分2.2.2 `ThreadedBinaryTree` 部分2.2.3 测试
☆
数据结构之顺序储存二叉树
1. 顺序储存二叉树
1.1 顺序存储二叉树的概念
从数据存储来看，数组存储方式和树的存储方式可以相互转换，即 数组可以转换成树， 树也可以转换成数组。
1.2 顺序存储二叉树的特点☆
顺序二叉树通常只考虑完全二叉树第 n 个元素的左子节点为 2 * n + 1第 n 个元素的右子节点为 2 * n + 2第 n 个元素的父节点为 (n-1) / 2n : 表示二叉树中的第几个元素(按 0 开始编号如图所示)
1.3 顺序存储二叉树遍历
要求在遍历数组 arr 时，仍然可以以前序遍历，中序遍历和后序遍历的方式完成结点的遍历给你一个数组 {1,2,3,4,5,6,7}，要求以二叉树前序遍历，中序遍历和后序遍历的方式进行遍历。
前序遍历的结果应当为1,2,4,5,3,6,7中序遍历的结果应当为4 2 5 1 6 3 7后序遍历的结果应当为4 5 2 6 7 3 1
1.3.1 代码实现
public class ArrBinaryTreeDemo {
public static void main(String
[] args
) {
int[] arr
= {1,2,3,4,5,6,7};
ArrBinaryTree arrBinaryTree
= new ArrBinaryTree(arr
);
System
.out
.println("顺序储存的二叉树的前序遍历：");
arrBinaryTree
.preOrder();
System
.out
.println("顺序储存的二叉树的中序遍历：");
arrBinaryTree
.infixOrder();
System
.out
.println("顺序储存的二叉树的后序遍历：");
arrBinaryTree
.postOrder();
}
}
class ArrBinaryTree {
private int[] arr
;
public ArrBinaryTree(int[] arr
) {
this.arr
= arr
;
}
public void preOrder() {
this.preOrder(0);
}
public void infixOrder() {
this.infixOrder(0);
}
public void postOrder() {
this.postOrder(0);
}
public void preOrder(int index
) {
if (arr
== null
|| arr
.length
== 0) {
System
.out
.println("数组为空，不能按照二叉树的前序遍历");
}
System
.out
.println(arr
[index
]);
if ((index
* 2 + 1) < arr
.length
) {
preOrder((index
* 2 + 1));
}
if ((index
* 2 + 2) < arr
.length
) {
preOrder((index
* 2 + 2));
}
}
public void infixOrder(int index
) {
if (arr
== null
|| arr
.length
== 0) {
System
.out
.println("数组为空，不能按照二叉树的前序遍历");
}
if ((index
* 2 + 1) < arr
.length
) {
infixOrder((index
* 2 + 1));
}
System
.out
.println(arr
[index
]);
if ((index
* 2 + 2) < arr
.length
) {
infixOrder((index
* 2 + 2));
}
}
public void postOrder(int index
) {
if (arr
== null
|| arr
.length
== 0) {
System
.out
.println("数组为空，不能按照二叉树的前序遍历");
}
if ((index
* 2 + 1) < arr
.length
) {
postOrder((index
* 2 + 1));
}
if ((index
* 2 + 2) < arr
.length
) {
postOrder((index
* 2 + 2));
}
System
.out
.println(arr
[index
]);
}
}
2. 线索化二叉树
n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种一个结点的前一个结点，称为 前驱结点一个结点的后一个结点，称为后继结点
2.1 线索二叉树应用案例
将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
当线索化二叉树后，Node 节点的 属性 left 和 right ，有如下情况:
left 指向的是左子树，也可能是指向的前驱节点. ① 节点 left 指向的左子树, ⑩ 节点的 left 指向的就是前驱节点right 指向的是右子树，也可能是指向后继节点。 ① 节点 right 指向的是右子树 ⑩ 节点的 right 指向的是后继节点
2.2 代码实现
2.2.1 HeroNode 部分
如果 leftType == 0 表示指向的是左子树，如果是1 表示指向的是前驱节点如果 rightType == 0 表示指向是右子树, 如果 1 表示指向后继结点
class HeroNode{
private int no
;
private String name
;
private HeroNode left
;
private HeroNode right
;
private int leftType
;
private int rightType
;
public HeroNode(int no
, String name
) {
super();
this.no
= no
;
this.name
= name
;
}
@Override
public String
toString() {
return "HeroNode [no=" + no
+ ", name=" + name
+ "]";
}
}
2.2.2 ThreadedBinaryTree 部分
public void threadedList();遍历线索化二叉树的方法
public void threadedNode();
public void threadedNode(HeroNode node);
class ThreadedBinaryTree{
private HeroNode root
;
private HeroNode pre
= null
;
public HeroNode
getRoot() {
return root
;
}
public void setRoot(HeroNode root
) {
this.root
= root
;
}
public HeroNode
getPre() {
return pre
;
}
public void setPre(HeroNode pre
) {
this.pre
= pre
;
}
public void threadedList() {
HeroNode node
= root
;
while(node
!= null
) {
while(node
.getLeftType() == 0) {
node
= node
.getLeft();
}
System
.out
.println(node
);
while(node
.getRightType() == 1) {
node
= node
.getRight();
System
.out
.println(node
);
}
node
= node
.getRight();
}
}
public void threadedNode() {
this.threadedNode(root
);
}
public void threadedNode(HeroNode node
) {
if(node
== null
) {
return;
}
threadedNode(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
;
threadedNode(node
.getRight());
}
}
2.2.3 测试
public class ThreadedBinaryTreeDemo {
public static void main(String
[] args
) {
HeroNode root
= new HeroNode(1, "tom");
HeroNode node2
= new HeroNode(3, "jack");
HeroNode node3
= new HeroNode(6, "smith");
HeroNode node4
= new HeroNode(8, "mary");
HeroNode node5
= new HeroNode(10, "king");
HeroNode node6
= new HeroNode(14, "dim");
root
.setLeft(node2
);
root
.setRight(node3
);
node2
.setLeft(node4
);
node2
.setRight(node5
);
node3
.setLeft(node6
);
ThreadedBinaryTree threadedBinaryTree
= new ThreadedBinaryTree();
threadedBinaryTree
.setRoot(root
);
threadedBinaryTree
.threadedNode();
HeroNode leftNode
= node5
.getLeft();
HeroNode rightNode
= node5
.getRight();
System
.out
.println("10 号结点的前驱结点是 =" + leftNode
);
System
.out
.println("10 号结点的后继结点是=" + rightNode
);
System
.out
.println("使用线索化的方式遍历 线索化二叉树");
threadedBinaryTree
.threadedList();
}
}
☆
