數(shù)據(jù)結(jié)構(gòu)教程--樹的遍歷及二叉樹

1、樹的遍歷 按照一定的規(guī)則將樹中所有結(jié)點的數(shù)據(jù)信息排列成一個線性序列 樹的前序遍歷 樹的后序遍歷 樹的層次遍歷 獲得樹中所有葉子結(jié)點樹的前序遍歷 首先訪問根結(jié)點,然后按前序遍歷根結(jié)點的各棵子樹 所得結(jié)點序列是唯一的 前序遍歷的定義是遞歸的ABECFGHD#include #define MAXM 10struct node char data; struct node *chileMAXM; ;typedef struct node NODE;int m;NODE *t;void r_preorder (t,m)NODE *t;int m; int i; if (t!=NULL) printf(

2、“%c”,t-data); for (i=0;ichildi!=NULL) r_preorder(t-childi,m); 樹的前序遍歷A地址210BCD210輸出A,A出棧A的孩子D,C,B進棧樹的前序遍歷CD210輸出B,B出棧ECD210B的孩子進棧樹的前序遍歷CD210輸出E,E出棧D210輸出C,C出棧樹的前序遍歷FGD210GD210輸出F,F出棧C的孩子進棧void s_preorder(t,m)NODE *t;int m; NODE *s100; int top,i; if (t= =NULL) return; s0=t; top=1;while (top0) t=s-top;

3、 printf(“%c”,t-data); for(i=m-1;i=0;i-) if (t-childi!=NULL) stop+=t-childi; 樹的后序遍歷 首先按后序遍歷根結(jié)點的各棵子樹,然后訪問根結(jié)點EBFHGCDA一棵3次有序樹其前序,后序的遍歷結(jié)果為: 前序: ABCDEFGHI 后序:BCGHFEIDA則該3次有序樹用圖形表示應(yīng)為什么?樹的層次遍歷 首先訪問處于第0層上的根結(jié)點,然后訪問處于第一層上的結(jié)點,再訪問處于第二層上的結(jié)點,再依次訪問以下各層上的結(jié)點ABCDEFGH樹的層次遍歷A輸出A,A出隊 B C DheadtailheadtailA的孩子進隊qq樹的層次遍歷 C

4、 DheadtailB的孩子進隊q輸出B,B出隊 C D Eheadtailq樹的層次遍歷 D EheadtailC的孩子進隊q輸出C,C出隊 D E F Gheadtailqvoid levorder(t,m)NODE *t;int m; NODE *q100,*p; int head,tail,i; q0=t; head=0; tail=1; while(headdata); for(i=0;ichildi!=NULL) qtail+=p-childi; 獲得樹中所有葉子結(jié)點 如樹中只有一個結(jié)點,則此結(jié)點就是此樹的葉子結(jié)點 樹中的葉子結(jié)點就是根結(jié)點的各棵子樹的葉子結(jié)點EFHD樹的線性表示

5、把樹的結(jié)點輸入計算機中,從而建立樹的結(jié)構(gòu) 樹的層號表示 樹的括號表示樹的層號表示 結(jié)點k的層號lev(k): 如果k是k的子結(jié)點,則 lev(k)lev(k) 如果k和k”同是結(jié)點k的子結(jié)點,則 lev(k”)=lev(k) 結(jié)點的層號不是唯一的 結(jié)點所在的層次是唯一的10202030303023 4040352525按前序?qū)懗鰳渲腥拷Y(jié)點按前序?qū)懗鰳渲腥拷Y(jié)點,并在結(jié)點之前帶上結(jié)點的層號并在結(jié)點之前帶上結(jié)點的層號(10,A),(20,B),(30,D),(30,E),(40,H),(40,I).(25,L)(0,A),(1,B),(1,C),(2,D),(2,E),(3,H),(3,I).(

6、4,L)011#include #define MAXM 10#define MAXN 100struct node int lev; char data; struct node *childMAXM; struct node *parent; ;typedef struct node NODE;typedef struct dnode int lev; char data; DNODE;DNODE aMAXN;int n,m;10202030303023 4040352525(10,A),(20,B),(30,D),(30,E),(40,H),(40,I),(30,F),(35,J)(20

7、,C),(23,G),(25,K),(25,L)30 E 10 A P20 B q30 D q(10,A),(20,B),(30,D),(30,E),(40,H),(40,I),(30,F),(35,J)(20,C),(23,G),(25,K),(25,L)NODE *lev_tree(a,m,n) DNODE a ; int m,n; int i,j; NODE *root,*p,*q; if (nlev=a0.lev; root-data=a0.data; for(i=0;ichildi=NULL; root-parent=NULL;p=root;for(i=1;ilev=ai.lev;

8、q-data=ai.data; for(j=0;jchildj=NULL; while (q-levlev) p=p-parent; q-parent=p; j=-1; while (p-child+j!=NULL) ; p-childj=q; p=q;return(root);樹的括號表示 設(shè)T是一棵樹,樹T的括號表示的規(guī)則如下: 如果樹T只有一個結(jié)點,則此結(jié)點就是它的括號表示 如果樹T是由樹根結(jié)點A和子樹T0,T1,.Tm-1組成,則樹T的括號表示是:A(T0的括號表示,T1的括號表示,.Tm-1的括號表示)A(B(D,E(H,I),F(J),C(G(K,L)A(B(C,D(E),F)字符

9、:為樹中的一個結(jié)點,申請空間( : 子樹開始,其前一個字符為子樹的根結(jié)點, : 已開始構(gòu)造某子樹的某子結(jié)點): 此子樹已處理完#include #include #define MAXM 3#define MAXN 100struct node char data; struct node *childMAXM; ;typedef struct node NODE;char aMAXN;int m;A(B(C,D(E),F)A 讀A讀(A地址p讀BB pA(B(C,D(E),F)讀(BA讀CC p讀, 取棧頂值給q q=BA B C BAA(B(C,D(E),F)讀DD p讀(DBA讀EE p

10、讀) 出棧并將值送給q q=DD E BA#include #include #define MAXM 3#define MAXN 100struct node char data; struct node *childMAXM; ;typedef struct node NODE;char aMAXN;int m;NODE *kh_tree(a,m) char a ; int m; NODE *stackMAXN,*p=NULL,*q; char ch; int i,k=0,top=0; ch=a0; while (ch!=0) if (isalpha(ch) p=(NODE*) mallo

11、c(sizeof(NODE); p-data=ch; for(i=0;ichildi=NULL; else switch(ch) case (: stacktop+=p; break; case ,: q=stacktop-1; i=-1; while (q-child+i!=null) ; q-childi=p; break; case): q=stack-top; i=-1; while (q-child+i!=null); q-childi=p; p=q; ch=a+k; return(p);1.一棵共有n個結(jié)點的樹,其中所有分枝結(jié)點的度 均為k,求該樹中葉子結(jié)點的個數(shù).2.試證明:在具

12、有n個結(jié)點的m次樹中,有n(m-1)+1個 指針是空的.作業(yè)1.一棵3次有序樹其前序,后序的遍歷結(jié)果為: 前序: ABECFGHD 后:EBFHGCDA 則該3次有序樹用圖形表示應(yīng)為什么?2.已知有序樹的層號表示,用圖形表示該有序樹. (5,A)(10,B)(20,E)(10,C)(15,F)(15,G)(18,H)(10,D)二叉樹 是n=0個結(jié)點的有窮集合T n=0時,稱該二叉樹為空二叉樹 n0時,它包含一個根結(jié)點以及二棵不相交的分別稱之為左子樹和右子樹的二叉樹 與樹的區(qū)別: 二叉樹可以為空 樹不能為空 與二次有序樹的區(qū)別: 嚴(yán)格區(qū)分左右孩子包含三個結(jié)點的二叉樹包含三個結(jié)點的二叉樹可能具有

13、多少種形態(tài)可能具有多少種形態(tài)?滿二叉樹:若一棵二叉樹中任何結(jié)點,或者是葉子結(jié)點,或者有兩棵非空子樹,并且葉子結(jié)點都集中在二叉樹的最下一層完全二叉樹(擬滿樹)若一棵二叉樹中最多只有最下面兩層的結(jié)點的度數(shù)可以小于2,并且最下面一層的結(jié)點都依次排列在該層最左邊的位置豐滿二叉樹若一棵二叉樹中最多只有最下面兩層的結(jié)點的度數(shù)可以小于2,最下一層的結(jié)點隨意分布在第i層上二叉樹的性質(zhì) 一棵非空二叉樹的第i層最多有2i個結(jié)點(i=0) 深度為k的二叉樹最多有2k+1-1個結(jié)點(k=0) 任意非空二叉樹中,若葉子結(jié)點的數(shù)目為n0,度為2的結(jié)點數(shù)目為n2,則有n0=n2+1將任意次樹轉(zhuǎn)換成相應(yīng)的二叉樹 把具有m個子

14、結(jié)點k0,k1,km-1的結(jié)點k轉(zhuǎn)換成以k0作為結(jié)點k的左子結(jié)點,并且ki+1作為ki的右子結(jié)點 將所有相鄰兄弟結(jié)點用線連接 對每個非終端結(jié)點,除最左孩子外,刪去該結(jié)點與其他孩子結(jié)點的連線 以根結(jié)點為軸,順時針旋轉(zhuǎn)45度將任意次樹轉(zhuǎn)換成相應(yīng)的二叉樹樹林與二叉樹的轉(zhuǎn)換 分別將樹林中的每棵樹轉(zhuǎn)換為二叉樹 從最后一棵二叉樹開始 ,依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹的根結(jié)點的右孩子,直到所有二叉樹全部連接二叉樹還原為一般樹 若某結(jié)點是雙親結(jié)點的左孩子,則將該結(jié)點的右孩子以及當(dāng)且僅當(dāng)連續(xù)地沿此右孩子的右子樹方向不斷地搜索到的所有右孩子,都分別與該結(jié)點的雙親結(jié)點用虛線連接起來 刪去原二叉樹中所有雙

15、親結(jié)點與右孩子的連線 將圖形規(guī)整化,.1.設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對應(yīng)的二叉樹為B.已知T1,T2,T3的結(jié)點數(shù)分別為n1,n2,n3,則二叉樹B的左子樹中的( )個結(jié)點,二叉樹B的右子樹中有( )個結(jié)點.2.一棵有124個葉結(jié)點的完全二叉樹,最多有( )個結(jié)點. 3.一棵有n個結(jié)點的滿二叉樹有( )個度為1的結(jié)點,有( )個分支結(jié)點和( )葉子,該滿二叉樹的深度為( ).4.包含結(jié)點A,B,C的二叉樹有( )種不同的形態(tài),( )種不同的二叉樹.5.包含結(jié)點A,B,C的樹有( )種不同的形態(tài),( )種不同的樹. 6.若一棵二叉樹的葉子數(shù)為n0,則該二叉樹中左右子樹皆非空的結(jié)點個數(shù)為(