(1)有且仅有一个称为根的结点

树集合图凹入树形定义：(1)有且仅有一个称为根的结点；(2)其余的结点可分为m(m≥0)个互不相交的子树Tl，T2，…，Tm。术语：孩子、双亲、兄弟、祖先、子孙度分支结点、叶子结点层数、深度有序树、无序树森林1练习已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问树中有多少个叶子结点？s=n0+n1+n2+……+nms=n1+2n2+……+mnm+1n0=1+n2+2n3+……+(m-1)nm2练习3二叉树(BinaryTree)1.递归定义

二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。2．二叉树的基本形态

4二叉树的性质在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=第i层上的结点数目最多为2i-1深度为k的二叉树至多有个结点2k-1n2+15练习画出由三个结点a、b、c组成的所有不同结构的二叉树，共有多少种不同的结构？24种6满二叉树(FullBinaryTree)定义

一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点：（1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。（2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。7完全二叉树(CompletebinaryTree)

至多只有最下面的两层上结点的度数小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。8完全二叉树特点满二叉树是完全二叉树，完全二叉树不一定是满二叉树。在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。9完全二叉树特点具有n个结点的完全二叉树的深度为[log2(n)]+1或[log2(n+1)]

2h-1-1＜n≤2h-12h-1＜n+1≤2hh-1＜log2(n+1)≤hlog2(n+1)≤h<log2(n+1)+1h=[log2(n+1)]10二叉树的顺序存储结构1．完全二叉树结点编号及特点结点i(1≤i≤n)[i/2]i>12i2i≤n2i+1≤n2i+1i-1i为奇数

i<>1i为偶数

i<ni+111二叉树的顺序存储结构完全二叉树的顺序存储一般二叉树的顺序存储12优点和缺点对完全二叉树而言，顺序存储结构既简单又节省存储空间。一般的二叉树采用顺序存储结构时，虽然简单，但易造成存储空间的浪费。在对顺序存储的二叉树做插入和删除结点操作时，要大量移动结点。

13链式存储结构及定义leftdatarighttypebtree=^node;node=recorddata:char;left,right:btree;end;varroot:btree;typesbtree=recorddata:char;left,right:integer;end;varroot:sbtree;动态静态14练习画出图示二叉树的存储形式（动态/静态）15注意一个二叉链表由根指针root唯一确定。若二叉树为空，则root=nil；若结点的某个孩子不存在，则相应的指针为空。具有n个结点的二叉链表中，共有_____个指针域。其中只有____个用来指示结点的左、右孩子，其余的____个指针域为空。二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。例：带双亲指针的二叉链表

16二叉树的生成运用顺序存储思想，输入结点字串（#表示空结点，@表示输入结束），生成相应的二叉树。(eg:abc##de#####gf@)分析：为了便于双亲和子女的链接，引用结点指针队列q[1..n],parent和child分别指向当前的双亲和子女。由child值判断该结点的性质。child=1:根child为偶数:左孩子child为奇数:右孩子17{初始化}root:=nil;child:=0;parent:=1;read(ch);{生成结点}s:=nil;ifch<>’#’thenbeginnew(s);s^.data:=ch;s^.left:=nil;s^.right:=nil;end;{结点入队列}child:=child+1;q[child]:=s;{与双亲链接}ifchild=1thenroot:=s{为根}elsebeginifs<>nilthen ifchildmod2=0thenq[parent]^.left:=selseq[parent]^.right:=s;ifchildmod2=1thenparent:=parent+1;end;whilech<>’@’dobeginread(ch);end;18qabc##de#####gf@parentchildaroot→bc19由广义表生成二叉树a(b(d),c(e,f))p93由先序遍历生成二叉树演示20二叉树的遍历遍历：按照一定的顺序访问二叉树的每个结点，并且每个结点只被访问一次。根(n)、左子树(l)、右子树(r)：nlrnrllnrlrnrnlrln先序遍历(nlr)中序遍历(lnr)后序遍历(lrn)abdegcfhidbgeachfidgebhifca21练习一只一棵二叉树的先序遍历结果为：abcdefghi；中序遍历结果为：cbafegdhi，请写出后序遍历结果并画出这棵二叉树。22遍历的递归算法（树非空）中序遍历：(1)遍历左子树；

(2)访问根结点；

(3)遍历右子树。proceduremvisit(bt);begin ifbt<>nilthenbegin mvisit(bt^.left);write(bt^.data); mvisit(bt^.right);end;end;

先序遍历：(1)访问根结点；(2)遍历左子树；

(3)遍历右子树。后序遍历：(1)遍历左子树；(2)遍历右子树；

(3)访问根结点。23求二叉树的深度分析：若一二叉树为空，则深度为0，否则，等于左子树和右子树的最大深度加1。functiondepth(bt):integer; begin ifbt=nilthendepth:=0elsebegin depl:=depth(bt^.left); depr:=depth(bt^.right); ifdepl>deprthendepth:=depl+1 elsedepth:=depr+1; end; end;24将二叉树以广义表形式输出分析：首先输出根结点，然后依次输出左子树和右子树，打印左子树前输出“(”，输出右子树后输出“)”。25procedureprint(bt);beginifbt<>nilthen begin write(bt^.data); if(bt^.left<>nil)or(bt^.right<>nilthen begin write(‘(‘); print(bt^.left); ifbt^.right<>nilthenwrite(‘,’); print(bt^.right); write(‘)’); end; end;end;

26作业1,建立一棵二叉树。2,写出中序遍历的非递归算法3,写出在二叉树上进行查找值为x的结点，如果存在，则输出它的所在层数，并删