数据结构 邓欣-ch6.pptVIP

* 中序遍历算法: #includestdio.h #includestdlib.h #define NULL 0 Typedef struct node{ char data; struct node *leftchild,*rightchild; }TREENODE; TREENODE *root; TREENODE *creat_tree(); Void inorder(TREENODE *); * TREENODE *creat_tree() { TREENODE *t; char c; c=getchar(); if(c= =‘#’) return(NULL); else{ t=(TREENODE *)malloc(sizeof(TREENODE)) t – data=c; t –leftchild=create_tree(); t –rightchild=create –tree(); } return(t); } AB#D##C## * Void inorder(TREENODE *p) { if(p!=NULL) { inorder(p–leftchild); printf(“%c”,p–data) inorder(p–rightchild); } } * 利用二叉树后序遍历计算二叉树结点个数 int Size (TREENODE *p) { if ( p == NULL ) return 0; else return 1 + Size ( p→leftChild ) + Size ( p→rightChild ); } 应用二叉树遍历的事例 * int Height ( TREENODE *p ) const { if ( p == NULL ) return 0; else return 1 + Max (Height ( p→leftChild ), Height ((p→rightChild ) ); } 二叉树的高度 * 遍历的其他应用 Copy Interchange all left and right subtrees Traversal level by level * 树的存储表示 ? 广义表表示（不要求） 树的广义表表示 (结点的utype域没有画出) 树与森林 * ? 双亲表示 * ? 左子女-右兄弟表示法 第一种解决方案 第二种解决方案 树的左子女-右兄弟表示 data child1 child2 child3 childd data firstChild nextSibling * 森林与二叉树的转换 森林与二叉树的对应关系 * (1) 森林转化成二叉树的规则 ? 若F为空，即n = 0，则 对应的二叉树B为空二叉树。 ? 若F不空，则 对应二叉树B的根root (B)是F中第一棵树T1的根root (T1)； 其左子树为B (T11, T12, …, T1m)，其中，T11, T12, …, T1m是root (T1)的子树； 其右子树为B (T2, T3, …, Tn)，其中，T2, T3, …, Tn是除T1外其它树构成的森林。 * (2) 二叉树转换为森林的规则 ? 如果B为空，则 对应的森林F也为空。 ? 如果B非空，则 F中第一棵树T1的根为root； T1的根的子树森林{ T11, T12, …, T1m }是由 root 的左子树 LB 转换而来，F 中除了 T1 之外 其余的树组成的森林{ T2, T3, …, Tn } 是由 root 的右子树 RB 转换而成的森林。 * 树的遍历 树的二叉树表示 及对应遍历方式 深度优先遍历 * 二叉树的计数 由二叉树的前序序列和中序序列可唯一地确定一棵二叉树。例, 前序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下： * 如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。 问题