文档介绍：树和二叉树
现实世界的实例----家族树
引子
现实世界的实例
引子
例如:
人类的家族血缘关系
学校的行政关系
书的层次结构
操作系统的目录
结构程序模块等
。。。
树的应用
排序中的应用
编码中的应用
计算机网络线路设计
制造系统的分组技术
…..
树的基本知识(定义、基本概念和表示)
二叉树
二叉树的定义
二叉树的性质
二叉树的存储结构
二叉树基本操作与实现
二叉树的应用
二叉排序树与C#实现
赫夫曼树
本章学习内容
一、树的定义和基本概念
1. 树的定义
树是n(n≥0)个结点的有限集,
n=0------空树;
n>0------一棵非空树:
有且只有一个特定的结点——根结点(root);
当n>1,其余结点可分为m个互不相交的子集T1,T2, ……,Tm,它们又是树——根结点的子树(Sub Tree)。
定义说明了:
树是一种递归的数据结构——树中包含树。
结构特点:结点间有明显层次关系。
一、树的定义和基本概念
1. 树的定义
树是n(n≥0)个结点的有限集,
n=0------空树;
n>0------一棵非空树:
有且只有一个特定的结点——根结点(root);
当n>1,其余结点可分为m个互不相交的子集T1,T2, ……,Tm,它们又是树——根结点的子树(Sub Tree)。
2、基本概念
(1)树的结点:包含一个数据元素及若干指向其子树的分支
(2)结点的度(degree):
结点拥有的子树数。
(3)根结点:无前驱。
(4)叶子(终端结点):
度为零的结点。无后继。
(5)分支结点(非终端结点)
度不为零的结点。除根结点外,分支结点也称内部结点(1个前驱,多个后继)
(6)树的度:树内各结点的度的最大值。
一、树的定义和基本概念
2、基本概念
一、树的定义和基本概念
(7)孩子:结点的子树的根称为该结点的孩子。相应地,该结点称为孩子的双亲。
(8)兄弟:同一双亲的孩子之间互为兄弟。
(9)祖先:结点的祖先是从根到该结点所经分支上的所有结点。
(10)子孙:以某结点为根的子树中的任一结点都称为该结点的子孙。
2、基本概念
一、树的定义和基本概念
(11)结点的层次:根为第一层,根的孩子为第二层。
(12)树的深度(高度):
树中结点的最大层次。
(13)堂兄弟:
双亲在同一层上的节点互为堂兄弟。
10
2、基本概念