计算机数据结构和二叉树

1遍历方式的递归和非递归算法。(3过程和算法；(4 23

A

D了树的概念。 了树的概念。

6.1T={A,B,C,D,E,F,G,H,I,T1={B,E,F，K，L},T2={C,G},T3={D,H,I, A 6

A

A

A C

AABCDEKFGHIJ文件夹11文件夹12文件11文件

6.1AA

(A）第一层(A(B, KJ MHKJI

D

(A(B(E,FC(GD(H,I,J)))(A(B(E(K,L),FC(G G

6.1 叶子结点：也叫终端结点，是度为0的结点；树的度为树的深度为 树的度为树的深度为

树的抽象数据型 A

ADTTree当n>1时，其余结点可分为mm>0)个互不相交的有限集T1,T2,…,Tm，其中每

} Value(T,cur_e)//求当前结点的元素值Parent(T,cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(Tcur_e)求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTreeTVisit())

InitTree(&T)//初始化置空树CreateTree(&T,definition) Assign(T,cur_e,value) //给当前结点赋值 //将树清空DestroyTree(&T)//销毁树的结构DeleteChild(&T&p,i)删除结点p的第i棵

二叉树A

二叉树 G

G

G

φ

-(a)空 (b)仅有 (c)

、 根节点是运算符 (d) (e)左、 二叉树

性质2深度为k的二叉树最多有2k-1个结点。 E I 完全二叉树：二叉树中所含的n个结点和满二叉树中编号为1至

完全二叉树：二叉树中所含的n个结点和满二叉树中编号为1至

E

89 性质3具有n个结点的完全二叉树的深度为log2n

性质4对任意二叉树T，如果度数为0的结点数为n0证明：二叉树T的结点总数

二叉树的分支总数b=n-1（根结点无进入分支） 由于k为整数，故有k-1=logn

则有分支总数b=n1+2*n2

log2n

D

由(1)(2)(3)得求得 注意：n个度为注意：n个度为的结点发出n支， E 性质5:若对含n个结点的完全二叉树从上到下且从左至右进若i/2的结点为其双亲的结点为其右孩子

i=1是根结 双亲为i/2 为双亲为i/2 为双亲为i/2 i

二叉

性质5:若对含n1至n

ii

1 4

9

ABCDEFGABCDEFGHIJ

B 0JABC0E0G00J1

6 9

A

C语言的类型描述如下typedefstruct

∧C ∧C∧∧E∧∧E∧∧∧∧∧DataTypestructBiTNode*lch,}BiTNode,*

A

针域的结点；

C语言的类型描述如下 ∧∧∧E∧

数为：2n（n-1）

typedefstructBiTNode∧F

structBiTNode}BiTNode,* A

ABB

BiTree*{t=C CE EFF

t‐>data=t‐>lch=CreateBiTree();t‐>rch=CreateBiTree();returnt;} 6.3二叉树的遍 遍历：按某种搜索路

6.3二叉树的遍历先上后下

先左 ）后右

TLR，LTR，LRTRL，RTL，RL

GTLR、LTR、LRT，分 6.3.1先序遍历（TL 例先序遍历右图所示的二叉 ：即按TLR的顺序遍历 ：即按TLR的顺序遍历

中序遍历（LTRA G DBG,E,A,C 后序遍历（LRT

例

G

：即按LRT的顺序遍历 ：即按LRT的顺序遍历

先序：-,+,a,*,b,- 中序：a,+,b,*,c,-,d,- 后序遍历序列：

6.3二叉树的遍历

先序遍历（TLR） 若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项

voidPreOrder(BiTreeT){if(T){∧a∧PreOrder(T->lch);∧a∧}}

* /*/-∧-∧∧∧b∧∧b∧∧c∧++

voidInOrder(BiTreeT) if*{*∧a∧visit(T->data)∧a∧∧b∧b∧}

++/-∧d-∧d∧∧e∧∧c∧∧∧*abcde称为前缀表达

a*b–c+de称为中缀表达

6.3二叉树的遍历+voidPostOrder(BiTreeT)+if*/{*/∧a∧-∧d∧∧e∧∧a∧-∧d∧∧e∧∧b∧∧b∧∧c∧}abc*de/+称为后缀表达

voidPreOrder(BiTreet)1（TLR）对每个结点，在完后，沿其左链一直下来，直到左链为空，这时，所有已被过的结点进栈。然后结点出栈，对于每个出栈结点，即表示该结点和其左已被结束，应该该结点的右。

PSeqStackBiTreep=t;/**/S=Init_SeqStack();/*栈初始化*/whilep||!Empty_SeqStack({if(p)visit(p->data)/*预留p指针在栈中*/Push_SeqStackS,p);p=p->lch;

{Pop_SeqStack(S,&pp=p-}/* }//end}//end步骤(2)，直到左孩子为 voidPreOrder(NODE*root)

+ + inttop=0;p=root;dowhile(p!=NULL){

toptoptoptop

node[

p p- pp }if(top>0)top--; p=p->rch;}while(top>0||}

,]ta); ;;>lch;

if(!T)returnwhile(T->lch) Push(S,

emType&e))StacktGoFarLeft(TS);while(t){T=T-}

if(t-t=GoFarLeft(t->rch,elseif!StackEmpty(S return }

}//}//

t=tNULL

typedefstruct{BiTNode*node;intflag;voidPostOrder(BiTreet){PSeqStackS;DataTypeinttag;BiTreep=S=Init_SeqStack();/*栈初始化*/while(p||!Empty_SeqStack(S))if(p)Sq.flag=0;Push_SeqStack(S,Sq);p=p-}

elsePop_SeqStackp=if(Sq.flag==0){p=p->rch;}elsevisit(p-p=null;/*把p赋空从 }}//end}end A

voidLevelOrder(BiTreeT){BiTreeP=T;if(P)Init_SeqQueue(Q);//

visit(P);In_SeqQueue(Q,P); while(!Empty_SeqQueue(Q)){//当队非空时重复执行下列操作 }} 例例求二叉树的叶子数。算法思想：采用任何遍历方法，

intcountleaf(bitreet,intnum){if(t!=NULL){if((t->lch==NULL)&&(t-num=countleaf(t->lch,num);num=countleaf(t->rch,}} 例求二叉树的深度。算法思想：从第一层的根结点开始往例求二叉树的深度。算法思想：从第一层的根结点开始往inttreedepth(bitree*t){inth,lh,rh; else returnh;}

DC

给定先序和后序不能

例先序：12例先序：1246357中序：26

(1

intEQUAL(BiTreet1,BiTreet2)intx=if(ISEMPTY(t1)&&ISEMPTY(t2))x=1;elseif(!ISEMPTY(t1)&&!ISEMPTY(t2))if(DATA(t1)==DATA(t2))if(EQUAL(LCHILD(t1),LCHILD(t2)))x=EQUAL(RCHILD(t1),RCHILD(t2))return}/*EQUAL

BiTreeCOPY(BiTreeoldtree)BiTreetempif(oldtree!=NULL){temp=newNodetemp->lch=COPY(oldtree->lch);temp->rch=COPY(oldtree->rch);temp->data=oldtree->data;return(temp);}return(NULL)} 6.5线索二叉

6.5

6.5typedefstructtypedefstructnodedatatypestructnode*lch,*rch;intltag,rtag;}threadbithptr,

6.5线索二叉树：

6.5线索二叉树 二叉树的根结点，其rchild域指向中序遍历时的最后

00*1d1a0-1b1c10-100-00-0 A

0000A0010B10

11001E001E1

00A00

1D1G1

11

1F

Thrt->lchT二叉树的根Thrt->lchThrtThrt->rchThrtThrt->lchThrtThrt->rchThrtThrt->ltag=0;Thrt->rtag=1;T0B001D011G

C110011F11001

0A0B 0C1D 1E 1F1G

A

线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继信息只有在遍历时才能得到，因此线索化的过程即为在遍历过程中修改算法中附设一个指针pre始终指向刚刚过的结点，若指针p指向当前的结点，则pre指向它的前

,

T ∧

∧

0∧ ∧

0∧ ∧ ∧G∧

if(!(Thrt=(threadbithptr ∧

exitThrt->ltag=0;Thrt->rtag=1;Thrt->rch=Thrt; ∧

0∧ ∧

0∧ ∧

return}// ∧G∧ if(!T)Thrt->lch=else pre=

P0

pre->rtag=1;}

0 ∧

∧0

00∧ ∧

0∧ ∧G∧ P

if(p) // //

{p->ltag=

p->lch=pre;

{pre->rtag= pre->rch=p;pre 1∧

∧ ∧

1∧ ∧

}//}//

// 6.5

threadbithptr*InOrderNext(threadbithptr*p)

若其左标志为“1threadbithptrif(p->rtag==1)//*P的 returnp->rch;else{//*P右 //找 returnq;(1)当p->rtag(1)当p->rtag1时，p->rch即为所求（线索）(2)当p->rtag=0时，p的

p

qq

} threadbithptr*InOrderPre(threadbithptr*p)threadbithptr*q;if(p->ltag==1)//*P的 returnp-else{//*P //找

if(p!=Null)//do p=InOrderNext(p);找*p}whilereturnq;(1)当p->ltag(1)当p->ltag1时，p->lch即为所求（线索）(2)当p->ltag=0时，p的 }

}

0101A001000 001000 11110D1 11110D1

而索树中结点的插入与删除则不同，因为要同时考虑11G11 例RS 。

例RS 。

W 例RS 。VoidRINSERT(threadbithptrS,R){if(S->rtag==1){ //右 R->rch=S->rch;R->rtag=S->rtag;R->ltag=1;R->lch=SS->rtag=0;S->rch=R;else{// w=InOrderNext(S)Rw->lch

}}

6.6

6.6.1树

typedefstructPTNode{Elemdata;intparent;}

A

data9A9A0B1C1D2E2F3G5H5I5123456采用一组采用一组连续

89

33

data∧0∧A AB2BC CC∧D ∧DE E

child

孩子结点结构: 双亲结点结构: 5∧∧∧642 5∧∧∧642

987∧G∧Ftypedef987∧G∧FtypedefstructCTNode{ structCTNode}∧H∧H∧I∧I

∧typedefstruct{∧typedefstruct{ //ChildPtr}

9∧9∧A0B1C1D2∧E2F3∧G5∧H5∧I5∧ 6∧5 6∧5 7 7

结点结构: ∧98typedefstructCSNode{∧98typedefstructCSNode{ structCSNode*firstchild,}CSNode,7带双亲的孩子链表9

parent

A∧A∧BB∧ C

6.6 BC ∧

E ∧F

∧∧I

A

AE

KL 任何一个森林或树可以唯一地对应到一棵

6.6

左右指的是在结构中自然形成的之间的次序），另 6.6.3树的遍T 先根顺序遍历T1先根顺序遍历T2

T后根顺序遍历T1 后根顺序遍历T2 …先根顺序遍历Tk

ACE

D K

A,B,E,H,I,J,C,D,C’,H,I,J,E,B,C,C’,K,G,D, 6.7树的应

typedeftypedefstructnode{keytypekey;infotypestructnode*lch,*}BSTNode,*8 8—12—45—54—60—67— 二叉排序树的优点：用二叉排序树作为树，把一个记录的关键码和记录的地址作为二叉排序树的结点，按关键码值8

bstnode*CreatBST(){bstnode*t,*s;while(key!=endflag){t=insertbts(t,s);

return}

例设查找的关键字序列

中序遍历二叉排序树可得到一个关键字有序的序列

BSTNode*searchbst(keytypekey,BSTree*t){if((T==NULL)||(T->key==key))return(T);}

BSTNode*insertbts(BSTNode*p,BSTNode*root)if(root==NULL)returnif(p->key<root-root->lch=insertbts(p,root->lch);root->rch=insertbts(p,root->rch);return(root); 首先查找到要删除的结点,删除结点后，仍保持二叉

若*p结点是叶子，则直接删除。空。（f->rch=NULL)

删除树叶结点

f

recordsdeletemin(F){recordstmp;BSTp;if(F->lch==NULL)p=Ftmp=F->data;F=F->rch;deletep;returntmp;}return(deletemin(F->lch)

DeleteBST(BiTreeTKeyTypekey)if(!T)returnFALSE;elseif(key==T->data.key)returnDelete(T);elseif(key<T->data.key)returnDeleteBST(T->lch,key);elsereturnDeleteBST(T->rch,key);returnTRUE;}}}

孩子应比最小元更小，如此一来就产生孩子应比最小元更小，如此一来就产生了，因此最 6.7

8

nSn

为什么Sn1

EI2×n，nI=2×1+3×2+1×3=EI2×n，n

A7BWPL=w

2 4 C4 7 5

752 DWPL最小

例构造以W=（5，14，40，26，10）为权

树时,

设F是由这n棵二叉树构成的集合，在F中选取两棵根结点树值最小的树作为左、右，构造一颗新的二叉树，置新二叉树根的权值=左、右根结点权值之和； 所示。

typedefstructfloatintlch,rch,CreatHuffmanTree(hufmtreetree[]){inti,j,p1,p2;floatsmall1,small2,for(i=0;i<m;i++){

//初始化}}

voidInputWeight(hufmtreeTfloatintfor(i=0;i<n;i++)}for(i=ni<m;i把合并后的结点放入向量p1=0; ////small1=maxval;

for(j=0;j<i-1;jif(tree[j].weight<small1)small2=small1//改变最小权，次小权及其位置small1=tree[j].weight;//找出最小的权值}elseif(tree[j].weight<small2){small2=tree[j].weight;//改变次小权及位置}// //新生成的结点放在向量tree[