计算机软件基础：14第四章数据结构二叉树

1、计算机软件基础多媒体教程第十四讲第四章 数据结构4. 树4.5 二叉树 二叉树的定义在一棵二次树中，若规定后件是有序的，即对于任何一个结点，规定它的第一后件称为左子(左后件，左件)，第二后件称为右子(右后件，右件)，那么这是一棵二次有序树，并被称为二叉树(Binary Tree)。二叉树的结点可以既有左子又有右子，也可以只有左子，或者只有右子，甚至没有后件。用图形表示时，左子画在左下方，右子画在右下方。 二叉树的括号表示 定义根(左子树, 右子树) 或 根(左子树, ) 或 根(, 右子树) 或 根 例如，图示二叉树的括号表示：A为根的二叉树:A(B(, D(G, H), C(E(, F),)

2、A的后件:A(B, C)B的后件:B(, D)C的后件:C(E, )D的后件:D(G, H)E的后件:E(, F) Backus描述形式之一<二叉树> :=<根> |<根> <子树><子树> :=( <左子树> , <右子树> ) |( <左子树> , ) |( , <右子树> )<左子树> :=<左子> |<左子> <子树><右子树> :=<右子> |<右子> <子树> Backus描述形式

3、之二<二叉树> :=<根> |<根> ( <子树> )<子树> :=<左子树> , <右子树> |<左子树> , |, <右子树><左子树> :=<左子> |<左子> ( <子树> )<右子树> :=<右子> |<右子> ( <子树> )4.5.1 二叉树的存储形式 标准形式设置两个指针场分量(pLeftk 和prightk)，分别指向左子和右子。akdkpLeftkprightk10A206

4、020B3030D405040G50H60C7070E100100F 逆形式设置一个指针场分量pprek，指向父结点。 扩充的标准形式将标准形式和逆形式结合在一起，即pprek指向父结点，pLeftk和prightk分别指向左子和右子。akdkpprekpLeftkprightk10A206020B103030D20405040G3050H3060C107070E60100100F70 链接存储二叉树的扩充标准形式#define BINODE struct binodeBINODE char *s;BINODE *father, *Left,*right;BINODE *Root;每个BINO

5、DE结构存放一个结点，根结点由Root指向，father，Left和right分别指向父结点和左右子。 用数组存储二叉树的扩充标准形式#define BINODE struct binodeBINODE char *s;short father, Left, right;BINODE Tree100;short Root;每个数组元素Treei(i=0,.,n-1)存放一个结点。用数组下标表示结点地址，用-1表示空地址。定义变量Root指向根结点。结点成员father，Left和right分别指向父结点和左右子。4.5.2 二叉树的遍历 前序遍历先访问根按前序遍历左子树按前序遍历右子树图示树的

6、前序遍历结果：A B D G H C E F 后序遍历按后序遍历左子树按后序遍历右子树最后访问根图示树的后序遍历结果：G H D B F E C A 中序遍历按中序遍历左子树访问根按中序遍历右子树图示树的中序遍历结果：B G D H A E F C 中序遍历与投影特性投影步骤:1) 将所有左子树中的结点都画在结点的左下方2) 将所有右子树中的结点都画在结点的右下方3) 然后垂直投影将得到二叉树的中序遍历:B G D H A E F C【例4-5.1】二叉树标准形式的数组编程 编程要求用数组存储树的标准形式，用递归函数实现二叉树的中序遍历(网络课堂：exe4-5.1BiTree.c) 程序中的数

7、据定义#define BINODE struct binodeBINODEchar s10;short left, right;BINODE T100;short n;每个数组元素Ti (i=0,.,n-1)存放一个结点。用数组下标表示结点地址，用-1表示空地址。定义变量root指向根结点。结点成员left和right分别指向左右子。iTi.sleftright0A211B4-12C-133D674E-155F-1-16G-1-17H-1-1 函数实现void CreateBitree(short *n, short *root)int i;scanf("%d%d", n,

8、 root);for(i=0; i<*n; i+)scanf("%s%d%d", Ti.s, &Ti.Left, &Ti.right);main()输入数据为： 8 0A 2 1B 4 -1C -1 3D 6 7E -1 5F -1 -1G -1 -1H -1 -1short root;CreateBitree(&n, &root); /* 输入并生成二叉树*/symOrder(root); /* 中序遍历函数*/ 中序遍历函数及运行过程示例symOrder(short node) if(node = -1)return;symOrde

9、r(Tnode.Left);printf(“%sn”, Tnode.s);symOrder(Tnode.right);【例4-5.2】二叉树标准形式的链接编程 编程要求输入用括号表示的二叉树，例如：A(C(, D(G, H), B(E(, F), )用链接的结构存储树的标准形式用递归函数实现二叉树的后序遍历(网络课堂：exe4-5.2BiTree.c) 程序实现#define BINODE struct binodeBINODEchar *key;BINODE *Left,*right;BINODE *Root;void postOrder(BINODE *node)if (!node) re

10、turn;postOrder(node->Left);postOrder(node->right);printf(“node=%sn”,node->key);void CreateBitree(void)见：exe5-5.2BiTree.cmain()CreateBitree();/* 输入并生成二叉树*/postOrder(Root); /* 后序遍历*/4.5.3 二叉树的顺序存储 二叉树的顺序存储根据树的定义，每个结点的后件不止一个。严格地说，不能采取顺序存储的方式来存储树，或者说不能用直接用数组实现树的存储，因为无法满足ak=ak+s (k是k的前件)，而只能用链接方

11、式进行存储。但是如果采用某种约定，例如根据某种遍历方式，可以实现树的顺序存储。因为遍历是一种线性的关系，当结点k是结点k关于某种遍历的前件时，可以满足ak=ak+s。在二叉树的存储中，往往采用这种修正的顺序存储方式。例如，按照前序遍历实现二叉树的顺序存储，可以满足前序遍历的前后件关系，但是二叉树中每个结点还有另外一个结点，必须采取一定的约定，或者说需要附加某种存储关系。 采用flag约定的前序遍历顺序存储 约定顺序存储的定义修正树的存储单元定义，例如，将k=ak, dk, pk扩充为k=ak, dk, pk, flag，即增加一个flag标志，以说明结点另外一个后件(非遍历后件)的存储信息。由

12、于二叉树中结点的后件最多是两个，因此可以用pk和flag来存储结点的后件。假定采用以下的flag约定的存储定义：规定结点k的右子kR地址用指针场pk表示。而左子kL的地址信息用flag说明，如果结点有左子kL，则必定是前序遍历的后件。因此若flag为1，表示结点k有左子kL，即akL=ak+s，否则表示结点k没有左子kL。 flag约定的存储单元示例根据约定，pk和flag的取值有四种情况，分别是：(1)结点k有左件kL，有右件kR则flag=1，pk=akR，akL=ak+s，如结点A和D。(2)结点k无左件kL，有右件kR则flag=0，pk = akR，如结点B和E。(3)结点k有左件k

13、L，无右件kR则flag=1，pk=-1，akL=ak+s，如结点C。(4)结点k无左件kL，无右件kR则flag=0， pk=-1，如结点G，H和F。 flag约定的顺序存储示例数据定义#define M 100#define BITREE struct bitreeBITREEchar *s;short p, flag;BITREE treeM;short n; 前序遍历函数void preOrder(BITREE *tree)int i;for(i=0; i<n ; i+)printf(“node=%sn”, treei.s); 打印左件的程序(取决于flag)根据结点k的地址j，

14、打印其左件。if(treej.flag = 0)printf(“no Left chiLdn”);eLseprintf(“Left chiLd is %sn”, treej+1.s); 打印右件的程序(取决于pk)根据结点k的地址j，打印其右件。if(treej.p = -1)printf(“no right chiLdn”);eLse printf(“right chiLd is %sn”, treetreej.p.s); 打印前序前件的程序(数组前一元素)根据结点k的地址j，打印其前序前件。if(j=0)printf(“no predecessorn”);eLse printf(“pred

15、ecessor is %sn”, treej-1.s); 采用一个指针场的前序遍历顺序存储 数据定义设存储单元为k=ak, dk, pk，存放结点的数组定义为#define M 100#define ABS(x) (x>0) ? (x) : (-x)#define BITREE struct bitreeBITREEchar *s;short p;BITREE treeM;short n;/* 结点数n<=M*/ pk的定义(1) 结点k有左件kL，有右件kR，则pk=akR(2) 结点k无左件kL，有右件kR，则pk=-akR(3) 结点k有左件kL，无右件kR，则pk=M(4)

16、 结点k无左件kL，无右件kR，则pk=-M 确定结点k的左件和右件地址的法则若pk>0，则结点k有左件，且akL=ak+s。若pk<0，则结点k无左件。若|pk|!=M，则结点k有右件，且akR = |pk|。若|pk|=M，则结点k无右件。 前序遍历函数void preOrder(BITREE *tree)int i;for(i=0; i<n ; i+)printf(“node=%sn”, treei.s); 打印左件的程序(判pk>0)根据结点k的地址j，打印其左件。if(treej.p < 0)printf(“no Left chiLdn”);eLsepr

17、intf(“Left chiLd is %sn”, treej+1.s); 打印右件的程序(判绝对值|pk|)根据结点k的地址j，打印其右件。if (ABS(treej.p) = M)printf(“no right chiLd n”);eLse printf(“right chiLd is %sn”, treeABS(treej.p).s); 打印前序前件的程序(数组前一元素)根据结点k的地址j，打印其前序前件。if(j=0)printf(“no predecessor n”);eLse printf(“predecessor is %sn”, treej-1.s);4.5.4 穿线树 穿线

18、树考察采用标准形式存储二叉树的情况。若有n个结点，共2n个指针场分量。因为根结点没有前件，其他每个结点只有一个父结点，因而共有n-1个指针场分量被利用，而n+1个被空置(浪费)。为了提高指针的利用率，我们引入穿线树的概念。 利用空闲指针场形成穿线树的方法对空闲的左子指针，用于指向其中序前件。对空闲的右子指针，用于指向其中序后件。这样被利用的指针有n-1个，则最后只有两个指针指向空，而不能再少。其中一个为中序始结点，另一个为中序终结点。用虚线表示穿线树的前后件关系，以便与二叉树的前后件关系有所区别。 穿线树的存储单元定义#define M 100#define ABS(x) (x>0) ?

19、 (x) : (-x) #define TH struct threadTHshort num, pL, pR;TH thM;short n; /* 结点数*/按标准形式用结构数组存放穿线树。其中， 用th1thn存放n个结点，用th0.num存放根结点的地址，本例中th0.num=1。用0表示空地址。穿线指针场的值(中序前件或者中序后件的地址)用负数表示。对中序始结点tb(如结点B)，必定有thtb.pL=0。对中序终结点te (如结点C)，必定有thte.pR=0。akdkpLpR110262200334045460-2-3580-3-163070750-18870-7-6 穿线树的处理函

20、数 根据结点k的地址i，求其中序前件k short getPre(TH *th, short i)if(i<1 | i>n) /* 非法地址 */error();if(i=thi.pL) > 0) /* 有左子 */whiLe(thi.pR > 0) /* 有右子 */i = thi.pR;return(ABS(i); 例如已知i=4，求结点60的中序前件k：th4.pL(=-2) < 0，无左子，得ak=|-2|=2，则dk = 20(th2.num)。akdkpLpR110262200334045460-2-3580-3-163070750-18870-7-6

21、函数调用为：if(k= getPre(th, i=4)printf(“prev node of %d is %dn”, thi.num, thk.num);elseprintf(“no prev node for %d.n”, thi.num); 例如已知i=1，求结点10的中序前件k：th1.pL(=2) > 0，有左子，令i=2；th2.pR(=3) > 0，有右子，令i=3；th3.pR(=5) > 0，有右子，令i=5；th5.pR(=-1) < 0，无右子，得ak=5，则dk = 80(th5.num)。akdkpLpR110262200334045460-2

22、-3580-3-163070750-18870-7-6函数调用为：if(k= getPre(th, i=1)printf(“prev node of %d is %dn”, thi.num, thk.num);eLseprintf(“no prev node for %d.n”, thi.num); 根据结点k的地址i，求其中序后件kshort getSuc(TH *th, short i) if(i<1 | i>n) /* 非法地址*/error();if (i=thi.pR)>0)/* 有右子*/whiLe(thi.pL>0) /* 有左子*/i = thi.pL;

23、return(ABS(i); 例如已知i=8，求结点70的中序后件k：th8.pR(=-6) < 0，无右子，得ak = |-6| = 6，则dk = 30(th6.num)。函数调用为：if(k= getSuc(th, i=8)printf(“suc node of %d is %dn“, thi.num, thk.num);eLseprintf(“no suc node for %d.n“, thi.num);akdkpLpR110262200334045460-2-3580-3-163070750-18870-7-6 例如已知i=1，求结点10的中序后件k：th1.pR(=6) &

24、gt; 0，有右子，令i=6；th6.pL(=7) > 0，有左子，令i=7；th7.pL(=-1) < 0，无左子，得ak=7，则dk = 50 (th7.num)。函数调用为：k= getSuc(th, i=1);akdkpLpR110262200334045460-2-3580-3-163070750-18870-7-6 求中序的始结点指针akfirstshort getFirst( TH * th)short i;if(i=th0.num) = 0)/* 空树*/return(i);whiLe(thi.pL != 0 )/* 有左子*/i = ABS(thi.pL);ret

25、urn(i); 例如，总是从i=th0.num=1开始，th1.pL(=2) != 0，有左子，令i=2，th2.pL = 0，无左子，得ak=2，则dk = 20 (th2.num)。函数调用为：akdkpLpR110262200334045460-2-3580-3-163070750-18870-7-6if(k= getFirst(th)printf(“first node for thread tree is %d.n”, thk.num);eLseprintf(“no node in the tree.n“); 中序遍历void symOrder(TH * th)short p;if(

26、p=getFirst(th) = 0) /* 求树根*/error();/* 空树*/doprintf(“node=%dn”, thp.num);while(p = getSuc(th, p); /* 求中序后件 */函数调用为：akdkpLpR110262200334045460-2-3580-3-163070750-18870-7-6symOrder(th);4.6 二叉树的线性表示及生成4.6.1 二叉树的层号表示 二叉树的层号及层号表示 图示二叉树的层号层号=1：A层号=2：B, G层号=3：E, F, K层号=4：H, J, L 前序遍历的层次表示1A, 2B, 3E, 4H, 3F

27、, 2G, 3K, 4J, 4L 后序遍历的层次表示4H, 3E, 3F, 2B, 4J, 4L, 3K, 2G, 1A 中序遍历的层次表示3E, 4H, 2B, 3F, 1A, 4J, 3K, 4L, 2G 二叉树层号表示的唯一性问题 前序遍历的层号表示一个结点的前序遍历后件可为左子(如G)，也可为右子(如E)。所以，前序遍历的层号表示不能唯一地确定一棵二叉树。 后序遍历的层号表示一个结点的后序遍历前件可为左子(如G)，也可为右子(如E)。所以，后序遍历的层号表示也不能唯一地确定一棵二叉树。 中序遍历的层次表示一个结点如果有左子，左子在中序遍历中的位置一定在该结点前方；一个结点如果有右子，右

28、子在中序遍历中的位置一定在该结点后方。所以，中序遍历的层次表示可以唯一地确定一棵二叉树。4.6.2 括号表示和二叉树的生成 二叉树的括号表示如果二叉树T只有一个结点，此结点就是它的括号表示。如果二叉树由根结点R和左子树TL和右子树TR组成，则树T的括号表示就是：R(TL的括号表示, TR的括号表示)。由于二叉树的左子树TL和右子树TR可能只出现任意一支，所以二叉树的括号表示可以是：R(TL的括号表示, ) 或者 R(, TR的括号表示) 或者R(TL的括号表示, TR的括号表示) 或者 R图示树的二叉树的括号表示A(B(E(, H), F), C(, K(L, )根据二叉树的括号表示，可以唯一

29、地确定一棵二叉树。二叉树的括号表示和层号表示可以相互转换。【例4-6.2】二叉树的生成算法(exe4-6.2BiTree.c) 根据输入的括号表示字符序列，生成并存储二叉树采用结构数组存储二叉树的结点，结点值为字母。例如输入的括号表示字符序列为： A(B(D, E), C(F(, G), ) 二叉树的生成算法及程序实现 程序中的数据定义#define M 1000#define EMPTY-1#define NODE struct nodeNODEchar key; /* 结点字符*/short Left, right;/* 左右子地址 */; NODE TreeM;/* 二叉树 */shor

30、t Root;/* 根地址 */short N=EMPTY; /* 结点数目*/char StringM; /* 输入字符串 */short Ptr=EMPTY; /* 字符数组指针*/akdkLeftright0A141B232D-1-13E-1-14C5-15F-176G-1-2 算法思路初始化：输入二叉树的括号表示，存入字符串数组String。生成二叉树的根；然后调用生成二叉树子树的函数，按“(左子树, 右子树)”的格式，递归生成子树。 递归生成子树的算法描述1. 取左括号(如果省略，表示空子树)2. 取左子(可以省略)2.1. 生成并存储左子2.2. 连接左子2.3. 递归生成左子树3

31、. 取逗号(不可省略)4. 取右子(可以省略)4.1. 生成并存储右子4.2. 连接右子4.3. 递归生成右子树5. 取右括号(不可省略) 函数设计 GetData()获取结点值从String中取一个结点字符，成功时返回1, 否则返回0。 GetSymboL()获取有效符号从String中取一个符号：“(”左括号，“)”右括号，或者 “,”逗号成功时返回1, 否则返回0 CreateNode()生成并存储结点生成结点，令左子和右子指向空，将结点存入数组Tree中。 CreateSubTree() 生成子树按“(左子树, 右子树)”的格式，调用GetData()和GetSymboL()获取结点值

32、和有效符号。若左子树或右子树非空，递归调用CreateSubTree()生成子树。 CreateBiTree()生成二叉树生成根结点，调用CreateSubTree()生成子树。 main()1. 输入括号表示的字符串2. 调用CreateBiTree生成二叉树3. 输出存储的二叉树 函数实现 GetData()获取结点值从String中取一个字母，成功时返回1, 否则返回0。short GetData(char *key) if(SringPtr+1 = 0)return(0);/* 无字符*/ * 从String中取一个字符 */*key = Sring+Ptr;if(isaLpha(*k

33、ey)/* 判字母 */return(1);Ptr-; /* 非字母，回退*/return(0); GetSymboL()获取有效符号从String中取一个指定的符号：“(”，“)”，或者 “,”，成功时返回1, 否则返回0short GetSymboL(char symboL) if(SringPtr+1 = 0)return(0); /* 无字符*/*从String中取一个符号 */if(Sring+Ptr = symboL)return(1);Ptr-; /* 非符号，回退*/return(0); CreateNode()生成并存储结点生成结点，令左子和右子指向空，将结点存入数组Tree

34、中。short CreateNode(char key) Tree+N.key = key;/* 存储结点值 */TreeN.Left = EMPTY;/* 左子树置空 */TreeN.right = EMPTY; /* 右子树置空 */return(N); /* 返回结点地址*/akdkLeftright0A141B232D-1-13E-1-1 CreateSubTree() 生成子树按“(左子树, 右子树)”的格式，调用GetData()和GetSymboL()获取结点值和有效符号，并递归调用CreateSubTree()生成子树。void CreateSubTree(short root

35、)short key, Left, right;/* 1. 取左括号(可以省略) */if(GetSymboL() = 0)return; /* 2. 取左子(可以省略) */if(GetData(&key) != 0) /* 2.1. 生成并存储左子 */Left = CreateNode(key); /* 2.2. 连接左子 */Treeroot.Left = Left; /* 2.3. 生成左子树 */CreateSubTree(Left); /* 3. 取逗号(不可省略)*/if(!GetSymboL(,)error(); /* 4. 取右子(可以省略)*/if(GetData

36、(&key)/* 4.1. 生成并存储右子*/right = CreateNode(key);/* 4.2. 连接右子*/Treeroot.right = right;/* 4.3. 生成右子树*/CreateSubTree(right);/* 5. 取右括号(不可省略)*/if(!GetSymboL()error (); CreateBiTree()生成二叉树先生成根结点，再调用CreateSubTree()生成子树。void CreateBiTree(void)char key;if(GetData(&key)/* 获取根结点值*/Root = CreateNode(key

37、);/* 生成根结点*/CreateSubTree(Root); /* 生成子树 */ main函数#define M 1000#define EMPTY-1#define NODE struct nodeNODEchar key; /* 结点字符*/short Left, right;/* 左右子地址*/; NODE TreeM; /* 二叉树*/ short Root;/* 根地址*/ short N=EMPTY; /* 结点数目*/ char StringM; /* 输入字符串*/ short Ptr=EMPTY;/* 字符数组指针*/main()short i=-1, c; /* 1.

38、 输入括号表示的字符串 */whiLe( (c=getchar() != EOF )if(!isspace(c) /* 滤去空字符*/String+i = c; String+i = 0;/* 2. 生成并存储二叉树 */CreateBiTree();/* 3. 输出存储的二叉树*/for(i=0; i<N; i+) printf(“node=%c, Left=%d, right=%dn”, Treei.key, Treei.Left, Treei.right);4.6.3 二叉树的确定如果已知二叉树的前序和中序的遍历，可以唯一地确定二叉树。如果已知二叉树的后序和中序的遍历，可以唯一地确

39、定二叉树。 由前序和中序确定二叉树的算法示例已知前序和中序的字符序列分别为p1,p2, ., pn和s1, s2, ., sn。例如，前序：ABCDEFGH，中序：BDCAGFHE。确定二叉树的算法为：1) 由于根是前序的首结点，可确定根为p1，同时可在中序中找到sR=p1。如：A是根。在前序中p1=A，在中序中s4=A。2) 在中序中划分左子树和右子树。根据中序，根的前面是左子树，后面是右子树。可划分为S左, 根(=sR), S右，其中：S左=s1,.,sR-1, S右=sR+1,.,sn, 分别表示左右子树的结点集合。如：BDC A GFHE3) 根据中序划分，可划分前序为：根(=p1) P左 P右，其中：P左=p2,.,pR-1，P右=pR,.,pn，S左与P左的结点相同，S右与P右的结点相同，但顺序可以不同。如：A BCD EFGH4) 从而分别获得左右子树的前序和中序。如，左子树的前序：BCD，