二叉排序樹的實(shí)現(xiàn)[最終版](編輯修改稿)
2025-07-13 00:24 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 deright == NULL) {//如果右兒子為空，則直接輸出 printf(%d ,nodeelement)。 }else { if(isStackEmpty(tmp) || node != top(tmp)) { push(node,stack)。//再次把有右兒子的節(jié)點(diǎn)入棧 push(node,tmp)。//同時(shí)也把該節(jié)點(diǎn)壓入臨時(shí)棧中 pushLeftToStack(noderight,stack)。 }else {//如果該節(jié)點(diǎn)兩次入棧了，就把它訪問(wèn)并輸出 pop(tmp)。 printf(%d ,nodeelement)。 } } } printf(\n)。 disposeStack(stack)。 disposeStack(tmp)。}3. 打印樹為了在終端中打印一棵樹，則需要確定在打印一個(gè)節(jié)點(diǎn)時(shí)，前面需要打印多少個(gè)空格。在這里，我們可以為每個(gè)節(jié)點(diǎn)設(shè)置一個(gè)位置。位置的設(shè)置方式如下圖：這棵樹高為3,故根節(jié)點(diǎn)的位置為??=8，這個(gè)8代表在打印根節(jié)點(diǎn)時(shí)，需要在其前面打印81 = 7個(gè)空格。確定好根節(jié)點(diǎn)的位置后，就可以確定其子節(jié)點(diǎn)的位置了。從最高的層開始，設(shè)置第1層所有節(jié)點(diǎn)的深度為0,第2層所有節(jié)點(diǎn)的深度為1,依此類推。設(shè)某個(gè)節(jié)點(diǎn)是其父節(jié)點(diǎn)的左兒子，它的位置為pc,深度為l,父節(jié)點(diǎn)位置為pp,根節(jié)點(diǎn)的位置為R，則pc = pp R/2^l。如上面的根節(jié)點(diǎn)的左兒子的位置為 8 2^1 = 4。同理，根的右兒子的位置為 8 + 2^1 = 12。第3層中的第一個(gè)節(jié)點(diǎn)的位置為4 8/2^2 = 4 2 = 2。這樣，只要知道根節(jié)點(diǎn)的位置，可以知道整棵樹的位置了。而根節(jié)點(diǎn)的位置 R = 2^h,其中h為樹的高度。下面來(lái)看具體代碼：先是獲取樹中每個(gè)節(jié)點(diǎn)的深度和整棵樹的高度的代碼，在這里，用層序遍歷樹來(lái)進(jìn)行深度設(shè)置：static int treeHeight = 1。static void getLegthOfTree(Tree tree) { Queue parentQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE)。//保存父節(jié)點(diǎn)的隊(duì)列 Queue childQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE)。//保存子節(jié)點(diǎn)的隊(duì)列 int leght = 0。//當(dāng)前的深度 treeHeight = 1。 Enqueue(tree, parentQueue)。 while(!IsQueueEmpty(parentQueue)) { while(!IsQueueEmpty(parentQueue)){ TreePosition node = FrontAndDequeue(parentQueue)。//出列 nodeleght = leght。 if(nodeleft != NULL) Enqueue(nodeleft, childQueue)。//把子節(jié)點(diǎn)入子隊(duì)列中 if(noderight != NULL) Enqueue(noderight, childQueue)。 } //交換父子隊(duì)列 Queue tempQueue = parentQueue。 parentQueue = childQueue。 childQueue = tempQueue。 leght++。//每遍歷一層，深度加一 treeHeight++。//樹高度加一 } DisposeQueue(parentQueue)。 DisposeQueue(childQueue)。}接下來(lái)是獲取樹中每個(gè)節(jié)點(diǎn)的位置的代碼，這里同樣使用層序遍歷來(lái)獲取每個(gè)節(jié)點(diǎn)的位置：static void getPositionOfTree(Tree tree) { Queue parentQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE)。 Queue childQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE)。 Enqueue(tree, parentQueue)。 treeposition = 1 treeHeight。 int topPosition = treeposition。 while(!IsQueueEmpty(parentQueue)) { while(!IsQueueEmpty(parentQueue)) { TreePosition node = FrontAndDequeue(parentQueue)。 if(nodeleft != NULL){ int leftStep = topPosition nodeleftleght。 nodeleftposition = nodeposition leftStep。 Enqueue(nodeleft, childQueue)。 } if(noderight != NULL){ int rightStep = topPosition noderightleght。 noderightposition = nodeposition + rightStep。 Enqueue(noderight, childQueue)。 } } Queue tempQueue = parentQueue。 parentQueue = childQueue。 childQueue = tempQueue。 } DisposeQueue(parentQueue)。 DisposeQueue(childQueue)。 }接下來(lái)是打印樹的代碼： void printTree(Tree tree) { getLegthOfTree(tree)。 getPositionOfTree(tree)。 printf(\n)。 Queue parentQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE)。 Queue childQueue = CreateQueue(TRAVERSAL_QUEUE_SIZE)。 int prePosition = 0。 Enqueue(tree, parentQueue)。 while(!I
研究報(bào)告相關(guān)推薦
鄂ICP備17016276號(hào)-1