2023年四川省資料總結高階

1、對一般二叉樹，僅根據乙個先序、中序、後序遍歷，不能確定另乙個遍歷序列。但對於滿二叉樹，任一結點的左右子樹均含有數量相等的結點，根據此性質，可將任一遍歷序列轉為另一遍歷序列（即任一遍歷序列均可確定一棵二叉樹）。

void pretopost(elemtype pre ,post,int l1,h1,l2,h2)

//將滿二叉樹的先序序列轉為後序序列，l1,h1,l2,h2是序列初始和最後結點的下標。

}//pretopost

32. .葉子結點只有在遍歷中才能知道，這裡使用中序遞迴遍歷。

設定前驅結點指標pre，初始為空。第乙個葉子結點由指標head指向，遍歷到葉子結點時，就將它前驅的rchild指標指向它，最後葉子結點的rchild為空。

linkedlist head,pre=null; //全域性變數

linkedlist inorder(bitree bt)

//中序遍歷二叉樹bt，將葉子結點從左到右鏈成乙個單鏈表，表頭指標為head

//處理第乙個葉子結點

else //將葉子結點鏈入鍊錶

inorder(bt->rchild中序遍歷左子樹

pre->rchild=null設定鍊錶尾

}return(head); } //inorder

時間複雜度為o(n),輔助變數使用head和pre,棧空間複雜度o(n)

2、有乙個帶頭結點的單鏈表，每個結點包括兩個域，乙個是整型域info，另乙個是指向下乙個結點的指標域next。假設單鏈表已建立，設計演算法刪除單鏈表中所有重複出現的結點，使得info域相等的結點只保留乙個。

#include <>

typedef char datatype;

typedef struct node listnode;

typedef listnode* linklist;

/* 刪除單鏈表中重複的結點 */

linklist deletelist(linklist head)

else

p=p->next;

}return head;

} 3、假設以i和o分別表示入棧和出棧操作。棧的初態和終態均為空，入棧和出棧的操作序列可表示為僅由i和o組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）

（1）a和d是合法序列，b和c 是非法序列。

（2）設被判定的操作序列已存入一維陣列a中。

int judge(char a)

判斷字元陣列a中的輸入輸出序列是否是合法序列。如是，返回true，否則返回false。

i++; //不論a[i]是『i』或『o』，指標i均後移。}

if(j!=k)

else

演算法結束。