数据结构第六章树和二叉树.ppt

以字符串的形式“根左子树右子树”定义一棵二叉树例如:以空白字符“”表示ABCDABCD空树只含一个根结点的二叉树A以字符串“A”表示以下列字符串表示intCreateBiTree(BiTreeT){scanf(ch);if(ch==)T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T-data=ch;//生成根结点CreateBiTree(T-lchild);//构造左子树CreateBiTree(T-rchild);//构造右子树}return1;}//CreateBiTreeABCDABCD上页算法执行过程举例如下:ATBCD^^^^^scanf(ch);if(ch==)T=NULL;else{if(!(T=newBiTNode))exit(OVERFLOW);T-data=ch;CreateBiTree(T-lchild);CreateBiTree(T-rchild);仅知二叉树的先序序列“abcdefg”能否唯一确定一棵二叉树？由二叉树的先序和中序序列建树如果同时已知二叉树的中序序列“cbdaegf”,则会如何？二叉树的先序序列二叉树的中序序列左子树左子树右子树右子树根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列6.5

线索二叉树何谓线索二叉树？线索链表的遍历算法一、何谓线索二叉树？遍历二叉树的结果是，求得结点的一个线性序列。ABCDEFGHK例如:先序序列:ABCDEFGHK中序序列:BDCAHGKFE后序序列:DCBHKGFEA指向该线性序列中的“前驱”和“后继”的指针，称作“线索”1与其相应的二叉树，称作“线索二叉树”2包含“线索”的存储结构，称作“线索链表”3ABCDEFGHK4^D^5C^6^B7E^8对线索链表中结点的约定：在二叉链表的结点中增加两个标志域，并作如下规定：若该结点的左子树不空，则Lchild域的指针指向其左子树，且左标志域的值为“0”；否则，Lchild域的指针指向其“前驱”，且左标志的值为“1”。如此定义的二叉树的存储结构称作“线索链表”若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为“0”；否则，rchild域的指针指向其“后继”，且右标志的值为“1”。线索链表的类型描述：typedefstructBiThrNod{添加标题TElemTypedata;添加标题structBiThrNode*lchild,*rchild;//左右指针添加标题PointerThrLTag,RTag;//左右标志添加标题}BiThrNode,*BiThrTree;添加标题typedefenum{Link,Thread}PointerThr;添加标题//Link==0:指针，Thread==1:线索添加标题二、线索链表的遍历算法:for(p=firstNode(T);p;p=Succ(p))Visit(p);添加标题由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。添加标题例如:对中序线索化链表的遍历算法添加标题中序遍历的第一个结点？添加标题在中序线索化链表中结点的后继？添加标题左子树上处于“最左下”（没有左子树）的结点添加标题若无右子树，则为后继线索所指结点添加标题否则为对其右子树进行中序遍历时访问的第一个结点添加标题voidInOrderTraverse_Thr(BiThrTreeT)