树与二叉树ppt课件.ppt

树（树（非线性数据结构非线性数据结构） 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现实世界中，能用树的结构表示的例子：现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关学校的行政关系、书的层次结构、人类的家族血缘关系等。系等。计算机软件技术中，能用树的结构表示的例子：计算机软件技术中，能用树的结构表示的例子：操作系统中的多级文件目录结构，高级语言中源程序操作系统中的多级文件目录结构，高级语言中源程序的语法结构等。的语法结构等。有关树的基本术语有关树的基本术语: :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棵互不相交的树的集合。棵互不相交的树的集合。 A C G T2 B E L KT1 FD H I T3J M C G T2 B E L KT1 FD H I T3J M 树的存储结构可以采用具有多个指针域的多重链表，结点中树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定指针域的个数应由树的度来决定 但在实际应用中，这种存储结构并不方便，一般将树转化为但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理二叉树表示，进行处理 可以用树来表示算术表达式。可以用树来表示算术表达式。Edatapoint1point2point3ABCDFGHIJroot(a)(b)是一种重要的树形结构，其结构定义为：二叉是一种重要的树形结构，其结构定义为：二叉树是树是n(n0)n(n0)个结点的有限集，它或为空树个结点的有限集，它或为空树(n=0)(n=0)，或由一，或由一个根结点和两棵分别称为根的左子树和右子树的、互不相个根结点和两棵分别称为根的左子树和右子树的、互不相交的二叉树组成。交的二叉树组成。(Binary Tree)(Binary Tree)二叉树一种特殊的树型结构，特点是树中每个结二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能点只有两棵子树，且子树有左右之分，次序不能颠倒。颠倒。因为树的每个结点的度不同，存储困难，使对树因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。的处理算法很复杂。所以引出二叉树的讨论。 空二叉树空二叉树 仅有仅有根结点根结点 右子右子树为空树为空 左子左子树为空树为空左右子树左右子树均非空均非空二叉树的结点的子树要区分左子树和右子树，即二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。左子树还是右子树。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性质性质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=1i=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倍，即倍，即2 22 2i-2i-2=2=2i-1i-1。深度为深度为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非完全二叉树非完全二叉树(2) (2) 链式存储结构链式存储结构T16若父结点在数组中若父结点在数组中i i下标处，其左孩子在下标处，其左孩子在2 2* *i i处，右孩子在处，右孩子在2 2* *i+1i+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一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。 每个结点由数据域、左指针域和右指针域组成。每个结点由数据域、左指针域和右指针域组成。rchildrchildDataDatalchildlchild A AD DB B C C E E F F 图 为 一 般 二 叉图 为 一 般 二 叉树 的 二 叉 链 表树 的 二 叉 链 表结构结构AECBDF链式存储结构的算法描述：链式存储结构的算法描述：Typedef struct BiTNode int data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree;rchildDatalchildrchildDatalchildrchildDatalchild1.1.树的结点个数至少为树的结点个数至少为1 1，而二叉树的结点个数可以为而二叉树的结点个数可以为0 0。2.2.树中结点的最大度数没有限制，二叉树结点最大度数为树中结点的最大度数没有限制，二叉树结点最大度数为2 2。3.3.树的结点子树无左、右之分，二叉树的结点子树有明确的左、树的结点子树无左、右之分，二叉树的结点子树有明确的左、 右之分。右之分。 二叉树二叉树树树 由于二叉树可以用二叉链表表示，为了使一般树也能由于二叉树可以用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉树之间的关系。用二叉链表表示，必须找出树与二叉树之间的关系。 这样，给定一棵树，可以找到唯一的一棵二叉树与之这样，给定一棵树，可以找到唯一的一棵二叉树与之对应。对应。（1 1）树转换为二叉树的方法：）树转换为二叉树的方法：（根结点的右子树必空）（根结点的右子树必空） 对每个孩子进行自左至右的排序；对每个孩子进行自左至右的排序； 在兄弟之间加一条连线；在兄弟之间加一条连线； 对每个结点，除了左孩子外，去除其与其余孩子之间的联系；对每个结点，除了左孩子外，去除其与其余孩子之间的联系； 以根结点为轴心，将整个树顺时针转以根结点为轴心，将整个树顺时针转4545度。度。 A B CD E G H FI(a)ABEFCDGHI(d) I A B C DE F G H(b)ABCDEFGHI(c)ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：方法：将各棵树分别转成二叉树；将各棵树分别转成二叉树；把每棵树的根结点用线连起来；把每棵树的根结点用线连起来；以第一棵树的根结点作为二叉树以第一棵树的根结点作为二叉树的根结点，按顺时针方向旋转。的根结点，按顺时针方向旋转。 查找某个结点，或对二叉树中全部结点进行某种处理，就查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。需要遍历。（1 1）遍历定义及遍历算法）遍历定义及遍历算法 遍历是指按某条搜索路线寻访树中每个结点，且每个结点遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。按先左后右的原则，一般使用三种遍序：只被访问一次。按先左后右的原则，一般使用三种遍序：先序遍历先序遍历(D L R):(D L R): 访问根结点，按先序遍历左子树，按先序遍历右子树。访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历中序遍历(L D R):(L D R): 按中序遍历左子树，访问根结点，按中序遍历右子树。按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历后序遍历(L R D):(L R D): 按后序遍历左子树，按后序遍历右子树，访问根结点。按后序遍历左子树，按后序遍历右子树，访问根结点。 二叉树为空时，执行空操作，即空二叉树已遍历完。二叉树为空时，执行空操作，即空二叉树已遍历完。先序遍历：先序遍历：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先序遍历二叉树的递归算法：先序遍历二叉树的递归算法： void PreOderTraverse(BiTreevoid PreOderTraverse(BiTree T) T) if(T if(T! =NULL)! =NULL) printf printf (T-data); (T-data); PreOrderTraverse(T-lchild PreOrderTraverse(T-lchild);); PreOrderTraverser(T-rchild PreOrderTraverser(T-rchild);); / /* *建立二叉链表，并进行二叉树的遍历建立二叉链表，并进行二叉树的遍历* */ /#include stdio.h#include stdio.h #include stdlib.h#include stdlib.h struct btnodestruct btnode int int d; d; struct btnode struct btnode * *lchildlchild; ; struct btnode struct btnode * *rchildrchild;intrav(struct btnode intrav(struct btnode * *btbt) ) if(bt if(bt!=NULL)!=NULL) pretrav(bt-lchild pretrav(bt-lchild);); printf(%dn,bt printf(%dn,bt-d);-d); pretrav(bt-rchild pretrav(bt-rchild);); return; return; main()main() struct btnode struct btnode * *btbt, ,* *h;h; bt bt=create(h,0);=create(h,0); pretrav(bt pretrav(bt);); struct btnode *create(bt,k)struct btnode *bt;int k; char b; struct btnode *p,*t; printf(input b:); scanf(%d,&b); if(b!=0) p=(struct btnode *)malloc(sizeof(struct btnode); 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); （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 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穿线二叉树1 1、穿线二叉树的含义、穿线二叉树的含义2 2、穿线二叉树的构造、穿线二叉树的构造3 3、穿线二叉树的遍历、穿线二叉树的遍历表达式的线性化1 1、有序树的二叉树表示、有序树的二叉树表示2 2、表达式的线性化、表达式的线性化