如何用 C++ 在 GUI 中畫出各種平衡樹插入刪除的動態變化？

01-08

例如展示紅黑樹插入節點、刪除節點、樹的動態變化、顏色變化，該如何在界面上實現？（例如具體用哪些控制項）
希望最好介紹基於 Qt 的實現，最好不要是 MFC。

先把平衡樹寫出來，然後做一個ICallback讓演算法裡面給你彙報中間進度，大概包含節點要從這裡抽走了，節點要從這裡插入了的這些關鍵內部步驟。然後對每一個平衡樹的函數和ICallback的成員函數做人肉CPS變換，於是你就完成了了可以在演算法中間隨時（一般指的是發生關鍵步驟的時候）暫停在演算法外面隨時恢復的牛逼功能了。整棵平衡樹就從push變成了pull。後面動畫就很容易寫了，學幾個Direct2D的API畫畫圖，輕鬆搞定。

貝爾實驗室出品的Graphviz專門用來繪製樹我之前用她來畫AST 用法極其簡便依樣畫葫蘆即可

儘管和你的目標還是有點區別不過應該可以從他的用法上學到點什麼

這個沒有現成的控制項弄，也沒聽過有現成的演算法可視化庫，估計你要自己從頭弄了

類似的問題我也考慮過，我考慮的主要是，如何畫出一個形態比較漂亮的二叉樹。

後來想想工作量略大，放棄了。

我也見過，有人做出 8皇后演算法的動態動畫。

我自己寫過 8 叉樹演算法生成索引圖像調色板的 8 叉樹和葉子節點展開，收縮，顏色變化等演化的動畫。

總體來說，樓主考慮的問題，主要是和 GDI 畫圖，以及視圖的控制有關係。

個人覺得工作量不小。收益 / 付出比有點低，所以一般這樣的任務，我就放棄了。。。除非，收益很重要，很大。

題主，Qt是有相關的控制項庫可用的。請看這兒：Reference documentation: Trees

對應的源碼在這兒：RomHaKorev/Thistle: A library for Qt applic...

結合上面各位的回答（ @vczh@孫明琦），做出來你要的效果不是難事兒。只是顯示出足夠好的動態過渡效果還需要自己去搞。

寫了一大半，結果爪機沒電了，又沒保存，坑爹(╯‵□′)╯︵┻━┻ 。

爪機答，沒圖，大家將就著看看，我說的還是挺簡單的，不需要學習gui編程。

話說我原來在學習opencv的時候我就跟題主一樣突發奇想想用opencv的窗口和裡面一些簡單的函數實現動態實時地展現演算法執行流程，我當時就以二叉樹思考了一番，如有紕漏，還請指正。

首先交代幾個量:

節點類:除了傳統數據，還加入一個圓心像素位置(x,y)，一個寬度w或者角度a，用來計算孩子節點的x坐標，這個寬度或者角度隨著深度增長而慢慢減小，可以事先確定一個減小因子e；

半徑r:節點用小圓圈表示，如果是紅黑樹這樣的，可以用紅圓圈紅數字和黑圓圈黑數字表示，r表示圓圈半徑；

上下層高度h:固定值，用來計運算元節點的y坐標；

初始時，根據窗口大小W*H，以及最大節點數計算出適合的r,h,w，避免插入過多節點使節點位置跑到窗口外面了，之後r,h固定不變了，w是會變的。這些都是以像素為單位。

好了，下面說插入過程:

初始:在(W/2,r)位置插入根節點，圓圈裡的數字用putText輸出，並計算它的孩子節點相對於它的水平偏移w*e；

保持:對於樹T，圓心位置(x,y)，寬度成員wt，假設在右邊插入，那麼孩子節點的圓心坐標為(x+wt,y+h)，左邊就是(x-wt,y+h)，輸出數字，並在兩個圓心間畫一個箭頭（線段也可以，不過箭頭好看些，哎，處女座）指向孩子節點，也可以在圓圈線上畫，需要計算一下起始點，這樣更美觀，計算寬度成員wt*e；

最終:不斷如此插入，不斷保存前一幀，在其上畫出插入後的結果，刷新窗口，實時動態展現。

查找過程。

對於節點A，(x,y)，訪問它的時候我們可以在圓心水平位置畫一個箭頭，表示正在訪問它，假設在該節點右邊畫，那麼箭頭終點就是(x+r,y)，箭頭長度為L，起點就是(x+r+L,y)，還有兩條分叉的小線段，這個也需要計算一下，如果只畫線段就不需要了。你還能在箭頭起點右邊一點展示當前正在插入的數字。

刪除過程稍微繁瑣一點，在要刪除的節點和箭頭的位置，畫一個相同的節點和箭頭，不過顏色和背景一樣，這樣就抹除了。

如果是平衡樹，旋轉什麼的就更繁瑣一點，不過也就是各種位置確定，抹除等等。

以上不僅每插入一個元素展現結果，而且每查找一步也展現結果，實時動態；

如果要想再簡單點，那麼可以不用每次保存前一次的幀，增量畫一點，而可以每次直接畫出整棵樹，查找的話還要在找到的節點旁邊畫個箭頭。

你看，並不難，簡單的位置計算，基本的opencv繪畫函數putText和circle還有line，窗口調用定義namedWindow和繪製imshow。

可以用一個專門的類來負責繪製。

除了這個，我當時還想著可以把所有常見的演算法，比如演算法導論上的全部再現，這個時候再用qt做一個界面，能夠通過按鈕選擇不同的演算法進行演示，數據也從界面輸入等等，然後打包成小軟體分享。不過當時距離我搞完演算法導論有幾個月了，而且工程量太大，演算法倒不擔心，因為我已經幾乎全部實現了，主要就是有點繁瑣，集中在坐標呀，間距設定呀(這個估計還要試)，要是複雜如斐波那契堆、圖，那就更煩鎖了，又沒太多時間，所以後來就沒搞了。

所以題主你可以用用opencv，不複雜，難的都是在演算法本身，繪製什麼的只是很繁瑣，你要有時間這些都是可以實現的。我舉的這個二叉樹實時展現例子可以用來很多類似的結構中，鏈表什麼的比這個還簡單些。

加油吧！期待你做出這個小軟體。

推薦一個用d3.js做的圖形化演算法的東西，希望對你有所啟發

VisuAlgo - visualising data structures and algorithms through animation

1樓說的是畫圖的方式，感覺好麻煩的說……

討個巧，由於樹是一種層次性很強的結構，所以我們可以直接把內容(放在label里)放在GridLayout上(就是一堆控制項)，然後在節點之間連線就好了。更新時有兩種選擇，全部刪除重新放置或者局部刪除調整，我個人傾向於前一種，因為好寫……

"Dynamic Multilevel Graph Visualization"

可以看看這篇論文然後用opengl實現 github上有人已經實現了。。

早期寫過一些類似的小軟體，但當時用java寫的，希望能對題主有所幫助：

helloyou2012/Mindmap · GitHub

helloyou2012/TreeDesigner · GitHub

helloyou2012/GraphEditor · GitHub

你這個不管qt還是mfc，就畫個圖，畫線的函數會了就做完了，一點區別都沒有，別糾結了，啥都行。

如果僅僅是展示執行過程，不用gui。還記得qq簽名裡面的那些火星文嗎？你就寫個演算法把兩叉樹上的結點映射到控制台坐標，然後列印點點就ok了。

哈哈，我用Qt做過查找演算法的動態演示，其中就有avl樹，b-樹的生成。可是現在不想看代碼，給你指條道:看c++ gt gui編程，其中有一節滑鼠單擊產生節點與節點間分支，我就說照那個做的，不需要什麼控制項。