清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter5 trees

CHAPTER 4 8 1 Preliminaries TREES 1. Terminology Pedigree Tree binary tree Lineal Tree
CHAPTER 4 TREES §1 Preliminaries 1. Terminology Lineal Tree Pedigree Tree ( binary tree )

Definition A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of (1) a distinguished node r, called the root (2) and zero or more nonempty(sub)trees T1,., Tk, each of whose roots are connected by a directed edge from r Note Subtrees must not connect together. Therefore every node in the tree is the root of some subtree There are N-1 edges in a tree with N nodes > Normally the root is drawn at the top
【Definition】A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of (1) a distinguished node r, called the root; (2) and zero or more nonempty (sub)trees T1 , , Tk , each of whose roots are connected by a directed edge from r. Note: ➢ Subtrees must not connect together. Therefore every node in the tree is the root of some subtree. ➢ There are edges in a tree with N nodes. ➢ Normally the root is drawn at the top. N − 1

degree of a node: : =number of subtrees of the node. For exam ple, degree(A)=3, degree(F)=0 ③⑦ o degree of a tree: =nomeree degree(node ⑥⑥⑥⑦ For example, degree of this tree= 3 o' parent: : =a node that has subtrees e children ::=the roots of the subtrees of a parent s siblings =children of the same parent leaf terminal node): = a node with degree o(no children)
A B C D E F G H I J K L M degree of a node ::= number of subtrees of the node. For example, degree(A) = 3, degree(F) = 0. degree of a tree ::= For example, degree of this tree = 3. max degree(node ) nodetree leaf ( terminal node ) ::= a node with degree 0 (no children). parent ::= a node that has subtrees. children ::= the roots of the subtrees of a parent. siblings ::= children of the same parent

a' path from n, to nk:: =a(unique) sequence of nodes n1,n2,……, nk such that n; is the parent of n;+ for Isi<k o' length of path: number of edges or⑥⑥⊙⑤ the path o depth of n; :=length of the unique path from the root to n Depth(root=0 a' height of n; : := length of the longest path from n, to a leaf Height(leaf)=0, and height(D)=2 o' height (depth) of a tree : height(root)=depth (deepest leaf) o' ancestors of a node: = all the nodes along the path from the node up to the root. descendants of a node: =all the nodes in its subtrees
A B C D E F G H I J K L M ancestors of a node ::= all the nodes along the path from the node up to the root. descendants of a node ::= all the nodes in its subtrees. depth of ni ::= length of the unique path from the root to ni . Depth(root) = 0. height of ni ::= length of the longest path from ni to a leaf. Height(leaf) = 0, and height(D) = 2. height (depth) of a tree ::= height(root) = depth(deepest leaf). path from n1 to nk ::= a (unique) sequence of nodes n1 , n2 , …, nk such that ni is the parent of ni+1 for 1 i < k. length of path ::= number of edges on the path

2. Implementation 令 List Representation (A) (A(B,C,D)) o@⑦⑦(A(B(E,F,C(G,D(H,J)) (A(B(E(K,L),F),C(G),D(H(M),L,J))) K F C+G 位M D
2. Implementation ❖ List Representation A B C D E F G H I J K L M ( A ) ( A ( B, C, D ) ) ( A ( B ( E, F ), C ( G ), D ( H, I, J ) ) ) ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) A B C D E F G H I J K L M

First Child-NextSibling Representation Element First Child NextSibling B 岛由思 NNI Note: The representation is not unique since the children in a tree can be of any order
❖ FirstChild-NextSibling Representation FirstChild NextSibling Element A B C D E F G H I J K L M N A B C N D E N K N N F N N G H N I N N J N N L N N M Note: The representation is not unique since the children in a tree can be of any order

§2 Binary trees Definition A binary tree is a tree in which no node can have more than two children R R Rotate the first child-Nextsibling tree clockwise by 45 45 由思圈盟思 Element Left left Right Right
§2 Binary Trees 【Definition】A binary tree is a tree in which no node can have more than two children. N A B C N D E N K NN F NN G H N I NN J NN L NN M Rotate the FirstChild-NextSibling tree clockwise by 45. 45 Left Right Element Left Right L R L R

Propert Property 1: at the level I of binary tree, there are at most 2i-Inodes(i2 1) prove using induction Prove: when i=l, there is only root node,21-1=2 0=1 Provided to all j, i>j21, then proposition is right, that is to say there are at most 2j-Inodes at level j. From Induction hypothesis, we know that there are at most 2i-2nodes at level i-1 Since the degree of every node in binary tree is at most 2. so the maximum node value of level l is as twice as the maximum node value of level i-1 namely 2* 2i-2=2 1-1
Property Property 1: at the level I of binary tree, there are at most 2i-1nodes. (i 1) [prove using induction] Prove: when i=1,there is only root node,2i-1=2 0=1 Provided to all j, i>j1,then proposition is right, that is to say there are at most 2j-1nodes at level j. From Induction hypothesis, we know that there are at most 2i-2nodes at level i-1. Since the degree of every node in binary tree is at most 2, so the maximum node value of level I is as twice as the maximum node value of level i-1, namely 2* 2i -2= 2 i-1

Property 2: a binary tree which depth is k has at most 2 K-l nodes(k2 1) Prove: since property 1, maximum node value of a binary tree which depth is k >(the maximum rade vaue g ledi) =∑21=20+21+…+2k1=2k-1
Property 2: a binary tree which depth is k has at most 2 k-1 nodes (k 1) . Prove: since property 1,maximum node value of a binary tree which depth is k = − k i i 1 1 2 =2 0 + 21 + … + 2 k-1 = 2 k-1 1 ( ) k i the maximum nodevalueof leveli = =

Property 3: to any binary tree T, if number of leaves is no. the number of node (degree of node is 2)is n2, then n0=n2 +1. Prove: if the number of node(degree of node is 1)is nl, the total number of node is n, the total number of edge is e, then as the definition of binary tree, n=n0+n1+n2 e=2n2+nl=n-1 SO, there comes 2n2+nl=n0+nl+n2 n2=n0-1n0=n2+1
Property 3: to any binary tree T, if number of leaves is n0, the number of node (degree of node is 2) is n2, then n0= n2 +1. Prove: if the number of node (degree of node is 1) is n1, the total number of node is n, the total number of edge is e, then as the definition of binary tree, n = n0 + n1 + n2 e = 2n2 + n1 = n – 1 so,there comes 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter4 Stacks Queues.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter3 Lists.ppt
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 2 ALGORITHM ANALYSIS.ppt
- 天津大学:《数据结构 Data Structures》课程PPT教学课件(英文版)CHAPTER 8 THE DISJOINT SET ADT.ppt
- 华中师范大学计算机科学系:《数据结构》第6章 二叉树和树.ppt
- 华中师范大学计算机科学系:《数据结构》第2章 线性表.ppt
- 华中师范大学计算机科学系:《数据结构》第8章 查找表.ppt
- 华中师范大学计算机科学系:《数据结构》第7章 图和广义表.ppt
- 华中师范大学计算机科学系:《数据结构》第5章 串和数组.ppt
- 华中师范大学计算机科学系:《数据结构》第4章 栈与队列.ppt
- 华中师范大学计算机科学系:《数据结构》第3章 排序.ppt
- 华中师范大学计算机科学系:《数据结构》第1章 绪论(王敬华).ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)实验一.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第四章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第六章 树和二叉树.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第二章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第三章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)三元组表示的稀疏矩阵加法.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter6 Graph Algorithms.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter7 Search.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter8 Sorting.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)Chapter9 String.ppt
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验二.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)二叉树试验三.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验一.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验四.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验模板.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)试验五.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)复习2007级.doc
- 清华大学:《数据结构》课程教学资源(习题讲义实验)2004级计算机B卷.doc
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第一章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第九章 排序.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第1章 绪论.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第2章 线性表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第3章 栈和队列.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第4章 串.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第五章 数组和广义表.ppt
- 清华大学:《数据结构》课程电子教案(PPT课件讲稿)第6章 树和二叉树.ppt