下载此文档

数据结构与算法第六章课后答案第六章 树和二叉树.doc


文档分类:办公文档 | 页数:约6页 举报非法文档有奖
1/6
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/6 下载此文档
文档列表 文档介绍
第6章树和二叉树(参考答案)

(1)根结点a

三个结点的树的形态: 三个结点的二叉树的形态:
(2) (3)
(1) (1) (2) (4) (5)
设树的结点数是n,则
n=n0+n1+n2+……+nm+ (1)
设树的分支数为B,有
n=B+1
n=1n1+2n2+……+mnm+1 (2)
由(1)和(2)有:
n0=n2+2n3+……+(m-1)nm+1

(1) ki-1 (i为层数)
(2) (n-2)/k+1
(3) (n-1)*k+i+1
(4) (n-1)%k !=0; 其右兄弟的编号 n+1
(1)顺序存储结构
1 2 3 4 5 6 7 8 9 10 11 12 13 14
A
B
C
D
#
E
F
#
G
#
#
#
#
H
注:#为空结点
A
C
B ^
^ E ^
F ^
^ D
^ H ^
^ G ^

(1) 前序 ABDGCEFH
(2) 中序 DGBAECHF
(3) 后序 GDBEHFCA

(1) 空二叉树或任何结点均无左子树的非空二叉树
(2) 空二叉树或任何结点均无右子树的非空二叉树
(3) 空二叉树或只有根结点的二叉树

int height(bitree bt)
// bt是以二叉链表为存储结构的二叉树,本算法求二叉树bt的高度
{ int bl,br; // 局部变量,分别表示二叉树左、右子树的高度
if (bt==null) return(0);
else { bl=height(bt->lchild);
br=height(bt->rchild);
return(bl>br? bl+1: br+1); // 左右子树高度的大者加1(根)
}
}// 算法结束

void preorder(cbt[],int n,int i);
// cbt是以完全二叉树形式存储的n个结点的二叉树,i是数
// 组下标,初始调用时为1。本算法以非递归形式前序遍历该二叉树
{ int i=1,s[],top=0; // s是栈,栈中元素是二叉树结点在cbt中的序号
// top是栈顶指针,栈空时top=0
if (n<=0) { printf(“输入错误”);exit(0);}
while (i<=n ||top>0)
{ while(i<=n)
{visit(cbt[i]); // 访问根结点
if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空,其编号进栈
i=2*i;// 先序访问左子树
}
if (top>0) i=s[top--]; // 退栈,先序访问右子树
} // END OF while (i<=n ||top>0)
}// 算法结束
//以下是非完全二叉树顺序存储时的递归遍历算法,“虚结点”用‘*’表示
void preorder(bt[],int n,int i);
// bt是以完全二叉树形式存储的一维数组,n是数组元素个数。i是数
// 组下标,初始调用时为1。
{ if (i<=n

数据结构与算法第六章课后答案第六章 树和二叉树 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数6
  • 收藏数0 收藏
  • 顶次数0
  • 上传人mh900965
  • 文件大小786 KB
  • 时间2018-04-10