树与二叉树ppt课件

1.树树树树有关树的术语有关树的术语有关树的术语有关树的术语树的存储结构树的存储结构树的存储结构树的存储结构2.二叉树二叉树二叉树二叉树二叉树的性质二叉树的性质二叉树的性质二叉树的性质满二叉树与完全二叉树满二叉树与完全二叉树满二叉树与完全二叉树满二叉树与完全二叉树二叉树的存储结构二叉树的存储结构二叉树的存储结构二叉树的存储结构树与二叉树的关系树与二叉树的关系树与二叉树的关系树与二叉树的关系二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历穿线二叉树穿线二叉树穿线二叉树穿线二叉树表达式的线性化表达式的线性化表达式的线性化表达式的线性化树（树（非线性数据结构非线性数据结构）树树（非线性数据结构）树的形式化定义树的形式化定义树的形式化定义树的形式化定义：树树树树(Tree)(Tree)(Tree)(Tree)是由一个或多个结点组成的有限集是由一个或多个结点组成的有限集是由一个或多个结点组成的有限集是由一个或多个结点组成的有限集合合合合T T T T，其中有一个特定的称为根的结点；其余结，其中有一个特定的称为根的结点；其余结，其中有一个特定的称为根的结点；其余结，其中有一个特定的称为根的结点；其余结点可分为点可分为点可分为点可分为m(m0)m(m0)m(m0)m(m0)个互不相交的有限集个互不相交的有限集个互不相交的有限集个互不相交的有限集T1,T2,T3 T1,T2,T3 T1,T2,T3 T1,T2,T3,Tm,Tm,Tm,Tm，每一个集合本身又是一棵树，且称为根，每一个集合本身又是一棵树，且称为根，每一个集合本身又是一棵树，且称为根，每一个集合本身又是一棵树，且称为根的的的的子树。子树。子树。子树。树的特点：仅有一个根结点，结点间有明树的特点：仅有一个根结点，结点间有明树的特点：仅有一个根结点，结点间有明树的特点：仅有一个根结点，结点间有明显的层次结构关系。显的层次结构关系。显的层次结构关系。显的层次结构关系。树的形式化定义：树的特点：仅有一个根结点，结点间有明显的层次 A A C C G G T T2 2 B B E E L L K KT T1 1 F FD D H H I I T T3 3J J M M现实世界中，能用树的结构表示的例子：现实世界中，能用树的结构表示的例子：学学校校的的行行政政关关系系、书书的的层层次次结结构构、人人类类的的家家族族血血缘缘关关系等。系等。计算机软件技术中，能用树的结构表示的例子：计算机软件技术中，能用树的结构表示的例子：操操作作系系统统中中的的多多级级文文件件目目录录结结构构，高高级级语语言言中中源源程程序序的语法结构等。的语法结构等。ACGT2BELKT1FDHIT有关树的基本术语有关树的基本术语:1.1.结结点点（NodeNode）：树树中中的的元元素素，包包含含数数据据项项及及若若干干指指向向其其子树的分支。子树的分支。2.2.结点的度（结点的度（DegreeDegree）：结点拥有的子树数。：结点拥有的子树数。3.3.结点的层次：结点的层次：从根结点开始算起，根为第一层从根结点开始算起，根为第一层.4.4.叶子（叶子（LeafLeaf）：度为零的结点，也称端结点。：度为零的结点，也称端结点。5.5.孩子（孩子（ChildChild）：结点子树的根称为该结点的孩子结点。：结点子树的根称为该结点的孩子结点。6.6.双双亲亲（ParentParent）：孩孩子子结结点点的的上上层层结结点点，称称为为这这些些结结点点的双亲。的双亲。7.7.兄弟（兄弟（SiblingSibling）：同一双亲的孩子。同一双亲的孩子。8.8.深度（深度（DepthDepth)：树中结点的最大层次数。树中结点的最大层次数。9.9.森林（森林（ForestForest）：M M棵互不相交的树的集合。棵互不相交的树的集合。ACGT2BELKT1FDHIT3JMCGT2BELKT1FDHIT3JM有关树的基本术语:ACGT2BELKT1树的存储结构树的存储结构树的存储结构可以采用具有多个指针域的多重链表，结点中树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定指针域的个数应由树的度来决定但在实际应用中，这种存储结构并不方便，一般将树转化为但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理二叉树表示，进行处理可以用树来表示算术表达式。可以用树来表示算术表达式。树的存储结构树的存储结构可以采用具有多个指针域的多重链表，结二叉树二叉树二叉树二叉树是一种重要的树形结构，其结构定义为：二叉是一种重要的树形结构，其结构定义为：二叉树是树是n(n0)n(n0)个结点的有限集，它或为空树个结点的有限集，它或为空树(n=0)(n=0)，或由一，或由一个根结点和两棵分别称为根的左子树和右子树的、互不相个根结点和两棵分别称为根的左子树和右子树的、互不相交的二叉树组成。交的二叉树组成。二叉树二叉树(Binary Tree)(Binary Tree)的定义的定义二二叉叉树树一一种种特特殊殊的的树树型型结结构构，特特点点是是树树中中每每个个结结点点只只有有两两棵棵子子树树，且且子子树树有有左左右右之之分分，次次序序不不能能颠倒。颠倒。因因为为树树的的每每个个结结点点的的度度不不同同，存存储储困困难难，使使对对树树的处理算法很复杂。所以引出二叉树的讨论。的处理算法很复杂。所以引出二叉树的讨论。二叉树是一种重要的树形结构，其结构定义为：二叉树是n(n0二叉树的五种基本形态二叉树的五种基本形态 空二叉树空二叉树 仅有仅有根结点根结点 右子右子树为空树为空 左子左子树为空树为空左右子树左右子树均非空均非空要要要要点点点点：二二叉叉树树的的结结点点的的子子树树要要区区分分左左子子树树和和右右子子树树，即即使使在在结结点点只只有有一一棵棵子子树树的的情情况况下下也也要要明明确确指指出出该该子子树树是是左子树还是右子树。左子树还是右子树。二叉树的五种基本形态空二叉树仅有右子树为空左子1.1.二叉树的第二叉树的第i i层上至多有层上至多有2 2i-1i-1（i i 1 1）个结点。个结点。2.2.深度为深度为m m的二叉树中至多含有的二叉树中至多含有2 2m m-1-1个结点。个结点。3.3.若若在在任任意意一一棵棵二二叉叉树树中中，有有n n0 0个个叶叶子子结结点点，有有n n2 2个个度度为为2 2的结点，则的结点，则：n n0 0=n=n2 2+1+1A AB BC CD DE EF F二叉树的性质二叉树的性质二叉树的第i层上至多有2i-1（i1）个结点。ABCDEF性质性质1 1：二叉树的第二叉树的第i i层上至多有层上至多有2 2 i-1i-1（i i 1 1）个结点。个结点。证明：证明：根据二叉树的特点，结论是显然的。根据二叉树的特点，结论是显然的。性质性质2 2：深度为深度为m m的二叉树中至多含有的二叉树中至多含有2 2m m-1-1个结点。个结点。证证明明：深深度度为为m m的的二二叉叉树树最最多多有有m m层层，根根据据性性质质1 1，只只要要将将第第1 1层层到到第第m m层层的的最最大大结结点点数数相相加加，就就可可得得到到整整个个二二叉叉树树中中结结点点的的最最大值。大值。2 21-11-1+2+22-12-1+2+2m-1m-1=2=2m m-1-1 性质性质3 3：度为：度为0 0的结点总比度为的结点总比度为2 2的结点多一个。的结点多一个。设：有设：有n n0 0个叶子结点，有个叶子结点，有n n1 1个度为个度为1 1的结点，有的结点，有n n2 2个度为个度为2 2的结点，的结点，则二叉树中结点总数为则二叉树中结点总数为：n=nn=n0 0+n+n1 1+n+n2 2 设所有进入分支的总数为设所有进入分支的总数为m,m,则总的结点个数为：则总的结点个数为：n=m+1n=m+1总的射出分支与总的进入分支数相等：总的射出分支与总的进入分支数相等：m=nm=n1 1+2n+2n2 2 因此：因此：n n0 0+n+n1 1+n+n2 2=n=n1 1+2n+2n2 2+1 +1 所以：所以：n n0 0=n=n2 2+1+1 A AB BC CD DE EF F4 42 23 31 15 56 67 78 89 9101011111212131314141515A AB BC CD DE EF FA AB BC CD DE EF F4 42 23 31 15 56 67 78 89 9101011111212131314141515用归纳法证明：用归纳法证明：i=1 i=1，则结点数，则结点数=2=20 0=1=1为根结点。为根结点。若若已已知知 i-1i-1层层上上结结点点数数至至多多有有2 2(i-1)-1(i-1)-1=2=2i-2i-2 个个，由由于于二二叉叉树树每每个个结结点点度度数数最最大大为为2 2，因因此此第第i i层层上上结结点点数数最最多多为为第第i-1i-1层层上上结结点数的点数的2 2倍，即倍，即2222i-2i-2=2=2i-1i-1。性质1：二叉树的第i层上至多有2i-1（i1）个结点。满二叉树：满二叉树：满二叉树：满二叉树：深度为深度为k k且含有且含有2 2k k-1-1个结点的二叉树。个结点的二叉树。特特点点：每每一一层层上上的的结结点点数数都都是最大结点数。是最大结点数。完全二叉树完全二叉树完全二叉树完全二叉树:指指深深度度为为k k的的，有有n n个个结结点点的的，且且每每一一个个结结点点都都与与深深度度为为k k的的满满二二叉叉树树中中编编号号从从1 1至至n n的结点的结点一一对应一一对应。4 42 23 31 15 56 67 78 89 91010111112121313141415154 42 23 31 15 56 67 78 89 9101011111212完全二叉树完全二叉树4 42 23 31 15 56 67 78 89 9101011111212非完全二叉树非完全二叉树满二叉树：深度为k且含有2k-1个结点的二叉树。完全二叉树:二叉树的存储结构二叉树的存储结构 (2)(2)链式存储结构链式存储结构T16若父结点在数组中若父结点在数组中i i下标处，其左孩子在下标处，其左孩子在2*i2*i处，右孩子在处，右孩子在2*i+12*i+1处。处。1111 A A B BC C F F E E D D 1 1 2 2 4 8 8 9 91010 5 5 6 6 3 3 7 71212131314141515(1)(1)顺序存储结构顺序存储结构(1)(1)顺序存储结构顺序存储结构2 2h h-1=-1=2 24 4-1=15-1=15用用一一组组连连续续的的存存储储单单元元存存放放二二叉叉树树的的数数据据元元素素。结结点点在在数数组组中中的的相相对对位位置置蕴蕴含含着着结结点之间的关系。点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。二叉树的存储结构(2)链式存储结构T16若父结点(2)(2)(2)(2)链式存储结构：链式存储结构：链式存储结构：链式存储结构：每个结点由数据域、左指针域和右指针域组成。每个结点由数据域、左指针域和右指针域组成。rchildrchildDataDatalchildlchild A AD DB B C C E E F F 图图为为一一般般二二叉叉树树的二叉链表结构的二叉链表结构AECBDF(2)链式存储结构：rchildDatalchildAD链式存储结构的算法描述：链式存储结构的算法描述：TypedefstructBiTNodeintdata;structBiTNode*lchild,*rchild;BiTNode,*BiTree;rchildDatalchildrchildDatalchildrchildDatalchild链式存储结构的算法描述：rchildDatalchildrc树与二叉树的区别树与二叉树的区别1.1.树的结点个数至少为树的结点个数至少为1 1，而二叉树的结点个数可以为而二叉树的结点个数可以为0 0。2.2.树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限制，二叉树结点最大度数为2 2。3.3.树树 的的 结结 点点 子子 树树 无无 左左、右右 之之 分分，二二 叉叉 树树 的的 结结 点点 子子 树树 有有 明明 确确 的的 左左、右之分。右之分。二叉树二叉树树树树与二叉树的区别树的结点个数至少为1，而二叉树的结点个数可以树和森林转换为二叉树树和森林转换为二叉树 由于二叉树可以用二叉链表表示，为了使一般树也能由于二叉树可以用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉树之间的关系。用二叉链表表示，必须找出树与二叉树之间的关系。这样，给定一棵树，可以找到唯一的一棵二叉树与之这样，给定一棵树，可以找到唯一的一棵二叉树与之对应。对应。（1 1）树转换为二叉树的方法：）树转换为二叉树的方法：（根结点的右子树必空）（根结点的右子树必空）对每个孩子进行自左至右的排序；对每个孩子进行自左至右的排序；在兄弟之间加一条连线；在兄弟之间加一条连线；对每个结点，除了左孩子外，去除其与其余孩子之间的联系；对每个结点，除了左孩子外，去除其与其余孩子之间的联系；以根结点为轴心，将整个树顺时针转以根结点为轴心，将整个树顺时针转4545度。度。树和森林转换为二叉树 A B CD E G H FI(a)树转换为二叉树树转换为二叉树树转换为二叉树树转换为二叉树ABEFCDGHI(d)I A B C DE F G H(b)ABCDEFGHI(c)ABCDEGHFI(a)树转换为二叉树ABEF（2 2）森林转换为二叉树森林转换为二叉树森林转换为二叉树森林转换为二叉树ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：方法：将各棵树分别转成二叉树；将各棵树分别转成二叉树；把每棵树的根结点用线连起来；把每棵树的根结点用线连起来；以以第第一一棵棵树树的的根根结结点点作作为为二二叉叉树树的根结点，按顺时针方向旋转。的根结点，按顺时针方向旋转。（2）森林转换为二叉树ADCBEFHIGJEFAD二叉树的遍历二叉树的遍历 查查找找某某个个结结点点，或或对对二二叉叉树树中中全全部部结结点点进进行行某某种种处处理理，就就需要遍历。需要遍历。（1 1）遍历定义及遍历算法）遍历定义及遍历算法 遍遍历历是是指指按按某某条条搜搜索索路路线线寻寻访访树树中中每每个个结结点点，且且每每个个结结点点只被访问一次。按先左后右的原则，一般使用三种遍序：只被访问一次。按先左后右的原则，一般使用三种遍序：先序遍历先序遍历(D L R):(D L R):访问根结点，按先序遍历左子树，按先序遍历右子树。访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历中序遍历(L D R):(L D R):按中序遍历左子树，访问根结点，按中序遍历右子树。按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历后序遍历(L R D):(L R D):按后序遍历左子树，按后序遍历右子树，访问根结点。按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。二叉树为空时，执行空操作，即空二叉树已遍历完。二叉树的遍历（2 2）遍历算法遍历算法先序遍历：先序遍历：D L RD L R中序遍历：中序遍历：L D RL D R后序遍历：后序遍历：L R DL R DA AD DB BC CT T1 1T T2 2T T3 3D L RD L RA AD L RD L RD L RD L R B B D D C CD L RD L R以先序遍历以先序遍历D L RD L R为例演示遍历过程为例演示遍历过程 ABDCABDCBDACBDAC DBCA DBCA（2）遍历算法先序遍历：DLRADBCT1T2T3D先序遍历二叉树的递归算法：先序遍历二叉树的递归算法：void PreOderTraverse(BiTree T)void PreOderTraverse(BiTree T)if(T!=NULL)if(T!=NULL)printf(T-data);printf(T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-lchild);PreOrderTraverser(T-rchild);PreOrderTraverser(T-rchild);先序遍历二叉树的递归算法：中序遍历二叉树的递归算法：中序遍历二叉树的递归算法：中序遍历二叉树的递归算法：中序遍历二叉树的递归算法：void InOrderTraverse(BiTree T)void InOrderTraverse(BiTree T)void InOrderTraverse(BiTree T)void InOrderTraverse(BiTree T)if(T!=NULL)if(T!=NULL)if(T!=NULL)if(T!=NULL)InOrderTraverse(T-lchild);InOrderTraverse(T-lchild);InOrderTraverse(T-lchild);InOrderTraverse(T-lchild);printf(T-data);printf(T-data);printf(T-data);printf(T-data);InOrderTraverse(T-rchild);InOrderTraverse(T-rchild);InOrderTraverse(T-rchild);InOrderTraverse(T-rchild);后序遍历二叉树的递归算法：后序遍历二叉树的递归算法：后序遍历二叉树的递归算法：后序遍历二叉树的递归算法：void PostOrderTraverse(BiTree T)void PostOrderTraverse(BiTree T)void PostOrderTraverse(BiTree T)void PostOrderTraverse(BiTree T)if(T!=NULL)if(T!=NULL)if(T!=NULL)if(T!=NULL)PostOrderTraverse(T-lchild);PostOrderTraverse(T-lchild);PostOrderTraverse(T-lchild);PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);PostOrderTraverse(T-rchild);PostOrderTraverse(T-rchild);PostOrderTraverse(T-rchild);printf(T-data);printf(T-data);printf(T-data);printf(T-data);中序遍历二叉树的递归算法：后序遍历二叉树的递归算法：/*/*建立二叉链表，并进行二叉树的遍历建立二叉链表，并进行二叉树的遍历*/*/#include stdio.h#include stdio.h#include stdlib.h#include stdlib.hstruct btnodestruct btnode int d;int d;struct btnode*lchild;struct btnode*lchild;struct btnode*rchild;struct btnode*rchild;intrav(struct btnode*bt)intrav(struct btnode*bt)if(bt!=NULL)if(bt!=NULL)pretrav(bt-lchild);pretrav(bt-lchild);printf(%dn,bt-d);printf(%dn,bt-d);pretrav(bt-rchild);pretrav(bt-rchild);return;return;main()main()struct btnode*bt,*h;struct btnode*bt,*h;bt=create(h,0);bt=create(h,0);pretrav(bt);pretrav(bt);structbtnode*create(bt,k)structbtnode*bt;intk;charb;structbtnode*p,*t;printf(inputb:);scanf(%d,&b);if(b!=0)p=(structbtnode*)malloc(sizeof(structbtnode);p-d=b;p-lchild=NULL;p-rchild=NULL;if(k=0)t=p;if(k=1)bt-lchild=p;if(k=2)bt-rchild=p;create(p,1);create(p,2);return(t);/*建立二叉链表，并进行二叉树的遍历*/structbtn （2 2）遍历算法遍历算法中序遍历：中序遍历：L D RL D RA AD DB BC CT T1 1T T2 2T T3 3L D RL D RA A L D R L D RL D RL D R B B D D C CL D RL D R以中序遍历以中序遍历L D RL D R为例演示遍历过程为例演示遍历过程 BDACBDAC（2）遍历算法中序遍历：LDRADBCT1T2T3L （2 2）遍历算法遍历算法后序遍历：后序遍历：L R DL R DA AD DB BC CT T1 1T T2 2T T3 3L R DL R DA A L R D L R DL R DL R D B B D D C CL R DL R D以后序遍历以后序遍历L R DL R D为例演示遍历过程为例演示遍历过程 DBCADBCA（2）遍历算法后序遍历：LRDADBCT1T2T3L穿线二叉树1 1、穿线二叉树的含义、穿线二叉树的含义2 2、穿线二叉树的构造、穿线二叉树的构造3 3、穿线二叉树的遍历、穿线二叉树的遍历穿线二叉树1、穿线二叉树的含义表达式的线性化1 1、有序树的二叉树表示、有序树的二叉树表示2 2、表达式的线性化、表达式的线性化表达式的线性化1、有序树的二叉树表示