在进行平衡二叉树的构建构成中,每当发现不平衡的结点就要及时的做平衡。根据不同的情况对最小不平衡子树进行左右旋转操作。例如:(左旋转)
右边多的进行左旋转,把1拉下来,看起来想往左边转吧!
//左旋转 static void L_Rotate(ref Node node)//传入的是1 { Node temp; temp = node.cRight; node.cRight = temp.cLeft;//2的左结点设为给1的右节点 temp.cLeft = node;//2的左边设为1 node = temp;//原1的位置改为2,这解释,啧啧 }
node.cRight = temp.cLeft;-》如果说原来2是有左结点的话设为x,x<2,又2是1的右结点,所有1<x,又1的原右结点被破坏了,所以可以用1的右节点来承接x结点。如果不这样做的话,你试试,2有左右结点,然后一转,嘿嘿,三个结点了真是奇怪。
//右旋转 static void R_Rotate(ref Node node) { Node temp; temp = node.cLeft; node.cLeft = temp.cRight;//原前驱,变左结点 temp.cRight = node; node = temp; }
右旋转和左旋转差不多,不同的是操作左右结点的不同。