Skip to content

Commit 06a2aa5

Browse files
MaJesTySAMaJesTySA
committed
revise
1 parent dde090d commit 06a2aa5

1 file changed

Lines changed: 39 additions & 41 deletions

File tree

‎src/q08_二叉树的下一个节点/GetNextNode.java‎

Lines changed: 39 additions & 41 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
package q08_二叉树的下一个节点;
22

3-
43
import utils.BinaryTreeNode;
54

65
import java.util.ArrayList;
@@ -9,12 +8,46 @@
98
public class GetNextNode {
109
public static void main(String[] args) {
1110
test1();
12-
System.out.println("======");
1311
test2();
14-
System.out.println("======");
1512
test3();
1613
}
1714

15+
private static BinaryTreeNode getNextNode(BinaryTreeNode node) {
16+
if (node == null)
17+
return null;
18+
BinaryTreeNode nextNode = null;
19+
//如果该节点右节点不为空，则找右节点的最左节点
20+
if (node.right != null) {
21+
BinaryTreeNode tempNode = node.right;
22+
while (tempNode.left != null) {
23+
tempNode = tempNode.left;
24+
}
25+
nextNode = tempNode;
26+
}
27+
//如果该节点右节点为空，则看该节点是否是父节点的左节点
28+
else if (node.parent != null) {
29+
BinaryTreeNode curNode = node;
30+
BinaryTreeNode pareNode = node.parent;
31+
while (pareNode != null && curNode == pareNode.right) {
32+
curNode = pareNode;
33+
pareNode = pareNode.parent;
34+
}
35+
nextNode = pareNode;
36+
}
37+
return nextNode;
38+
}
39+
40+
private static void printNodes(List<BinaryTreeNode> lists) {
41+
for (int i = 0; i < lists.size(); i++) {
42+
try {
43+
System.out.println("节点: " + lists.get(i).value + "的后继结点: " + getNextNode(lists.get(i)).value);
44+
} catch (Exception e) {
45+
System.out.println("节点: " + lists.get(i).value + "的后继结点: null");
46+
}
47+
}
48+
System.out.println("=========");
49+
}
50+
1851
private static void test1() {
1952
System.out.println("完全二叉树");
2053
BinaryTreeNode node1 = new BinaryTreeNode(8);
@@ -24,13 +57,13 @@ private static void test1() {
2457
BinaryTreeNode node5 = new BinaryTreeNode(7);
2558
BinaryTreeNode node6 = new BinaryTreeNode(9);
2659
BinaryTreeNode node7 = new BinaryTreeNode(11);
27-
node1.right = node2;
60+
node1.left = node2;
2861
node1.right = node3;
2962
node2.parent = node1;
30-
node2.right = node4;
63+
node2.left = node4;
3164
node2.right = node5;
3265
node3.parent = node1;
33-
node3.right = node6;
66+
node3.left = node6;
3467
node3.right = node7;
3568
node4.parent = node2;
3669
node5.parent = node2;
@@ -73,16 +106,6 @@ private static void test2() {
73106
printNodes(lists);
74107
}
75108

76-
private static void printNodes(List<BinaryTreeNode> lists) {
77-
for (int i = 0; i < lists.size(); i++) {
78-
try {
79-
System.out.println("节点: " + lists.get(i).value + "的后继结点: " + getNextNode(lists.get(i)).value);
80-
} catch (Exception e) {
81-
System.out.println("节点: " + lists.get(i).value + "的后继结点: null");
82-
}
83-
}
84-
}
85-
86109
private static void test3() {
87110
System.out.println("只有右节点");
88111
BinaryTreeNode node1 = new BinaryTreeNode(2);
@@ -105,31 +128,6 @@ private static void test3() {
105128
System.out.println();
106129
printNodes(lists);
107130
}
108-
109-
private static BinaryTreeNode getNextNode(BinaryTreeNode node) {
110-
if (node == null)
111-
return null;
112-
BinaryTreeNode nextNode = null;
113-
//如果该节点右节点不为空，则找右节点的最左节点
114-
if (node.right != null) {
115-
BinaryTreeNode tempNode = node.right;
116-
while (tempNode.right != null) {
117-
tempNode = tempNode.right;
118-
}
119-
nextNode = tempNode;
120-
}
121-
//如果该节点右节点为空，则看该节点是否是父节点的左节点
122-
else if (node.parent != null) {
123-
BinaryTreeNode curNode = node;
124-
BinaryTreeNode pareNode = node.parent;
125-
while (pareNode != null && curNode == pareNode.right) {
126-
curNode = pareNode;
127-
pareNode = pareNode.parent;
128-
}
129-
nextNode = pareNode;
130-
}
131-
return nextNode;
132-
}
133131
}
134132

135133

0 commit comments

Comments
 (0)