数据结构基本知识.ppt

数据结构基本知识
——树、栈、队列
树
树的基本概念
树的相关术语
二叉树
遍历(周游)二叉树
树的基本概念
树的定义 树是一个集合以及在该集合上定义的一种关系构成。集合中的元素称为树的结点。
注意:
单个结点是一棵树,树根就是该结点本身。
空集合也是树,称为空树。空树中没有结点。
一棵典型的树
A
C
D
B
E
F
I
J
G
H
树根(树的根结点)
分枝结点
树叶结点
结点集合:K={A,B,C,D,E,F,G,H,I,J}
K上的关系N={〈A,B〉,〈A,C 〉,〈A,D 〉,〈B,E 〉,〈B,F 〉,〈D,G 〉,〈D,H 〉,〈F,I 〉,〈F,J 〉}
树的相关术语
度:一个结点的儿子结点的个数称为该结点的度。一棵树的度是该树中结点度数最大值.
树叶:树中度为零的节点称为树叶结点或终端结点;不为零的结点称为分枝结点或非终端结点;除根结点外的分枝结点称为内部结点。
高度:树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。
有序树:在树中如果结点的相对次序是重要的,不能改变的,称为有向有序树
森林:是零棵或多棵不相交的树的集合。
二叉树:二叉树由结点的有限集合构成,这个有限集合或者为空集,或者由一个根结点及两棵不相交的分别称为这个根的左子树和右子树的二叉树组成。度数最大为二。
二叉树的概念
A
A
A
A
B
B
B
C
根和空的
左右子树
根和非空的左子
树,空的右子树
根和空的左子树,
非空的右子树
根和非空
的左右子树
空二叉树
特殊的二叉树
满二叉树:如果一棵二叉树的任何结点,或者是树叶,或者恰有两棵非空子树。
完全二叉树: 如果一棵二叉树最多只有最下面的两层结点度数可以小于2,并且最下面一层的结点都集中在该层最左边的若干位置上。
作业:对于三个结点A ,B,C,有多少个多少个不同的二叉树?把它们画出来.
遍历(周游)二叉树
方式:前序遍历、中序遍历、后序遍历
前序遍历:访问根;按前序遍历左子树;按前序遍历右子树。
中序遍历:按中序遍历左子树;访问根;按中序遍历右子树。
后序遍历:按后序遍历左子树;按后序遍历右子树;访问根;
前序遍历:ABEFIJCDGH
中序遍历:EBIFJACGDH
后序遍历:EIJFBCGHDA
作业:已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为DBAEGCHFI与DBGEHIFCA则该二叉树的先序遍历的顺序为:
C
D
B
E
F
I
J
G
H
A
二叉树的重要性质
高度为h>=0的二叉树至少有h+1个结点。
高度不超过h(>=0)的二叉树至多有个结点。
含有n >=1个结点的二叉树的高度至多为n-1;
含有n >=1个结点的二叉树的高度至少为logn;因此其高度为O(logn)。