答是要 6.1树的定义及基本术语 6.2二叉树 6.3编历二叉树 64线索二叉树 6.5二叉排序字树 6.6平衡二又树 6.7树和森林 68哈夫曼树及应用
1 内容提要 6.1 树的定义及基本术语 6.2 二叉树 6.3 编历二叉树 6.4 线索二叉树 6.5 二叉排序树 6.6 平衡二叉树 6.7 树和森林 6.8 哈夫曼树及应用
61的定义基水水 1、树的定义 (1)树的一般定义 树是包含n个结点的有限集合,在这个集合上定义了 个唯一的关系,这个关系满足下面的条件 .存在唯一的一个结点,它没有前驱,称为根 ∥.除了根结点外,其它结点有且仅有一个前驱 M.除了根结点外,在何结点a(0≤1m),都存在唯 的一个从根到的结点序列0,a1,a2,an,其中, a入a0是根。这个序列称为从根到白的路径 a2 日
2 6.1 树的定义及基本术语 1、树的定义 (1)树的一般定义 树是包含n个结点的有限集合，在这个集合上定义了 一个唯一的关系，这个关系满足下面的条件： I. 存在唯一的一个结点，它没有前驱，称为根 II. 除了根结点外，其它结点有且仅有一个前驱 III. 除了根结点外，任何结点ai (0 im)，都存在唯一 的一个从根到ai的结点序列a0 , a1 , a2 ,.., am ，其中， a0 a0是根。这个序列称为从根到ai的路径。 a1 a2 a3 a4 a5
的定业差水米con (2)树的递归定义 树是包含m个结点的有限集,在这个集合上定义了 唯一的关系,它满足下面的条件: .有个待定的称为根的结点; ∥.-mn>1的,除了根以外的其余结点根据它们之间 的关系可分为m个不相交的有限集71,72,,Tm,其中 ,每个有限集都是一棵树。这些树称为根的子树 Tl={b,e,f};T2={c};T3={d}
3 树的定义及基本术语(cont’d) (2)树的递归定义 树是包含n个结点的有限集，在这个集合上定义了 唯一的关系，它满足下面的条件： I. 有个特定的称为根的结点； II. 当n>1时，除了根以外的其余结点根据它们之间 的关系可分为m个不相交的有限集T1,T2,..,Tm，其中 ，每个有限集都是一棵树。这些树称为根的子树。 a b c d e f T1={b,e,f};T2={c};T3={d}
(3)树的基本术语 1.根,唯一没有前驱的结点 2.度,结点的度是结点的子树数,树的度是指结点 度的最大值 3.叶子,度为0的结点,也称终端结点 4.分枝结点,叶子之外的结点,也称非终端结点。 除了根以外的分枝结点又称内部结点 5.双亲、子女、祖先、子孙,结点子树的根称为结 点的子女,该结点就是它子女的双来;某结点的 祖先是指从根到该结点的路径上的全部结点;结 点的子树中全部结点都是该结点的子孙 d
4 树的定义及基本术语(cont’d) (3)树的基本术语 1. 根,唯一没有前驱的结点 2. 度,结点的度是结点的子树数目,树的度是指结点 度的最大值 3. 叶子，度为0的结点，也称终端结点 4. 分枝结点，叶子之外的结点，也称非终端结点。 除了根以外的分枝结点又称内部结点。 5. 双亲、子女、祖先、子孙，结点子树的根称为结 点的子女，该结点就是它子女的双亲；某结点的 祖先是指从根到该结点的路径上的全部结点；结 点的子树中全部结点都是该结点的子孙。 a b c d e f
的定差水语cm (3)树的基本术语 6.兄弟、堂兄弟,同一个结点的子女互为兄弟,双 亲为兄弟的结点互称堂兄弟 7.结点的层次、树的深高度,根为第1层,结点 的层次是其双来层次加1。树的深度是指结点的最 大层数 8.有序树、无序树,如果结点的各子树自左向右是 有次序的,则称有序树,否则称无序树 9.森林,m棵互不相交的树就构成了森林 a 第1层 d 第2层 c 3层 e f g
5 树的定义及基本术语(cont’d) (3)树的基本术语 6. 兄弟、堂兄弟，同一个结点的子女互为兄弟，双 亲为兄弟的结点互称堂兄弟。 7. 结点的层次、树的深度(高度)，根为第1层，结点 的层次是其双亲层次加1。树的深度是指结点的最 大层数。 8. 有序树、无序树，如果结点的各子树自左向右是 有次序的，则称有序树，否则称无序树 9. 森林，m棵互不相交的树就构成了森林。 a b c d e f g 第1层 第2层 第3层
62二 1.二又树的概念 每个结点最多有2棵子树,并且子树有左右之 分,不能任意颜倒 二又树有5种形态: ①空树②只有一个根 ③只有左子树④只有右子树 ⑤有两个子树 2.二又树的性质 在二又树的第层上E多有2-1个结点(>=1 ②深度冰的二叉树至多有2-1个结点
6 6.2 二叉树 1. 二叉树的概念 每个结点最多有2棵子树，并且子树有左右之 分，不能任意颠倒。 二叉树有5种形态： ①空树 ②只有一个根 ③只有左子树 ④只有右子树 ⑤有两个子树 2. 二叉树的性质 ①在二叉树的第i层上至多有2 i－1个结点(i>=1) ②深度为k的二叉树至多有2 k -1个结点。 1 2 3 4 5 6 7 8 9
Xpfcont'd) 2.二又树的性质 ③设二又树中,叶结点数为0度为1的结点数为1度 为2的结点数机m2,则有:n=n2+1 因为N=n0+n1+n2=1+n1*1+n22 ④具有n个结点的完全二又树的深度为Log2n/+1 og2n/表示g2取整 满二又树:具有最多结点数的二又树(即一棵深度为 k且有2k-1个结点的二叉树) 完全二叉树:将满二叉树从右向左 删除叶子的结果,因此, ⑤ 结点数n2k1-1
7 二叉树(cont’d) 2. 二叉树的性质 ③ 设二叉树中，叶结点数为n0 ,度为1的结点数为n1 ,度 为2的结点数为n2 ,则有： n0 = n2 + 1 因为 N=n0+n1+n2=1+n1 *1+n2 *2 ④ 具有n个结点的完全二叉树的深度为 log2n +1 log2n 表示 log2n取整 满二叉树：具有最多结点数的二叉树（即一棵深度为 k且有2 k -1 个结点的二叉树） 完全二叉树：将满二叉树从右向左 删除叶子的结果，因此 , 结点数 n2k-1 -1 1 2 3 4 5 6 7 8 9
XBfIcont d 3.二又树的存情结构 (1)顺序存,利用数组按照完全二又树的方式 对结点编号,根据编号将结点存放在数组中相应 的位置中 # define M50∥二叉树的最大结点数 typedef elemtype SQTREEIN∥顺序存储的二叉树 SQ TREE bt 0123456789 ABCEF ①F6
9 二叉树(cont’d) 3. 二叉树的存储结构 (1) 顺序存储，利用数组按照完全二叉树的方式 对结点编号，根据编号将结点存放在数组中相应 的位置中。 #define N 50 //二叉树的最大结点数 typedef elemtype SQTREE[N]; //顺序存储的二叉树 SQTREE bt; A B C E F 1 2 3 4 5 6 A B C E F 0 1 2 3 4 5 6 7 8 9
XBfIcont d 3.二又树的存储结构 (2)链式存储,利用二又链表或三又链表 PARENT KIANN /child data rchild B 团CZ DATA Iciild data parent rchild LCHILD RCHILD E酉F typedef struct treenode teletype data;M结点数据 指向左右孩子的指针 struct treenode lchild, rchild / parent*/, JTREENODE, *TREENODEPTR, BTREE
10 二叉树(cont’d) 3. 二叉树的存储结构 (2)链式存储，利用二叉链表或三叉链表 typedef struct treenode {elemtype data; //结点数据 //指向左右孩子的指针 struct treenode *lchild,*rchild /*,*parent*/; }TREENODE,*TREENODEPTR,*BTREE A ^B C^ ^ E ^ ^ F ^ DATA PARENT LCHILD RCHILD lchild data rchild lcjild data parent rchild
14.一又树的建立(1)按层序历序为入顺序 whil(fontlchild==NULL it>Child=(TREENODEPTR)malloc(sizeof(TREENODE)): t->lchild->data=value ∥建立左孩子结点 rear+;q[rear]-t-) Child;∥左孩子入队 scanf(%od", &value) if(value==0)t>rchild=NULL it >rchild=(TREENODEPTR)malloc(sizeof(TREENODE) t->rchild->data=value ∥建立左孩子结点 rear++;q[rear}=t> rchild;∥左孩子入队 i//while
11 ＃define N 50 //定义二叉树最大结点数 void createtree(BTREE *root) {int value,front,rear; TREENODEPTR t,q[N]; //q是队列，front,rear是队头队尾下标。 scanf("%d",&value); //开始创建根结点 if(value==0){*root=NULL; return;}; //输入0，表示空结点 *root=(TREENODEPTR)malloc(sizeof(TREENODE)); (*root)→data=value; rear=front=1; q[front]=*root; //根指针入队 二叉树(cont’d) 4. 二叉树的建立 (1) 按层序遍历顺序为输入顺序 while(front<=rear) //只要队列不空 { t＝q[front]; front++; //出队一结点指针 scanf("%d",&value); if(value==0) t→lchild=NULL; else {t→lchild=(TREENODEPTR)malloc(sizeof(TREENODE)); t→lchild→data=value; //建立左孩子结点 rear++; q[rear]=t→lchild; //左孩子入队 } scanf("%d",&value); if(value==0) t→rchild=NULL; else {t→rchild=(TREENODEPTR)malloc(sizeof(TREENODE)); t→rchild→data=value; //建立左孩子结点 rear++; q[rear]=t→rchild; //左孩子入队 } }//while } 5 3 4 7 9