2021年湖北省基礎數(shù)據(jù)要領

1、2021年湖北省基礎數(shù)據(jù)要領 2021年湖北省基礎數(shù)據(jù)要領 1、 二叉樹的層次遍歷序列的第一個結(jié)點是二叉樹的根。實際上，層次遍歷序列中的每個結(jié)點都是“局部根”。確定根后，到二叉樹的中序序列中，查到該結(jié)點，該結(jié)點將二叉樹分為“左根右”三部分。若左、右子樹均有，則層次序列根結(jié)點的后面應是左右子樹的根；若中序序列中只有左子樹或只有右子樹，則在層次序列的根結(jié)點后也只有左子樹的根或右子樹的根。這樣，定義一個全局變量指針r，指向?qū)哟涡蛄写幚碓亍Ｋ惴ㄖ邢忍幚砀Y(jié)點，將根結(jié)點和左右子女的信息入隊列。然后，在隊列不空的條件下，循環(huán)處理二叉樹的結(jié)點。隊列中元素的數(shù)據(jù)結(jié)構(gòu)定義如下： typedef struct

2、 int lvl; /層次序列指針，總是指向當前“根結(jié)點”在層次序列中的位置 int l,h; /中序序列的下上界 int f; /層次序列中當前“根結(jié)點”的雙親結(jié)點的指針 int lr; / 1雙親的左子樹 2雙親的右子樹 qnode; bitree creat(datatype in,level,int n) /由二叉樹的層次序列l(wèi)eveln和中序序列inn生成二叉樹。 n是二叉樹的結(jié)點數(shù) if (n1) printf(“參數(shù)錯誤n”); exit(0); qnode s,q; /q是元素為qnode類型的隊列，容量足夠大 init(q); int r=0; /r是層次序列指針，指向當前待

3、處理的結(jié)點 bitree p=(bitree)malloc(sizeof(binode); /生成根結(jié)點 p-data=level0; p-lchild=null; p-rchild=null; /填寫該結(jié)點數(shù)據(jù) for (i=0; in; i+) /在中序序列中查找根結(jié)點，然后，左右子女信息入隊列 if (ini=level0) break; if (i=0) /根結(jié)點無左子樹，遍歷序列的1n-1是右子樹 p-lchild=null; s.lvl=+r; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(q,s); else if (i=n-1) /根結(jié)點無右

4、子樹，遍歷序列的1n-1是左子樹 p-rchild=null; s.lvl=+r; s.l=1; s.h=i-1; s.f=p; s.lr=1; enqueue(q,s); else /根結(jié)點有左子樹和右子樹 s.lvl=+r; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(q,s);/左子樹有關信息入隊列 s.lvl=+r; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(q,s);/右子樹有關信息入隊列 while (!empty(q) /當隊列不空，進行循環(huán)，構(gòu)造二叉樹的左右子樹 s=delqueue(q); father=s.f

5、; for (i=s.l; i=s.h; i+) if (ini=levels.lvl) break; p=(bitreptr)malloc(sizeof(binode); /申請結(jié)點空間 p-data=levels.lvl; p-lchild=null; p-rchild=null; /填寫該結(jié)點數(shù)據(jù) if (s.lr=1) father-lchild=p; else father-rchild=p； /讓雙親的子女指針指向該結(jié)點 if (i=s.l) p-lchild=null; /處理無左子女 2021年湖北省基礎數(shù)據(jù)要領 s.lvl=+r; s.l=i+1; s.f=p; s.lr=2

6、; enqueue(q,s); else if (i=s.h) p-rchild=null; /處理無右子女 s.lvl=+r; s.h=i-1; s.f=p; s.lr=1; enqueue(q,s); elses.lvl=+r; s.h=i-1; s.f=p; s.lr=1; enqueue(q,s);/左子樹有關信息入隊列 s.lvl=+r; s.l=i+1; s.f=p; s.lr=2; enqueue(q,s); /右子樹有關信息入隊列 /結(jié)束while (!empty(q) return(p); /算法結(jié)束 2、 二叉樹的層次遍歷序列的第一個結(jié)點是二叉樹的根。實際上，層次遍歷序列中

7、的每個結(jié)點都是“局部根”。確定根后，到二叉樹的中序序列中，查到該結(jié)點，該結(jié)點將二叉樹分為“左根右”三部分。若左、右子樹均有，則層次序列根結(jié)點的后面應是左右子樹的根；若中序序列中只有左子樹或只有右子樹，則在層次序列的根結(jié)點后也只有左子樹的根或右子樹的根。這樣，定義一個全局變量指針r，指向?qū)哟涡蛄写幚碓亍Ｋ惴ㄖ邢忍幚砀Y(jié)點，將根結(jié)點和左右子女的信息入隊列。然后，在隊列不空的條件下，循環(huán)處理二叉樹的結(jié)點。隊列中元素的數(shù)據(jù)結(jié)構(gòu)定義如下： typedef struct int lvl; /層次序列指針，總是指向當前“根結(jié)點”在層次序列中的位置 int l,h; /中序序列的下上界 int f; /層

8、次序列中當前“根結(jié)點”的雙親結(jié)點的指針 int lr; / 1雙親的左子樹 2雙親的右子樹 qnode; bitree creat(datatype in,level,int n) /由二叉樹的層次序列l(wèi)eveln和中序序列inn生成二叉樹。 n是二叉樹的結(jié)點數(shù) if (n1) printf(“參數(shù)錯誤n”); exit(0); qnode s,q; /q是元素為qnode類型的隊列，容量足夠大 init(q); int r=0; /r是層次序列指針，指向當前待處理的結(jié)點 bitree p=(bitree)malloc(sizeof(binode); /生成根結(jié)點 p-data=level0;

9、 p-lchild=null; p-rchild=null; /填寫該結(jié)點數(shù)據(jù) for (i=0; in; i+) /在中序序列中查找根結(jié)點，然后，左右子女信息入隊列 if (ini=level0) break; if (i=0) /根結(jié)點無左子樹，遍歷序列的1n-1是右子樹 p-lchild=null; s.lvl=+r; s.l=i+1; s.h=n-1; s.f=p; s.lr=2; enqueue(q,s); else if (i=n-1) /根結(jié)點無右子樹，遍歷序列的1n-1是左子樹 p-rchild=null; s.lvl=+r; s.l=1; s.h=i-1; s.f=p; s.

10、lr=1; enqueue(q,s); 2021年湖北省基礎數(shù)據(jù)要領 else /根結(jié)點有左子樹和右子樹 s.lvl=+r; s.l=0; s.h=i-1; s.f=p; s.lr=1;enqueue(q,s);/左子樹有關信息入隊列 s.lvl=+r; s.l=i+1;s.h=n-1;s.f=p; s.lr=2;enqueue(q,s);/右子樹有關信息入隊列 while (!empty(q) /當隊列不空，進行循環(huán)，構(gòu)造二叉樹的左右子樹 s=delqueue(q); father=s.f; for (i=s.l; i=s.h; i+) if (ini=levels.lvl) break;

11、p=(bitreptr)malloc(sizeof(binode); /申請結(jié)點空間 p-data=levels.lvl; p-lchild=null; p-rchild=null; /填寫該結(jié)點數(shù)據(jù) if (s.lr=1) father-lchild=p; else father-rchild=p； /讓雙親的子女指針指向該結(jié)點 if (i=s.l) p-lchild=null; /處理無左子女 s.lvl=+r; s.l=i+1; s.f=p; s.lr=2; enqueue(q,s); else if (i=s.h) p-rchild=null; /處理無右子女 s.lvl=+r; s.h=i-1; s.f=p; s.lr=1; enqueue(q,s); elses.lvl=+r; s.h=i-1; s.f=p; s.lr=1; enqueue(q,s);/左子樹有關信息入隊列 s.lvl=+r; s.l=i+1; s.f=p;