求二叉樹中兩結點最近的共同祖先

1、目 錄沈陽航空航天大學I學術誠信聲明I1 題目介紹和功能要求41.1 題目介紹41.2 功能要求42 課程設計原理42.1 課設題目粗略分析42.2 原理圖介紹52.2.1 功能模塊52.2.2int main()主函數(shù)模塊62.2.3Node *Create()創(chuàng)建二叉樹模塊72.2.4 Node *closest_common_ancestor(Node *r, int u, int v)計算公共結點模塊83 主要函數(shù)描述93.1 創(chuàng)建二叉樹函數(shù)93.2 計算最近共同祖先函數(shù)93.3畫出二叉樹函數(shù)94 調試與分析104.1 調試過程105 運行結果115.1初始界面115.2創(chuàng)建二叉樹界面

2、115.3顯示二叉樹大概構成界面125.4輸入兩個結點計算最近共同祖先界面12參考文獻14附 錄（關鍵部分程序清單）15 1 題目介紹和功能要求1.1 題目介紹1、 根據(jù)鍵盤輸入數(shù)據(jù)創(chuàng)建二叉樹（默認采用先序遍歷創(chuàng)建二叉樹），結點數(shù)不少于5個。2、 假設二叉樹采用二叉鏈的結構存儲，p和q為二叉樹中的兩個結點，編寫程序計算它們最近的共同祖先并輸出。1.2 功能要求1、 有提示語句可以選擇是否退出程序。2、 具有判別輸入結點是否為該樹結點的功能。3、 p、q兩個結點可選，輸出顯示出樹的大概構成情況。2 課程設計原理2.1 課設題目粗略分析根據(jù)課設題目要求，擬將程序設計成八個模塊。以下是八個模塊的大體

3、分析：1、 int main()主函數(shù)模塊2、 int menu()提示語句模塊3、 Node *Create()創(chuàng)建二叉樹模塊4、 void dds(Node *p, Node *r)創(chuàng)建父結點模塊5、 void Draw(Node *r)顯示二叉樹大概構成模塊6、 Node *find(Node *p, int u)查找結點模塊7、 Node *closest_common_ancestor(Node *r, int u, int v)計算公共結點模塊8、 void clear(Node *r)清空標記模塊2.2 原理圖介紹2.2.1 功能模塊L C A生成模板查找模板顯示模板計算模板圖2

4、.2.1 功能模塊 2.2.2int main()主函數(shù)模塊圖2.2.2 主函數(shù)模塊2.2.3Node *Create()創(chuàng)建二叉樹模塊圖2.2.3創(chuàng)建二叉樹模塊2.2.4 Node *closest_common_ancestor(Node *r, int u, int v)計算公共結點模塊圖2.24計算最近共同結點模塊3 主要函數(shù)描述3.1 創(chuàng)建二叉樹函數(shù)調用遞歸，采用先序遍歷創(chuàng)建二叉樹，同時創(chuàng)建每個結點的父結點。根結點的父結點為NULL，左孩子和右孩子的父結點為他們的雙親，以鏈式存儲結構存儲二叉樹。3.2 計算最近共同祖先函數(shù)給出任意兩個結點P和Q后，先從P開始向上遍歷父結點，并進行標記

5、，直至指針指向NULL。接著，從Q開始遍歷其父結點，當指針遇到標記時退出循環(huán)。輸出最近共同祖先，否則無共同結點。3.3畫出二叉樹函數(shù)用一個二維數(shù)組graph 表示圖型，第一維表示圖的橫坐標，第二維表示圖的縱坐標，然后通過cal_d()函數(shù)計算出整個二叉樹的高度，cal_d()函數(shù)是一個遞歸函數(shù)，從根結點向下遍歷，獲取最大深度即為二叉樹高度，然后從二叉樹頂部向左右結點遞歸建圖，在二維數(shù)組中畫出主要形狀后，以打印字符形式把圖形輸出。4 調試與分析4.1 調試過程在調試程序是主要遇到以下幾類問題：1、基本語法錯誤解決方法：因為這屬于對于C語言基礎知識掌握的問題，所以查閱了相關書籍詢問了老師和同學，最

6、終改正。2、 如何創(chuàng)建二叉樹，并創(chuàng)建每個結點的父結點解決方法：調用遞歸，采用鏈式存儲結構先序遍歷創(chuàng)建二叉樹，空結點設為-1。根結點的父結點為NULL，左孩子和右孩子的父結點為他們的雙親。3、二叉樹表示模塊 解決方法：用一個二維數(shù)組表示二叉樹，然后計算出整個二叉樹的高度，從頂部向下遞歸建圖 。5 運行結果5.1初始界面5.2創(chuàng)建二叉樹界面采用先序遍歷創(chuàng)建二叉樹，空結點為-1，創(chuàng)建二叉樹：21749385.3顯示二叉樹大概構成界面5.4輸入兩個結點計算最近共同祖先界面選擇輸入4 和 7兩個結點，它們的最近共同祖先為4。輸入 1 和8兩個結點，它們的最近共同祖先為2。輸入 5 和 7兩個結點， 它們

7、沒有最近共同祖先。參考文獻1 高富平，張楚 . 電子商務法M. 北京：北京大學出版社，20022 Huang S C，Huang Y M，Shieh S MVibration and stability of a rotating shaft containing a transerse crackJ, J Sound and Vibration，1993，162（3）：3874013嚴蔚敏，吳偉民. 數(shù)據(jù)結構（c 語言版）M.北京：清華大學教育出版社，20064戴艷等.零基礎學算法M.北京：機械工業(yè)出版社.2012附 錄（關鍵部分程序清單）#include <stdio.h>#i

8、nclude <stdlib.h>#include <string.h>#define maxv 1024typedef struct Node int value, mark; struct Node *lc, *rc, *pa; Node;int graphmaxvmaxv;Node *Create();void dfs(Node *p, Node *r); /*設置父結點Node *find(Node *p, int u); /*查找void clear(Node *p); /*清空標記Node *closest_common_ancestor(Node *r,

9、int u, int v);/*計算最近共同祖先int menu();Node *Build(); /*構建二叉樹void Calculate(Node *r);int Max(int a, int b); /*比較a和b誰大int cal_d(Node *r, int d); /*計算二叉樹的高度void DFS(Node *r, int h, int w, int d); /*遞歸建圖void Draw(Node *r); /*畫出二叉樹int main() Node *r; while(1) switch(menu() case 1: r = Build(); break; case 2

10、: Calculate(r); break; case 3: Draw(r); break; case 0: return 0; return 0;Node *Create() int n; Node *p; scanf("%d", &n); if(n=-1) return NULL; p = (Node *)malloc(sizeof(Node); p->value = n; p->lc = Create(); p->rc = Create(); return p;void dfs(Node *p, Node *r) p->pa = r;

11、if(p->lc) dfs(p->lc, p); if(p->rc) dfs(p->rc, p);Node *find(Node *p, int u) Node *t; if(p->value=u) return p; if(p->lc) t = find(p->lc, u); if(t) return t; if(p->rc) t = find(p->rc, u); if(t) return t; return 0;Node *closest_common_ancestor(Node *r, int u, int v) Node *p =

12、 find(r, u); Node *q = find(r, v); while(p) p->mark = 1; p = p->pa; while(q) if(q->mark) break; q = q->pa; return q;void clear(Node *r) r->mark = 0; if(r->lc) clear(r->lc); if(r->rc) clear(r->rc);int menu() int option; printf("n-n"); printf("1、創(chuàng)建二叉樹n");

13、 printf("2、計算最近公共祖先n"); printf("3、顯示二叉樹n"); printf("0、退出n"); printf("-n"); scanf("%d", &option); return option;Node *Build() Node *p; printf("前序遍歷創(chuàng)建一棵二叉樹：n"); p = Create(); dfs(p, 0); return p;void Calculate(Node *r) int u, v; Node *p;

14、printf("輸入兩點：n"); scanf("%d%d", &u, &v); clear(r); p = closest_common_ancestor(r, u, v); if(!p) printf("沒有公共祖先n"); else printf("%d和%d的最近公共祖先是：%dn", u, v, p->value);int Max(int a, int b) return a>b ? a : b;int cal_d(Node *r, int d) int t = d; if(r

15、->lc) t = Max(t, cal_d(r->lc, d+1); if(r->rc) t = Max(t, cal_d(r->rc, d+1); return t;void DFS(Node *r, int h, int w, int d) int i; if(!r->lc && !r->rc) graphhw = r->value + '0' return ; graphhw = r->value + '0' if(r->lc) for(i=1; i<=(1<<d-2

16、); i+) graphhw-i = '-' graphh-1w-(1<<d-2) = '|' DFS(r->lc, h-2, w-(1<<d-2), d-1); if(r->rc) for(i=1; i<=(1<<d-2); i+) graphhw+i = '-' graphh-1w+(1<<d-2) = '|' DFS(r->rc, h-2, w+(1<<d-2), d-1); void Draw(Node *r)/*畫出二叉樹 int d,

17、h, w, i, j; if(!r) return ; d = cal_d(r, 1); h = d*2; w = 1<<d-1; DFS(r, h, w, d); for(i=h; i>=0; i-) for(j=0; j<w*2; j+) if(!graphij) putchar(' '); else putchar(graphij); putchar('n'); 課程設計總結：這次課程設計讓我收獲很多。這次的課設題目是求二叉樹中任意兩點的最近共同祖先，即經(jīng)典的LCA（Lowest Common Ancestor）題型。求解此問題的算法有很多，我在做這次的課設中采用的主要思路是：令每條樹上左孩子和右孩子的父親為父結點，根結點的父結點為NULL，在存儲二叉樹的同時存儲每個結點的父結點。給出任意兩個結點P和Q后，先從P開始向上遍歷父結點，并進行標記，直至NULL。接著，從Q開始遍歷其父結點，當指針遇到標記時退出循環(huán)。輸出最近共同祖先，否則無共同結點。通過這次課設，讓自己學到很多，首先是在面對自己從未見過的問題時，應該從已知的知識入手，首先是二叉樹的先序存儲，其次