树与二叉树

1.树①有关树的术语②树的存储结构2.二叉树①二叉树的性质②满二叉树与完全二叉树③二叉树的存储结构④树与二叉树的关系⑤二叉树的遍历⑥穿线二叉树⑦表达式的线性化树（非线性数据结构）树的形式化定义：树(Tree)是由一个或多个结点组成的有限集合T，其中有一个特定的称为根的结点；其余结点可分为m(m≥0)个互不相交的有限集T1,T2,T3,…,Tm，每一个集合本身又是一棵树，且称为根的子树。树的特点：仅有一个根结点，结点间有明显的层次结构关系。ACGT2BELKT1FDHIT3JM现实世界中，能用树的结构表示的例子：学校的行政关系、书的层次结构、人类的家族血缘关系等。计算机软件技术中，能用树的结构表示的例子：操作系统中的多级文件目录结构，高级语言中源程序的语法结构等。有关树的基本术语:1.结点（Node）：树中的元素，包含数据项及若干指向其子树的分支。2.结点的度（Degree）：结点拥有的子树数。3.结点的层次：从根结点开始算起，根为第一层.4.叶子（Leaf）：度为零的结点，也称端结点。5.孩子（Child）：结点子树的根称为该结点的孩子结点。6.双亲（Parent）：孩子结点的上层结点，称为这些结点的双亲。7.兄弟（Sibling）：同一双亲的孩子。8.深度（Depth)：树中结点的最大层次数。9.森林（Forest）：M棵互不相交的树的集合。ACGT2BELKT1FDHIT3JMCGT2BELKT1FDHIT3JM树的存储结构树的存储结构可以采用具有多个指针域的多重链表，结点中指针域的个数应由树的度来决定但在实际应用中，这种存储结构并不方便，一般将树转化为二叉树表示，进行处理可以用树来表示算术表达式。Edatapoint1point2point3ABCDFGHIJroot(a)(b)二叉树是一种重要的树形结构，其结构定义为：二叉树是n(n≥0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为根的左子树和右子树的、互不相交的二叉树组成。二叉树(BinaryTree)的定义二叉树一种特殊的树型结构，特点是树中每个结点只有两棵子树，且子树有左右之分，次序不能颠倒。因为树的每个结点的度不同，存储困难，使对树的处理算法很复杂。所以引出二叉树的讨论。二叉树的五种基本形态空二叉树仅有根结点右子树为空左子树为空左右子树均非空要点：二叉树的结点的子树要区分左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。1.二叉树的第i层上至多有2i-1（i1）个结点。2.深度为m的二叉树中至多含有2m-1个结点。3.若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=n2+1ABCDEF二叉树的性质性质1：二叉树的第i层上至多有2i-1（i1）个结点。证明：根据二叉树的特点，结论是显然的。性质2：深度为m的二叉树中至多含有2m-1个结点。证明：深度为m的二叉树最多有m层，根据性质1，只要将第1层到第m层的最大结点数相加，就可得到整个二叉树中结点的最大值。21-1+22-1+…+2m-1=2m-1性质3：度为0的结点总比度为2的结点多一个。设：有n0个叶子结点，有n1个度为1的结点，有n2个度为2的结点，则二叉树中结点总数为：n=n0+n1+n2设所有进入分支的总数为m,则总的结点个数为：n=m+1总的射出分支与总的进入分支数相等：m=n1+2n2因此：n0+n1+n2=n1+2n2+1所以：n0=n2+1ABCDEF423156789101112131415ABCDEFABCDEF423156789101112131415用归纳法证明：i=1，则结点数=20=1为根结点。若已知i-1层上结点数至多有2(i-1)-1=2i-2个，由于二叉树每个结点度数最大为2，因此第i层上结点数最多为第i-1层上结点数的2倍，即2×2i-2=2i-1。满二叉树：深度为k且含有2k-1个结点的二叉树。特点：每一层上的结点数都是最大结点数。完全二叉树:指深度为k的，有n个结点的，且每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。423156789101112131415423156789101112完全二叉树423156789101112非完全二叉树二叉树的存储结构(2)链式存储结构T[16]若父结点在数组中i下标处，其左孩子在2*i处，右孩子在2*i+1处。11ABCFED●●●●●●●●●1248910563712131415(1)顺序存储结构(1)顺序存储结构2h-1=24-1=15用一组连续的存储单元存放二叉树的数据元素。结点在数组中的相对位置蕴含着结点之间的关系。0000FE000DC0BA15141312111098765432100一般二叉树必须按完全二叉树的形式存储，将造成存储的浪费。(2)链式存储结构：每个结点由数据域、左指针域和右指针域组成。rchildDatalchild^ADB^C^^E^^F^图为一般二叉树的二叉链表结构AECBDF链式存储结构的算法描述：TypedefstructBiTNode{intdata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;rchildDatalchildrchildDatalchildrchildDatalchild树与二叉树的区别1.树的结点个数至少为1，而二叉树的结点个数可以为0。2.树中结点的最大度数没有限制，二叉树结点最大度数为2。3.树的结点子树无左、右之分，二叉树的结点子树有明确的左、右之分。二叉树树树和森林转换为二叉树由于二叉树可以用二叉链表表示，为了使一般树也能用二叉链表表示，必须找出树与二叉树之间的关系。这样，给定一棵树，可以找到唯一的一棵二叉树与之对应。（1）树转换为二叉树的方法：（根结点的右子树必空）对每个孩子进行自左至右的排序；在兄弟之间加一条连线；对每个结点，除了左孩子外，去除其与其余孩子之间的联系；以根结点为轴心，将整个树顺时针转45度。ABCDEGHFI(a)树转换为二叉树ABEFCDGHI(d)IABCDEFGH(b)ABCDEFGHI(c)（2）森林转换为二叉树ADCBEFHIGJEFADCBHIGJADCBEFHIGJADCBEFHIGJ方法：•将各棵树分别转成二叉树；•把每棵树的根结点用线连起来；•以第一棵树的根结点作为二叉树的根结点，按顺时针方向旋转。二叉树的遍历查找某个结点，或对二叉树中全部结点进行某种处理，就需要遍历。（1）遍历定义及遍历算法遍历是指按某条搜索路线寻访树中每个结点，且每个结点只被访问一次。按先左后右的原则，一般使用三种遍序：先序遍历(DLR):访问根结点，按先序遍历左子树，按先序遍历右子树。中序遍历(LDR):按中序遍历左子树，访问根结点，按中序遍历右子树。后序遍历(LRD):按后序遍历左子树，按后序遍历右子树，访问根结点。二叉树为空时，执行空操作，即空二叉树已遍历完。（2）遍历算法先序遍历：DLR中序遍历：LDR后序遍历：LRDADBCT1T2T3DLRADLRDLRBDCDLR以先序遍历DLR为例演示遍历过程ABDCBDACDBCA先序遍历二叉树的递归算法：voidPreOderTraverse(BiTreeT){if(T!=NULL){printf(T-data);PreOrderTraverse(T-lchild);PreOrderTraverser(T-rchild);}}中序遍历二叉树的递归算法：voidInOrderTraverse(BiTreeT){if(T!=NULL){InOrderTraverse(T-lchild);printf(T-data);InOrderTraverse(T-rchild);}}后序遍历二叉树的递归算法：voidPostOrderTraverse(BiTreeT){if(T!=NULL){PostOrderTraverse(T-lchild);PostOrderTraverse(T-rchild);printf(T-data);}}/*建立二叉链表，并进行二叉树的遍历*/#includestdio.h#includestdlib.hstructbtnode{intd;structbtnode*lchild;structbtnode*rchild;};intrav(structbtnode*bt){if(bt!=NULL){pretrav(bt-lchild);printf(%d\n,bt-d);pretrav(bt-rchild);}return;}main(){structbtnode*bt,*h;bt=create(h,0);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);}（2）遍历算法中序遍历：LDRADBCT1T2T3LDRALDRLDRBDCLDR以中序遍历LDR为例演示遍历过程BDAC（2）遍历算法后序遍历：LRDADBCT1T2T3LRDALRDLRDBDCLRD以后序遍历LRD为例演示遍历过程DBCA穿线二叉树1、穿线二叉树的含义2、穿线二叉树的构造3、穿线二叉树的遍历表达式的线性化1、有序树的二叉树表示2、表达式的线性化