搜索
6.1树的定义和基本术语1、树的定义树是由n(n≥0)个结点组成的有限集合。如果n=0，称为空树；否则，在一棵非空树中，满足如下两个条件：（1）有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；（2）除根以外的其它结点划分为m(m≥0)个互不相交的有限集合T0,T1,…,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。ABCDGFEHIJKLM2、树的表示（1）树型表示（直观表示法）6.1树的定义和基本术语ABCDGFEHIJKLM2、树的表示（1）树型表示（直观表示法）（2）二元组表示T=(D,R)D={A,B,C,D,E,F,G,H,I,J,K,L,M}R={A,B,A,C,A,D,B,E,B,F,C,G,D,H,D,I,D,J,E,K,E,L,H,M}6.1树的定义和基本术语ABCDGFEHIJKLM2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法6.1树的定义和基本术语ABCDGFEHIJKLMABEKLFCGDHMJI2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法（4）嵌套集合表示6.1树的定义和基本术语ABCDGFEHIJKLMAEDHJIKLMDGC2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法（4）嵌套集合表示（5）广义表表示（嵌套括号表示）6.1树的定义和基本术语ABCDGFEHIJKLM（A（B（E（K,L）,F）,C（G）,D（H（M）,I,J）））3、基本术语结点（node）：包含一个数据元素及若干指向其它结点的分支信息。结点的度(degree)：结点的子树个数叶结点(leaf)：度为0的结点，也称为终端结点。分支结点(branch)：度不为0的结点，也称为非终端结点。孩子结点(child)：一个结点的直接后继或某结点子树的根结点。双亲结点(parent)：一个结点的直接前驱或某个结点是其子树之根的双亲。6.1树的定义和基本术语ABCDGFEHIJKLM3、基本术语兄弟(sibling)结点:具有同一双亲的所有结点祖先(ancestor)结点:若树中结点k到ks存在一条路径，则称k是ks的祖先子孙(descendant)结点:若树中结点k到ks存在一条路径，则称ks是k的子孙结点所处层次(level):根结点的层数为1，其余结点的层，其余结点的层数为双亲结点的层数加1树的高度(depth):树中结点的最大层数树的度(degree):树中结点的最大度数6.1树的定义和基本术语ABCDGFEHIJKLM3、基本术语有序树子树的次序不能互换无序树子树的次序可以互换森林（Forest）互不相交的树的集合6.1树的定义和基本术语ABCDGFEHIJKLM4、树的基本操作①初始化②求指定结点所在树的根结点③求指定结点的双亲结点④求指定结点的某一孩子结点⑤求指定结点的最右边兄弟结点⑥将一棵树插入到另一树的指定结点下作为它的子树⑦删除指定结点的某一子树⑧树的遍历6.1树的定义和基本术语6.2二叉树(BinaryTree)6.2.1二叉树的定义1、二叉树（BinaryTree）或为空树，或由根及两棵不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两棵子树；二叉树每个结点度小于等于2;2）左、右子树不能颠倒——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;AFGEDCB6.2二叉树(BinaryTree)6.2.1二叉树的定义2、二叉树的五种不同形态二叉树的五种不同形态6.2二叉树(BinaryTree)6.2.1二叉树的定义3、二叉树和树的区别：二叉树不是树的特殊情形，它们是两个概念。树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。6.2二叉树(BinaryTree)6.2.2二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)性质2：深度为k的二叉树最多有2k-1个结点。(k≥1)性质3：对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1。6.2二叉树(BinaryTree)6.2.2二叉树的性质两种特殊的二叉树：满二叉树：深度为k且有2k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。123456789101112131415满二叉树6.2二叉树(BinaryTree)6.2.2二叉树的性质两种特殊的二叉树：完全二叉树：若设二叉树的高度为h，除第h层外，其它各层的结点数都达到最大个数，第h层的结点集中出现在左端若干连续位置上，这就是完全二叉树。完全二叉树1234567891011121314关系：满二叉树必为完全二叉树，而完全二叉树不一定是满二叉树。6.2二叉树(BinaryTree)6.2.2二叉树的性质两种特殊的二叉树：完全二叉树举例：12345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树6.2二叉树(BinaryTree)6.2.2二叉树的性质性质4：具有n个结点的完全二叉树的深度为└log2n┘+1证明：设完全二叉树的高度为深度为h，则有2h-1-1n≤2h-1⇒2h-1=n2h⇒取对数h–1=log2(n)h。6.2二叉树(BinaryTree)6.2.2二叉树的性质性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：（1）如i=1，则序号为i的结点是根结点，无双亲结点；如i1，则序号为i的结点的双亲结点序号为└i/2┘。（2）如2×in，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结点的左孩子结点的序号为2×i。（3）如2×i＋1n，则序号为i的结点无右孩子；如2×i＋1≤n，则序号为i的结点的右孩子结点的序号为2×i＋1。6.2二叉树(BinaryTree)6.2.3二叉树的存储结构1、顺序存储结构#defineMAXNODE100typedefelemtypeSqBiTree[MAXNODE]SqBiTreebt;ABCDEFGHIJKLABCDEFGHIJKL二叉树的顺序存储结构111098765432106.2二叉树(BinaryTree)6.2.3二叉树的存储结构1、顺序存储结构ACBEDFGABC∧DE∧∧∧F∧∧GABDCEFG(a)一般的二叉树(b)改造后的完全二叉树6.2二叉树(BinaryTree)6.2.3二叉树的存储结构1、顺序存储结构ABCDA^B^^^C^^^^^^^D单支树顺序存储结构仅适用于完全二叉树2n-16.2二叉树(BinaryTree)6.2.3二叉树的存储结构2、链式存储结构（1）二叉链表：二叉链表中每个结点包含三个域：数据域、左指针域、右指针域lchilddatarchildtypedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BiTNode,*BiTree;6.2二叉树(BinaryTree)6.2.3二叉树的存储结构2、链式存储结构（1）二叉链表：∧EA∧D∧C∧∧G∧∧F∧BBDFACEG二叉树的二叉链表表示6.2二叉树(BinaryTree)6.2.3二叉树的存储结构2、链式存储结构（2）三叉链表：三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域BDEADFABDFEC6.2二叉树(BinaryTree)6.2.3二叉树的存储结构2、链式存储结构示例6.2二叉树(BinaryTree)6.2.4二叉树的基本操作创建二叉树二叉树的遍历6.3遍历二叉树和线索二叉树6.3.1遍历二叉树（traversingbinarytree）一、遍历二叉树的定义：1、先序遍历（DLR）若二叉树为空，则空操作；否则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；AFGEDCB先序遍历序列：A,B,D,E,G,C,F6.3遍历二叉树和线索二叉树6.3.1遍历二叉树（traversingbinarytree）一、遍历二叉树的定义：2、中序遍历（LDR）若二叉树为空，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；AFGEDCB中序遍历序列：D,B,G,E,A,C,F6.3遍历二叉树和线索二叉树6.3.1遍历二叉树（traversingbinarytree）一、遍历二叉树的定义：3、后序遍历（LRD）若二叉树为空，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点；AFGEDCB后序遍历序列：D,G,E,B,F,C,A6.3遍历二叉树和线索二叉树6.3.1遍历二叉树例：先序遍历、中序遍历、后序遍历下图所示的表达式语法树后序遍历序列（后缀表达式）：abcd-*+ef/-中序遍历序列（中缀表达式）：a+b*c–d–e/f先序遍历序列（前缀表达式）：-+a*b–cd/ef6.3遍历二叉树和线索二叉树6.3.1遍历二叉树二、遍历二叉树的递归算法数据结构定义：typedefintElemTypetypedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BiTNode,*BiTree;6.3遍历二叉树和线索二叉树6.3.1遍历二叉树二、遍历二叉树的递归算法1、先序遍历PreOrderTranverse(BiTreeT){if(T){printf(“%d”,T-data);//访问的方式有多种PreOrderTranverse(T-LChild);PreOrderTranverse(T-RChild);}}6.3遍历二叉树和线索二叉树6.3.1遍历二叉树二、遍历二叉树的递归算法2、中序遍历InOrderTranverse(BiTreeT){if(T){InOrderTranverse(T-LChild);printf(“%d”,T-data);//访问的方式有多种InOrderTranverse(T-RChild);}}6.3遍历二叉树和线索二叉树6.3.1遍历二叉树二、遍历二叉树的递归算法3、后序遍历PostOrderTranverse(BiTreeT){if(T){PostOrderTranverse(T-LChild);PostOrderTranverse(T-RChild);printf(“%d”,T-data);//访问的方式有多种}}6.3遍历二叉树和线索二叉树6.3.1遍历二叉树三、遍历二叉树的非递归算法遍历的递归执行过程：⊕⊕⊕⊕⊕⊕*******△△△AGBCDE△△△F△6.3遍历二叉树和线索二叉树6.3.1遍历二叉树三、遍历二叉树的非递归算法（一）基于栈的递归消除1、中序遍历的非递归算法voidInOrder（BiTreeT）{InitStack(S);push(S,T);while(!StackEmpty(S)){if(Getop(S,p)&&p!=NULL)//向左走到尽头{push(S,p-lchild;}pop(S,p);//空指针退栈if(!StackEmpty(S)){//访问结点，向右一步pop(S,p);visit(p-data);p=p-rchild;}}}6.3遍历二叉树和线索二叉树voidInOrder（BiTreeT）{InitStack(S);p=T;while(p!=NULL||!StackEmpty(S)){if(p!=NULL)/*根指针进栈，遍历左子树*/{push(S,p);p=p-lchild;}else{/*根指针退栈，访问根结点，遍历右子树*/pop(S,p);visit(p-data);p=p-rchild;}