数据结构基本知识二叉树遍历.ppt

该【数据结构基本知识二叉树遍历 】是由【1485173816】上传分享，文档一共【45】页，该文档可以免费在线阅读，需要了解更多关于【数据结构基本知识二叉树遍历 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构基本知识二叉树遍历树()是n(n?0)个结点的有限集T,其中:有且仅有一个特定的结点,称为树的根()当n>1时,其余结点可分为m(m>0)个互不相交的有限集T12,……,其中每一个集合本身又是一棵树,称为根的子树()。回顾上节课主要内容二叉树是n(n?0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。顺序存储结构按满二叉树的结点层次编号,依次存放二叉树中的数据元素链式存储结构使用二叉链表存储,通过指针指向左右子树。;{;*,*},*;;lchilddatarchildACBED树ABCDE二叉树A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^对应存储存储解释解释遍历——按一定规律走遍树的各个结点,且使每一结点仅被访问一次,即找一个完整而有规律的走法,以得到树中所有结点的一个线性排列。常用方法先序遍历:先访问根结点,然后分别先序遍历左子树、先序遍历右子树。中序遍历:先中序遍历左子树,然后访问根结点,最后中序遍历右子树。后序遍历:先后序遍历左、后序遍历右子树,(n?0)个结点的有限集,它或为空树(0),或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成。ADBC根左右A根左右根左右>B>>D>>C根左右先序遍历序列:ABDC先序遍历:ABDC先序遍历:算法过程描述如下:,则返回①访问根结点②先序遍历左子树③先序遍历右子树(T){(){("%3c">);(>);(>);}}{;*,*},*;1.(T)2.{()3.{("%3c">);4.(>L);5.(>R);6.}7.}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列:ABDC例:对如下二叉树进行前序遍历的结果为ABDCEFFCADEGBABDECFFCADBEG左根右B左根右左根右>A>>D>>C左根右中序遍历序列:BDAC中序遍历:ADBCBDAC