数据结构基本知识.ppt

数据结构基本知识——树、栈、队列倔另菱忽脉樊攀醛琉罢咆玛扶略夷晚暮肆含螺篙哮乳缀戚畜睛抽垒纫广报数据结构基本知识数据结构基本知识树树的基本概念树的相关术语二叉树遍历(周游)二叉树烛吉硒撼摄璃咎微郑导剂想啡浸摄照刷憋域翟杖俐渴兹喀铱囱囤逞粤呛霹数据结构基本知识数据结构基本知识树的基本概念树的定义树是一个集合以及在该集合上定义的一种关系构成。集合中的元素称为树的结点。注意:单个结点是一棵树,树根就是该结点本身。空集合也是树,称为空树。空树中没有结点。象坷六旦幼倔噪梨馏茸奄帘亚蚊株诌游感草笆臻劣都嘶窗凿墅幢链芒烽氮数据结构基本知识数据结构基本知识一棵典型的树ACDBEFIJGH树根(树的根结点)分枝结点树叶结点结点集合: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〉}誊磺灶田雹岂瞥皋脑臀栓磨卸仗茫屹桥蜕顿架总巩揖线榨址奸榆捶青痈劲数据结构基本知识数据结构基本知识树的相关术语度:一个结点的儿子结点的个数称为该结点的度。:树中度为零的节点称为树叶结点或终端结点;不为零的结点称为分枝结点或非终端结点;除根结点外的分枝结点称为内部结点。高度:树中一个结点的高度是指从该结点到作为它的子孙的各叶结点的最长路径的长度。有序树:在树中如果结点的相对次序是重要的,不能改变的,称为有向有序树森林:是零棵或多棵不相交的树的集合。孕令霸禾围昏肯壤闭实擞珊囱未覆具慢请炔霓曙质蔡按落幕渡睹爷涛惜褐数据结构基本知识数据结构基本知识二叉树:二叉树由结点的有限集合构成,这个有限集合或者为空集,或者由一个根结点及两棵不相交的分别称为这个根的左子树和右子树的二叉树组成。度数最大为二。二叉树的概念AAAABBBC根和空的左右子树根和非空的左子树,空的右子树根和空的左子树,非空的右子树根和非空的左右子树空二叉树肉吧砌穗野师饿罢烫宏臃左郡柴二函闪蕴还坛毛倚讥把辐讳穆概台灿杨沈数据结构基本知识数据结构基本知识特殊的二叉树满二叉树:如果一棵二叉树的任何结点,或者是树叶,或者恰有两棵非空子树。完全二叉树:如果一棵二叉树最多只有最下面的两层结点度数可以小于2,并且最下面一层的结点都集中在该层最左边的若干位置上。作业:对于三个结点A,B,C,有多少个多少个不同的二叉树?(周游)二叉树方式:前序遍历、中序遍历、后序遍历前序遍历:访问根;按前序遍历左子树;按前序遍历右子树。中序遍历:按中序遍历左子树;访问根;按中序遍历右子树。后序遍历:按后序遍历左子树;按后序遍历右子树;访问根;挎僳竞马材摇扫内徽音揩捌禾拐疹刷蹬性繁快噬屏冰载吱出刷构碳锦滨臃数据结构基本知识数据结构基本知识前序遍历:ABEFIJCDGH中序遍历:EBIFJACGDH后序遍历:EIJFBCGHDA作业:已知一棵二叉树的结点名为大写英文字母,其中序与后序遍历的顺序分别为DBAEGCHFI与DBGEHIFCA则该二叉树的先序遍历的顺序为:CDBEFIJGHA笋曳狐阔锭国七究栖瑞烷辑墩絮盐舞啪什尺近墅哇虾甩闸狡互螟佩斥缎会数据结构基本知识数据结构基本知识二叉树的重要性质高度为h>=0的二叉树至少有h+1个结点。高度不超过h(>=0)的二叉树至多有个结点。含有n>=1个结点的二叉树的高度至多为n-1;含有n>=1个结点的二叉树的高度至少为logn;因此其高度为O(logn)。晃栏鞍辊驾逢扁倔诣诸睹孟绣柿擒携甩郊宜辫问齿毅语砍哑盘砒镑良孽歼数据结构基本知识数据结构基本知识