0
我试图在学习它之后实现红黑树，但打印红黑树时出错。你能否看看并提出实施红黑树插入是否存在任何问题。 它显示只有root和它的第一左，右孩子递归，然后显示以下错误：红黑树 - 打印错误
Exception in thread "main" java.lang.StackOverflowError
at java.io.FileOutputStream.write(FileOutputStream.java:326)
at java.io.BufferedOutputStream.flushBuffer(BufferedOutputStream.java:82)
at java.io.BufferedOutputStream.flush(BufferedOutputStream.java:140)
at java.io.PrintStream.write(PrintStream.java:482)
at sun.nio.cs.StreamEncoder.writeBytes(StreamEncoder.java:221)
at sun.nio.cs.StreamEncoder.implFlushBuffer(StreamEncoder.java:291)
at sun.nio.cs.StreamEncoder.flushBuffer(StreamEncoder.java:104)
at java.io.OutputStreamWriter.flushBuffer(OutputStreamWriter.java:185)
at java.io.PrintStream.write(PrintStream.java:527)
at java.io.PrintStream.print(PrintStream.java:669)
at java.io.PrintStream.println(PrintStream.java:806)
at RedBlackTree.preOrder(RedBlackTree.java:161)
at RedBlackTree.preOrder(RedBlackTree.java:162)
at RedBlackTree.preOrder(RedBlackTree.java:162)
at RedBlackTree.preOrder(RedBlackTree.java:163)
最后的两个错误的线路重复多次。
对于打印命令，我使用简单的预先递归代码。 以下是代码：
public class RedBlackTree {
public RBNode root;
void leftRotate(RBNode node)
{
RBNode y;
y = node.right;
if(y.left != null)y.left.parent = node;
y.parent = node.parent;
if(node.parent == null)root = y;
else
{
if(node == node.parent.left)node.parent.left = y;
else node.parent.right =y;
}
y.left = node;
node.parent = y;
}
void rightRotate(RBNode node)
{
RBNode y;
y = node.left;
if(y.right != null)y.right.parent = node;
y.parent = node.parent;
if(node.parent == null)root = y;
else
{
if(node == node.parent.right)node.parent.right = y;
else node.parent.left =y;
}
y.right = node;
node.parent = y;
}
void insertNode(RBNode node, RBNode data)
{
// INSERT IN ROOT
if(node == null)
{
node = new RBNode(data.key);
root = node;
root.color = 0;
System.out.println("Root " + root.key);
}
else if (data.key < node.key && node.left == null)
{
node.left = data;
data.parent = node;
}
else if(data.key >node.key && node.right == null)
{
node.right = data;
data.parent = node;
}
else{
if(data.key < node.key)insertNode(node.left, data);
else insertNode(node.right, data);
}
data.color = 1;
RBNode uncle;
//Check REB BLACK PROPERTIES
while(data.parent != null && data.parent.color ==1 && data != root && data.color != 0)
{
System.out.println("Data " + data.key + " Parent " + data.parent.key);
//PARENT IS RIGHT CHILD
if(data.parent == data.parent.parent.right)
{
System.out.println("Parent RIGHT");
uncle = data.parent.parent.left;
if(uncle == null) System.out.println("Uncle is null");
//UNCLE IS BLACK OR NULL
if(uncle == null || uncle.color == 0)
{
System.out.println("Uncle BLACK or NULL");
if(data == data.parent.left)
{
System.out.println("Node is LEFT");
data = data.parent;
rightRotate(data);
}
data.parent.color = 0;
if(data.parent.parent.key != root.key)data.parent.parent.color = 1;
leftRotate(data.parent.parent);
}
//UNCLE IS RED
else
{
System.out.println("Uncle RED");
data.parent.parent.left.color = 0;
data.parent.color = 0;
if(data.parent.parent.key != root.key)data.parent.parent.color = 1;
data = data.parent;
}
}
// PARENT IS LEFT CHILD
else
{
System.out.println("Parent LEFT");
uncle = data.parent.parent.right;
//UNCLE IS NULL OR BLACK
if(uncle ==null || uncle.color == 0)
{
System.out.println("Uncle BLACK or NULL");
System.out.println("");
if(data == data.parent.right)
{
System.out.println("Node is RIGHT");
data = data.parent;
leftRotate(data);
}
data.parent.color = 0;
if(data.parent.parent.key != root.key)data.parent.parent.color = 1;
rightRotate(data.parent.parent);
}
//UNCLE IS RED
else
{
System.out.println("Uncle RED");
data.parent.parent.right.color = 0;
data.parent.color = 0;
if(data.parent.parent.key != root.key)data.parent.parent.color= 1;
data = data.parent;
}
}
}
root.color = 0;
}
void preOrder(RBNode node)
{
if(node != null)
{
System.out.println("Value : " + node.key + "Color: " + node.color);
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String args[])
{
RedBlackTree tree = new RedBlackTree();
tree.insertNode(tree.root, new RBNode(2));
tree.insertNode(tree.root, new RBNode(1));
tree.insertNode(tree.root, new RBNode(4));
tree.insertNode(tree.root, new RBNode(5));
tree.insertNode(tree.root, new RBNode(9));
tree.insertNode(tree.root, new RBNode(3));
tree.insertNode(tree.root, new RBNode(6));
tree.insertNode(tree.root, new RBNode(7));
tree.preOrder(tree.root);
}
}
class RBNode
{
int key;
RBNode parent;
RBNode left;
RBNode right;
int color; // 1 = RED , 0 = BLACK
public RBNode(int key)
{
this.key = key;
this.parent = null;
this.left = null;
this.right = null;
}
}
是插入实行错了吗？
能否请您提供整个代码与您的进口和全员工，以便我们可以编译和调试代码？ – Rafael
@PyPiper - 请检查编辑的问题。我输入了完整的代码。 –