[信息与通信]树.ppt

6.2.2 树的表示 （1）树形图表示??? 　树形图表示是树结构的主要表示方法。??? 树的树形图表示中：结点用圆圈表示，结点的名字写在圆圈旁边（有时亦可写在圆圈内）。 （2）树的其他表示法① 嵌套集合表示法??? 　是用集合的包含关系来描述树结构。? 上图(a)树的嵌套集合表示法如图(b)? ?② 凹入表表示法??? 　类似于书的目录，上图(a)树的凹入表示法如图(c)③ 广义表表示法??? 　用广义表的形式表示的。上图(a)树的广义表表示法如图(d)　　（A（B（E，F（I，J）），C，D（G，H））） 6.4.4 思考 已知一棵二叉树的前序跟中序遍历序列，是否能求得这棵二叉树？ 6.4.5 二叉树的应用 二叉树的初始化 void CreateBinTree (BinTree *T)????? { //构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身??????? char ch；??????? if((ch=getchar())==) T=NULL； //读人空格，将相应指针置空???????? else{ //读人非空格????????????? *T=(BinTNode *)malloc(sizeof(BinTNode))； //生成结点????????????? (*T)-data=ch；????????????? CreateBinTree((*T)-lchild)； //构造左子树????????????? CreateBinTree((*T)-rchild)； //构造右子树???????????? }????? } 6.6.3 森林与二叉树之间的转换 图6.18 森林转换为二叉树 6.4.1 先序遍历 先序遍历可以递归地描述如下： 如果二叉树为空，则空操作，否则： ① 访问根结点； ② 按先序次序遍历左子树； ③ 按先序次序遍历右子树。 先序遍历的递归算法如下: /*算法描述6.2 先序遍历的递归算法*/ void preorder(BTlink * p) { if(p!=NULL) {printf(%c\n，p-data)； /*访问根结点*/ preorder(p-lch)； /*按先根次序遍历左子树*/ preorder(p-rch)； /*按先根次序遍历右子树*/ } } /*preorder*/ 图6.11 遍历序列示例 6.4.2 中序遍历 中序遍历可以递归地描述如下： 如果二叉树为空，则空操作，否则： ① 按中序次序遍历左子树， ② 访问根结点， ③ 按中序次序遍历右子树。 中序遍历递归算法如下: /*算法描述6.3 中序遍历的递归算法*/ void inorder(BTlink *p) {if (p!=NULL) {inorder(p-lch)； /*中序遍历左子树*/ printf(%c\n，p-data)； /*访问根结点*/ inorder(p-rch)； /*中序遍历右子树*/ } }/*inorder*/ 例如，图6.11(a)所示二叉树的中根遍历序列为BAC, 图6.11(b)所示二叉树的中根遍历序列为BCAEDF。 6.4.3 后根遍历 后根遍历可以递归地描述如下： 如果二叉树为空，则空操作，否则： ① 后序遍历左子树； ② 后序遍历右子树； ③ 访问根结点。 后根遍历递归算法如下： /*算法描述6.4 后序遍历的递归算法*/ void postorder (BTlink* p ) { if ( p!= NULL ) { postorder ( p-lch); /*后序遍历左子树*/ postorder ( p-rch ); /*后根遍历右子树*/ printf ( %c＼n，p-data); /*访问根结点*/ } } /*postorder*/ 例如，图6.11(a)所示二叉树的后序遍历序列为BCA, 图6.11(b)所示二叉树的后根遍历序列为CBEFDA。 6.5 线索二叉树 6.5.1 线索二叉树的基本概念 我们发现，具有n个结点的二叉树中有n – 1条边指向其左、右孩子，这意味着在二叉链表中的2n个孩子指针域中只用到了n –1 个域，还有另外n+1个指针域是空