[]软件技术基础_树.ppt

1.3 非线性结构 1.3.1 树 1.3.2 二叉树 ③关于完全二叉树的其他描述形式： 如果对满二叉树的节点从上至下，从左至右连续编号，具有n个节点的完全二叉树各节点与同样深度的满二叉树的前n个节点一一对应 叶节点仅位于下两层，对任一节点，若其右子树的深度为1，则其左子树的深度不小于1 例2：利用二叉树后序遍历计算二叉树结点个数 int size(btreenode *bt) { if(bt==NULL) return(0); else return( 1 + size ( bt -Lchild ) + size ( bt -Rchild ) ); } 例3：建立二叉树 设输入次序：（先序） 以先根遍历算法为基础，修改为二叉树的建立算法 2、哈夫曼树——最优二叉树（路径带权总长最小） 作业: P.75~76：18, 19, 20, 21, 22； 例1：在一棵二叉树中找某结点s的双亲结点t 算法实现：采用中序遍历 btreenode *searchparent(btreenode *s, btreenode *bt) { btreenode *p, *t; p=bt; setnull(stack); if(s==bt) return(NULL); else{ /*s结点为根结点，无双亲，返回空指针*/ while(p!=NULL || !empty(stack)){ if(p!=NULL){ push(stack,p); p=p-Lchild; } else{ p=pop(stack); if(p-Lchild==s || p-Rchild==s){ t=p; p=NULL; setnull(stack); } else p=p-Rchild; } } return(t); } } /*找到双亲结点t*/ Process (P) /*主动结束遍历过程*/ ABC_ _ DEF _ _ G _ _ _ H _ I _ JK _ _ L _ _ A B C _ _ D E F _ _ G _ _ _ H _ I _ J K _ _ L _ _ 每一个空格“_”表示一个空指针 利用先根遍历算法框架，按照遍历顺序，逐个结点地建立二叉树。 根据输入的情况，将新结点放在指定的位置，然后从新结点开始下一个过程；如果输入是空格，则置结点的相应子树指针为空 void c_preorder( root ){ process(root); if( root-Lchild != NULL) c_preorder (root-Lchild); if( root-Rchild != NULL) c_preorder(root-Rchild); } 将新链点挂在root的左子树上; 将新链点挂在root的右子树上; 输入一个值，并生成新链点； 输入一个值，并生成新链点； void create_tree(btreenode ** root){ read( ch ); if ( ch = = ‘ ‘ ){ *root = NULL; return; } p-data = ch; p-Lchild = NULL; p-Rchild = NULL; p = (btreenode *)malloc(sizeof(btreenode)); 输入新元素 生成整个树的根 c_preorder(p); } 以先根遍历算法为基础递归生成二叉树 九、二叉树的重构： 对于一个遍历序列，若没有加空格字符来表示空孩子，则不能根据一个遍历序列构造出二叉树。因为无法从遍历序列中区分二叉树的左右子树。所以必须用两个序列联合才能构造二叉树。 已知先序序列和中序序列，或者已知后序序列和中序序列，可唯一求出一棵二叉树。而已知先序序列和后序序列，则不能唯一求出一棵二叉树。 例：两棵不同的二叉树如图所示： A B C A B C 先序序列相同：ABC后序序列相同：CBA ∵二叉树是有序树，其子树有左、右之分，且次序不能颠倒。 ∴这是两棵不同的二叉树 例：已知一棵二叉树，其 先序序列为：ABCDEFGHIJ 中序序列为：CBDEAFHIGJ 试画出对应的二叉树。 解：按遍历算法可知： 二叉树的根结点为A， 其左子树的先序序列为：BCDE