63树和森林 计算机教研宦 第1页 2021/2/19
Data Structure 数据结构—— 第6章树和二叉树 胡建华 2021/2/19 计算机教研室 第 1 页 6.3 树和森林
@63.1树和森林的定义 树的定义 定义:树(tren(n>0)个结点的有限集T,其中 (1)有且仅有一个特定的结点,称为树的根(root) (2)当m1时,其余结点可分为m(m>0)个互不相交的有限 集T,T2m,其中每一个集合本身又是一棵树,称为 根的子树( subtree) 特点: 树中至少有一个结点根 树中各子树是互不相交的集合 森林( forest)—m(m≥0)棵互不相交的树的集合 计算机教研宦 第2页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第2页 6.3.1 树和森林的定义 • 树的定义 – 定义：树(tree)是n(n>0)个结点的有限集T，其中： （1）有且仅有一个特定的结点，称为树的根(root) （2）当n>1时，其余结点可分为m(m>0)个互不相交的有限 集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为 根的子树(subtree) – 特点： • 树中至少有一个结点——根 • 树中各子树是互不相交的集合 • 森林(forest)——m(m0)棵互不相交的树的集合
只有根结点的树 有子树的树 根 B )cG画 K 子树 计算机教研宦 第3页 2021/2/19
Data Structure 数据结构—— 第6章树和二叉树 胡建华 2021/2/19 计算机教研室 第 3 页 A 只有根结点的树 A B C D E F G H I J K L M 有子树的树 根 子树
@基本术语 结点(node)表示树中的元素,包括数据项及若干 指向其子树的分支 结点的度( degree)-结点拥有的子树数 叶子(ea)度为0的结点 ·孩子(chid)结点子树的根称为该结点的孩子 ·双亲( parents)孩子结点的上层结点叫该结点的 兄弟( sibling)—同一双亲的孩子 树的度 棵树中最大的结点度数 意·结点的层次eve)从根结点算起,根为第一层,它 的孩子为第二层…… ·深度(dept)树中结点的最大层次数 有序树和无序树 计算机教研宦 第4页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第4页 基本术语 • 结点(node)——表示树中的元素，包括数据项及若干 指向其子树的分支 • 结点的度(degree)——结点拥有的子树数 • 叶子(leaf)——度为0的结点 • 孩子(child)——结点子树的根称为该结点的孩子 • 双亲(parents)——孩子结点的上层结点叫该结点的~ • 兄弟(sibling)——同一双亲的孩子 • 树的度——一棵树中最大的结点度数 • 结点的层次(level)——从根结点算起，根为第一层，它 的孩子为第二层…… • 深度(depth)——树中结点的最大层次数 •有序树和无序树
结点A的度 叶子:K,L,F,G,M,I,J 结点B的度:2 结点M的度 结点I双亲:D 结点A的孩子:B,C,D 结点L的双亲:E 结点B的孩子:E,F 结点B,C,D为兄弟 树的度:3 结点K,L为兄弟 ⑥⑥③○ 树的深度:4 测结点A的层次:1 结点F,G为堂兄弟 结点M的层次: 结点A是结点F,G的祖先 计算机教研宦 第5页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第5页 A B C D E F G H I J K L M 结点A的度：3 结点B的度：2 结点M的度：0 叶子：K，L，F，G，M，I，J 结点A的孩子：B，C，D 结点B的孩子：E，F 结点I的双亲：D 结点L的双亲：E 结点B，C，D为兄弟 树的度：3 结点K，L为兄弟 结点A的层次：1 结点M的层次：4 树的深度：4 结点F，G为堂兄弟 结点A是结点F，G的祖先
@基本操作 查找类 e Root(T ∥求树的根结点 Value(, cur e ∥求当前结点的元素值 o Parent(,cur e ∥求当前结点的双亲结点 G LeftChild(T, cur ∥求当前结点的最左孩子 Rightsibling(T, cur e ∥求当前结点的右兄弟 TreeDepth(T) ∥求树的深度 的 Traverse Tree(T,Ⅴisit0)∥遍历 插入类 ca InitTree(&t ∥初始化置空树 Createtree((&T, definition)∥/按定义构造树 Assign(,curc, value)∥给当前结点赋值 Insertchild(&工,&Pc)∥将以c为根的树插入为结点p的第棵子树 删除类 Delete child(&T,&p,i)∥删除结点p的第裸子树 Deletechild(&T,&p,i)∥删除结点p的第裸棵子树 第6页 Delete child(&T,&p,i)∥删除结点p的第棵子树
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第6页 基本操作： • 查 找 类 Root(T) // 求树的根结点 Value(T, cur_e) // 求当前结点的元素值 Parent(T, cur_e) // 求当前结点的双亲结点 LeftChild(T, cur_e) // 求当前结点的最左孩子 RightSibling(T, cur_e) // 求当前结点的右兄弟 TreeDepth(T) // 求树的深度 TraverseTree( T, Visit() ) // 遍历 • 插 入 类 InitTree(&T) // 初始化置空树 CreateTree(&T, definition) // 按定义构造树 Assign(T, cur_e, value) // 给当前结点赋值 InsertChild(&T, &p, i, c) // 将以c为根的树插入为结点p的第i棵子树 • 删 除 类 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树 DeleteChild(&T, &p, i) // 删除结点p的第i棵子树
@632树和森林的存储结构 ·1.双亲表示法: data parent A 0A-1 r=0 1B0 BCD n=6 2C0 E( 3D0 4E2 5F2 6G5 计算机教研宦 第7页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第7页 6.3.2 树和森林的存储结构 • 1.双亲表示法: A B C D E F G 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 r=0 n=6 data parent
@C语言的类型描述: #define MAX TREE sIze 100 结点结构: data parent typedef struct PTNode i Elem data int parent;∥双亲位置域 3 PTNode 树结构: 0 ty pede struct i PTNode nodes MAX TREE Size intr.n:∥/根结点的位置和结点个数 3 PTree 计算机教研宦 第8页 2021/2/19
Data Structure 数据结构—— 第6章树和二叉树 胡建华 2021/2/19 计算机教研室 第 8 页 C语言的类型描述 : #define MAX_TREE_SIZE 100 • 结点结构: typedef struct PTNode { Elem data; int parent; // 双亲位置域 } PTNode; • 树结构 : typedef struct { PTNode nodes [MAX_TREE_SIZE]; int r, n; // 根结点的位置和结点个数 } PTree; data parent
@2.孩子链表表示法: data firstchild 0A BQ①1B A 2 C 5∧ 3 D 4 E G 5F ∧ 6∧ 06 6 G 计算机教研室 第9页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第9页 A B C D E F G 0 A 1 B 2 C 3 D 4 E 5 F 6 G r=0 n=6 data firstchild 1 2 3 4 5 6 2.孩子链表表示法:
C语言的类型描述: 孩子结点结构: typedef struct CTNode i int child child next struct CTNode * next: 3*ChildPtr; 双亲结点结构 图 typedef struct{ Elem data: ChildPtr firstchild;∥/孩子链的头指针 3 CTBOx; 树结构: typedef struct t CTBox nodes MAX TREE Size; intn,r;∥/结点数和根结点的位置 3 CTree 计算机教研宦 第10页 2021/2/19
Data Structure 数 据 结 构—— 第 6 章 树 和 二 叉 树 胡建华 2021/2/19 计算机教研室 第10页 C语言的类型描述: • 孩子结点结构: typedef struct CTNode { int child; struct CTNode *next; } *ChildPtr; • 双亲结点结构 typedef struct { Elem data; ChildPtr firstchild; // 孩子链的头指针 } CTBox; • 树结构: typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; // 结点数和根结点的位置 } CTree; child next