1、因為後序遍歷棧中保留當前結點的祖先的資訊,用一變數儲存棧的最高棧頂指標,每當退棧時,棧頂指標高於儲存最高棧頂指標的值時,則將該棧倒入輔助棧中,輔助棧始終儲存最長路徑長度上的結點,直至後序遍歷完畢,則輔助棧中內容即為所求。
void longestpath(bitree bt)//求二叉樹中的第一條最長路徑長度
//沿左分枝向下
if(tag[top]==1) //當前結點的右分枝已遍歷
//保留當前最長路徑到l棧,記住最高棧頂指標,退棧
}else if(top>0) //沿右子分枝向下
}//while(p!=null||top>0)
}//結束longestpath
2、本題應使用深度優先遍歷,從主調函式進入dfs(v)時,開始記數,若退出dfs()前,已訪問完有向圖的全部頂點(設為n個),則有向圖有根,v為根結點。將n個頂點從1到n編號,各呼叫一次dfs()過程,就可以求出全部的根結點。題中有向圖的鄰接表儲存結構、記頂點個數的變數、以及訪問標記陣列等均設計為全域性變數。
建立有向圖g的鄰接表儲存結構參見上面第2題,這裡只給出判斷有向圖是否有根的演算法。
int num=0, visited=0 //num記訪問頂點個數,訪問陣列visited初始化。
const n=使用者定義的頂點數;
adjlist g用鄰接表作儲存結構的有向圖g。
void dfs(v)
//if
p=g[v].firstarc;
while (p)
//while
visited[v]=0; num--; //恢復頂點v
}//dfs
void judgeroot()
//判斷有向圖是否有根,有根則輸出之。
}// judgeroot
演算法中列印根時,輸出頂點在鄰接表中的序號(下標),若要輸出頂點資訊,可使用g[i].vertex。
3、由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹,下面程式的作用是實現由已知某二叉樹的前序遍歷和中序遍歷序列,生成一棵用二叉鍊錶表示的二叉樹並列印出後序遍歷序列,請寫出程式所缺的語句。
#define max 100
typedef struct node
tnode;
char pred[max],inod[max];
main(int argc,int **ar**)
tnode *restore(char *ppos,char *ipos,int n)
postorder(tnode*ptr)
2023年吉林省資料總結加強
1 對一般二叉樹,僅根據乙個先序 中序 後序遍歷,不能確定另乙個遍歷序列。但對於滿二叉樹,任一結點的左右子樹均含有數量相等的結點,根據此性質,可將任一遍歷序列轉為另一遍歷序列 即任一遍歷序列均可確定一棵二叉樹 void pretopost elemtype pre post,int l1,h1,l2...
2023年吉林省資料總結加強
1 本題要求建立有序的迴圈鍊錶。從頭到尾掃瞄陣列a,取出a i 0 ilinkedlist creat elemtype a,int n 由含n個資料的陣列a生成迴圈鍊錶,要求鍊錶有序並且無值重複結點 查詢a i 的插入位置 if p h p data a i重複資料不再輸入 for return ...
2023年吉林省重要資料加強
1 設一棵樹t中邊的集合為,要求用孩子兄弟表示法 二叉鍊錶 表示出該樹的儲存結構並將該樹轉化成對應的二叉樹。2 設一棵二叉樹的結點結構為 llink,info,rlink root為指向該二叉樹根結點的指標,p 和q分別為指向該二叉樹中任意兩個結點的指標,試編寫一演算法ancestor root,p...