目录
  1. 1. Node节点类
  2. 2. 创建二叉树、二叉树中序线索化(线索化有3种,此处单讲中序)
算法-线索二叉树

概念性的东西,自行百度。

按照国际管理,直接上代码来分析。

Node节点类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
package com.tree.thread;

/**
* Author: lihao
* Date:2017/8/30
* Description:ThreadBinaryTree Node
*/
public class Node
{
private int data;
private Node left;
private boolean leftIsThread; // 左孩子是否为线索
private Node right;
private boolean rightIsThread; // 右孩子是否为线索

public Node(int data)
{
this.data = data;
this.left = null;
this.leftIsThread = false;
this.right = null;
this.rightIsThread = false;
}

public int getData()
{
return data;
}

public void setData(int data)
{
this.data = data;
}

public Node getLeft()
{
return left;
}

public void setLeft(Node left)
{
this.left = left;
}

public boolean isLeftIsThread()
{
return leftIsThread;
}

public void setLeftIsThread(boolean leftIsThread)
{
this.leftIsThread = leftIsThread;
}

public Node getRight()
{
return right;
}

public void setRight(Node right)
{
this.right = right;
}

public boolean isRightIsThread()
{
return rightIsThread;
}

public void setRightIsThread(boolean rightIsThread)
{
this.rightIsThread = rightIsThread;
}

@Override
public boolean equals(Object obj)
{
if (obj instanceof Node)
{
Node temp = (Node) obj;
if (temp.getData() == this.data)
{
return true;
}
}
return false;
}

@Override
public int hashCode()
{
return super.hashCode() + this.data;
}
}

创建二叉树、二叉树中序线索化(线索化有3种,此处单讲中序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
package com.tree.thread;

public class ThreadTree {
private Node root; // 根节点
private Node pre = null; // 线索化的时候保存前驱

public ThreadTree() {
this.root = null;
this.pre = null;
}

public ThreadTree(int[] data) {
this.pre = null;
this.root = createTree(data, 0); // 创建二叉树
}

/**
* 创建二叉树
*/
public Node createTree(int[] data, int index) {
if (index >= data.length) {
return null;
}
Node node = new Node(data[index]);
node.setLeft(createTree(data, 2 * index + 1));
node.setRight(createTree(data, 2 * index + 2));
return node;
}

/**
* 将以root为根节点的二叉树线索化 中序法
*/
public void inThread(Node root) {
if (root != null) {
inThread(root.getLeft()); // 线索化左孩子
if (null == root.getLeft()) // 左孩子为空
{
root.setLeftIsThread(true); // 将左孩子设置为线索
root.setLeft(pre);
}
if (pre != null && null == pre.getRight()) // 右孩子为空
{
pre.setRightIsThread(true);
pre.setRight(root);
}
pre = root; //每次将当前节点设置为pre
inThread(root.getRight()); // 线索化右孩子
}
}

/**
* 中序遍历线索二叉树
*/
public void inThreadList(Node root) {
if (root == null) {
return;
}
//查找中序遍历的起始节点
while (root != null && !root.isLeftIsThread()) {
root = root.getLeft();
}
while (root != null) {
System.out.print(root.getData() + ",");
if (root.isRightIsThread()) // 如果右孩子是线索
{
root = root.getRight();
} else // 有右孩子
{
root = root.getRight();
while (root != null && !root.isLeftIsThread()) {
root = root.getLeft();
}
}
}

}


/**
* 中序遍历
*/
public void inList(Node root) {
if (root != null) {
inList(root.getLeft());
System.out.print(root.getData() + ",");
inList(root.getRight());
}
}

public Node getRoot() {
return root;
}

public void setRoot(Node root) {
this.root = root;
}
}
文章作者: 李浩
文章链接: https://leehoward.cn/2019/10/17/算法-线索二叉树/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 leehoward
打赏
  • 微信
  • 支付宝

评论