数据结构第6章二叉树和树习题.ppt

第6章 二叉树和树习题 习题6.6: * * 习题6.2: 否 习题6.3: 习题6.4: ? log220? +1 =5 习题6.5: CBA CBA CBA CBA BCA 后 序 ABC CBA ACB BCA BAC 中 序 ABC ABC ABC ABC ABC 前 序 (5) (4) (3) (2) (1) 1 Φ 0 0 Φ 1 0 0 0 1 1 1 习题6.7: (a) 空树、只有根结点的二叉树、右单支二叉树 (b) 空树、只有根结点的二叉树、左支二叉树 (c) 空树、只有根结点的二叉树 习题6.8: void Get_PreOrder(BiTree T,int k,TElemType e) { //求先序序列中第k个位置上结点的值 if(T) {??? c++; //每访问一个子树的根都会使前序序号计数器加1, //c设为全局量???? if(c==k) { e=T-data; return;}????????? else???? {?? Get_PreOrder(T-lchild, k, e ); //在左子树中查找?????? Get_PreOrder(T-rchild, k ,e); //在右子树中查找???? }?? }//if } //Get_PreOrder 习题6.9: int LeafCount(BiTree T) //求二叉树中叶子结点的数目{ ??if(!T) return 0; //空树没有叶子?? else if(!T-lchild!T-rchild) return 1; //叶子结点?? else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild); //左子树的叶子数加上右子树的叶子数} //LeafCount 习题6.10: //交换所有结点的左右子树 void Change_BiTree (BiTree T){ BiTree temp; if(T) {? temp=T-lchild; T-lchild=T-rchild; T-rchild=temp; } //交换左右子树 ?? if(T-lchild) Change_BiTree(T-lchild);?? if(T-rchild) Change_BiTree (T-rchild); //左右子树再分别交换各自的左右子树}//Change_BiTree 习题6.11: //求二叉树中以值为x的结点为根的子树深度int Get_Sub_Depth(BiTree T,int x, int depth) {? if(T-data==x)?? { depth=Get_Depth(T); return;}//找到了值为x的结点,求其深度???else?? {???if(T-lchild) Get_Sub_Depth(T-lchild,x,depth);??? if(T-rchild) Get_Sub_Depth(T-rchild,x,depth); } //在左右子树中继续寻找} //Get_Sub_Depth int Get_Depth(BiTree T) //求子树深度的递归算法{ ??if(!T) return 0;?? else?? {???m=Get_Depth(T-lchild);???? n=Get_Depth(T-rchild);???? return (mn?m:n)+1;?? }} //Get_Depth 习题6.12: // 删除所有以元素x为根的子树 void Del_Sub_x(BiTree T,int x){ ?if(T-data==x) Del_Sub(T); //删除该子树?? else?? { ??if(T-lchild) Del_Sub_x(T-lchild,x);???? if(T-rchild) Del_Sub_x(T-rchild,x); ?? } //else 在左右子树中继续查找} //Del_Sub_x void Del_Sub(BiTree T) //删除子树T{? if(T-lchild) Del_Sub(T-lchild);?? if(T-rchild) Del_Sub(T-rchild);?? free(