数据基础教程13

二叉树也称为二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。二叉树中许多概念与树中的概念相同。在含n个结点的二叉树中，所有结点的度小于等于2，通常用n0表示叶子结点个数，n1表示单分支结点个数，n2表示双分支结点个数。7.2.1二叉树的概念7.2二叉树1.二叉树的定义1/35度为2的树至少有3个结点，而二叉树的结点数可以为0。度为2的树不区分子树的次序，而二叉树中的每个结点最多有两个孩子结点，且必须要区分左右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。提示二叉树与度为2的树是不同的。2/35归纳起来，二叉树的5种形态：Ø(a)空二叉树(b)只有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树非空的二叉树3/35ADTBTree{

数据对象： D={ai|1≤i≤n，n≥0，ai为E类型}//为了简单，假设E为char

数据关系： R={r} r={<ai，aj>|ai，aj∈D，1≤i，j≤n，当n=0时，称为空二叉树；

否则其中有一个根结点，其他结点构成根结点的互不相交的左、右子

树，该左、右两棵子树也是二叉树}

基本运算： voidCreateBTree(stringstr)：由二叉树括号表示串建立其存储结构。 StringtoString()：返回由二叉树树转换的括号表示串。 BTNodeFindNode(x)：在二叉树中查找值为x的结点。 intHeight()：求二叉树的高度。

…}2.二叉树抽象数据类型的描述4/353.满二叉树和完全二叉树在一棵二叉树中，如果所有分支结点都有左孩子结点和右孩子结点，并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。可以对满二叉树的结点进行层序编号，约定编号从树根为1开始，按照层数从小到大、同一层从左到右的次序进行。满二叉树也可以从结点个数和树高度之间的关系来定义，即一棵高度为h且有2h-1个结点的二叉树称为满二叉树。ABDHIEJKCFLMGNO1248951011361213714155/35满二叉树的特点如下：叶子结点都在最下一层。只有度为0和度为2的结点。含n个结点的满二叉树的高度为log2(n+1)，叶子结点个数为

n/2

+1，度为2的结点个数为

n/2

。ABDHIEJKCFLMGNO124895101136121371415n=15h=log2(n+1)=46/35若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。同样可以对完全二叉树中每个结点进行层序编号，编号的方法同满二叉树相同，图中每个结点外边的数字为对该结点的编号。ABDHIEJKCFG12489510113677/35完全二叉树的特点如下：叶子结点只可能出现在最下面两层中。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。如果有度为1的结点，只可能有一个，且该结点只有左孩子而无右孩子；按层序编号后，一旦出现某结点（其编号为i）为叶子结点或只有左孩子，则编号大于i的结点均为叶子结点。ABDHIEJKCFG12489510113678/357.2.2二叉树性质性质1

非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1。总结点数n=n0+n1+n2。一个度为1的结点贡献1个度，一个度为2的结点贡献2个度，所以总的度数=n1+2n2。总的度数=总分支数=n-1。则n1+2n2=n0+n1+n2-1，求出n0=n2+1。证明：在二叉树中计算结点时常用的关系式有：①所有结点的度之和=n-1②所有结点的度之和＝n1＋2n2

③n=n0+n1+n2。归纳9/35性质2

非空二叉树上第i层上至多有2i-1个结点，这里应有i≥1。

由树的性质2可推出。性质3

高度为h的二叉树至多有2h-1个结点（h≥1）。

由树的性质3可推出。10/35性质4对完全二叉树中层序编号为i的结点（1≤i≤n，n≥1）有：

（1）若i≤

n/2

，即2i≤n，则编号为i的结点为分支结点，否则为叶子结点。

（2）若n为奇数，则n1=0，这样每个分支结点都是双分支结点；若n为偶数，则n1=1，只有一个单分支结点，该单分支结点是编号最大的分支结点（编号为

n/2

）。

（3）若编号为i的结点有左孩子结点，则左孩子结点的编号为2i；若编号为i的结点有右孩子结点，则右孩子结点的编号为2i+1。

（4）若编号为i的结点有双亲结点，其双亲结点的编号为

i/2

。i/2i2i2i+111/35

性质5

具有n个（n＞0）结点的完全二叉树的高度为

log2(n+1)

或

log2n

+1。

由完全二叉树的定义和树的性质3可推出。一棵完全二叉树中，由结点总数n可以确定其树形。n1只能是0或1，当n为偶数时，n1=1，当n为奇数时，n1=0。层序编号为i的结点层次恰好为

log2(i+1)

或者

log2i

+1。归纳12/35

【例7.2】一棵含有882个结点的二叉树中有365个叶子结点，求度为1的结点个数和度为2的结点个数。这里n=882，n0=365。由二叉树的性质1可知n2=n0-1=364。n=n0+n1+n2，即n1=n-n0-n2=882-365-364=153。所以该二叉树中度为1的结点和度为2的结点个数分别是153和364。13/35【例7.5】一棵完全二叉树中有501个叶子结点，则至少有多少个结点。该二叉树中有，n0=501。由二叉树性质1可知n0=n2+1，所以n2=n0-1=500。n=n0+n1+n2=1001+n1，由于完全二叉树中n1=0或n1=1，则n1=0时结点个数最少，此时n=1001，即至少有1001个结点。14/357.2.3二叉树存储结构1.二叉树的顺序存储结构顺序存储一棵二叉树时，就是用一组连续的存储单元存放二叉树中的结点。由二叉树的性质4可知，对于完全二叉树（或满二叉树），树中结点层序编号可以唯一地反映出结点之间的逻辑关系，所以可以用一维数组按从上到下、从左到右的顺序存储树中所有结点值，通过数组元素的下标关系反映完全二叉树或满二叉树中结点之间的逻辑关系。15/35一棵完全二叉树的顺序存储结构1234567891011121314…ABCDEFGHIJK####位置sbABDHIEJKCFG124895101136716/35ABDEGHCFKABDEGHCFK1248951011361271413增添空结点补齐为一棵完全二叉树并对所有结点进行编号一般的二叉树的顺序存储结构设计：17/351234567891011121314…ABCDE#F##GH##K#位置sb仅保留实际存在的结点值，其他为空ABDEGHCFK124895101136127141318/35

二叉树顺序存储结构采用这样的数组存放（假设每个结点值为单个字符）：

Stringsb; //二叉树的顺序存储结构用sb字符串存储

当二叉树中某结点为空结点或无效结点（不存在该编号的结点）时，对应位置的值用特殊值（如'#'）表示。19/35完全二叉树或满二叉树采用顺序存储结构比较合适如果需要增加很多空结点才能将一棵二叉树改造成为一棵完全二叉树，采用顺序存储结构会造成空间的大量浪费，这时不宜用顺序存储结构。h=4MazSize=24-1=15空间利用率=4/15=27%优缺点20/352.二叉树的链式存储结构ABCEFDG二叉链存储结构AB∧C∧D∧E∧∧G∧∧F∧b21/35对应Java语言的二叉链结点类BTNode<E>classBTNode<E>{

//二叉链中结点类Edata; //存放数据元素BTNodelchild; //指向左孩子结点BTNoderchild; //指向右孩子结点publicBTNode(){

//默认构造方法lchild=rchild=null;}publicBTNode(Ed){

//重载构造方法data=d;lchild=rchild=null;}}22/357.2.4二叉树的递归算法设计对于二叉树b，设f(b)是求解的“大问题”。f(b->lchild)和f(b->rchild)为“小问题”。假设f(b->lchild)和f(b->rchild)是可求的，在此基础上得出f(b)和f(b->lchild)、f(b->rchild)之间的关系，从而得到递归体。再考虑b=NULL或只有一个结点的特殊情况，从而得到递归出口。一般地，二叉树的递归结构如下：bf(b)b->lchildf(b->lchild)b->rchildf(b->rchild)23/357.2.5二叉树的基本运算及其实现1.二叉树类设计publicclassBTreeClass{

//二叉树类BTNode<Character>b; //根结点Stringbstr; //二叉树的括号表示串publicBTreeClass(){ //构造方法b=null;}//二叉树基本运算算法}

为了简单，本节讨论的二叉树中所有结点值为单个字符。逻辑结构采用括号表示串，存储结构采用二叉链。24/352.二叉树的基本运算算法实现（1）创建二叉树CreateBTree(str)str逻辑结构b存储结构正确的括号表示串（每个结点值为单个字符）25/35用ch扫描str，其中只有4类字符，各类字符的处理方式如下：若ch='('：表示前面刚创建的p结点存在着孩子结点，需将其进栈。然后开始处理该结点的左孩子，因此置flag=true，表示其后创建的结点将作为这个结点（栈顶结点）的左孩子结点。若ch=')'：表示以栈顶结点为根结点的子树创建完毕，将其退栈。若ch=','：表示开始处理栈顶结点的右孩子结点，置flag=false。其他情况：只能是单个字符，表示要创建一个新结点p，根据flag值建立p结点与栈顶结点之间的联系，当flag=true时，表示p结点作为栈顶结点的左孩子结点，当flag=false时，表示p结点作为栈顶结点的右孩子结点。26/35publicvoidCreateBTree(Stringstr){

Stack<BTNode>st=newStack<BTNode>();

//建立一个栈stBTNode<Character>p=null;booleanflag=true;charch;inti=0;由括号表示层str创建以b为根结点的二叉链存储结构27/35while(i<str.length()){ //循环扫描str中每个字符ch=str.charAt(i);switch(ch){ case'(': st.push(p); //刚刚新建的结点有孩子,将其进栈flag=true;break; case')':st.pop(); //栈顶结点的子树处理完，出栈break; case',':flag=false; //开始处理栈顶结点的右孩子break;28/35default:p=newBTNode<Character>(ch); //用ch值新建一个结点if(b==null)b=p; //若尚未建立根结点,p作为根结点else{ //已建立二叉树根结点if(flag){ //新结点p作为栈顶结点的左孩子if(!st.empty())st.peek().lchild=p;}else{ //新结点p作为栈顶结点的右孩子if(!st.empty())st.peek().rchild=p;}}break;}i++; //继续遍历}}29/35str="A(B(D(，G))，C(E，F))"AB∧C∧D∧E∧∧G∧∧F∧b30/35（2）返回二叉链的括号表示串toString()publicStringtoString(){ //返回二叉链的括号表示串bstr="";

toString1(b);returnbstr;}privatevoidtoString1(BTNode<Character>t){//被toString方法调用if(t!=null){bstr+=t.data; //输出根结点值if(t.lchild!=null||t.rchild!=null){bstr+="("; //有孩子结点时输出"("

toString1(t.lchild); //递归输出左子树if(t.rchild!=null)bstr+=","; //有右孩子结点时输出","

toString1(t.rchild); //递归输出右子树bstr+=")"; //输出")"}}}31/35（3）查找值为x的结点FindNode(x)设f(t，x)在以t为根结点的二叉树中查找值为x的结点，找到后返回其地址，否则返回null。f(t，x)=null 若t=nullf(t，x)=t 若t.data=xf(t，x)=p

若在左子树中找到了，即

p=f(t.lchild，x)且p!=nullf(t，x)=f(t.rchild，x)

其他情况32/35publicBTNode<Character>FindNode(charx){

//查找值为x的结点算法returnFindNode1(b,x);}privateBTNode<Character>FindNode1(BTNode<Character>t,charx){//被FindNode方法调用BTNode<Charac