98数据结构.第6章 树和二叉树-第2页
上亿文档资料，等你来发现
98数据结构.第6章 树和二叉树-2
所1999一、3(6分）】；A．结点数B．叶结点数C．非叶结点数D．度为2的；键字的有序表；F．需要对n个关键字进行动态插入G．需要n个关键；任何前提；62．下述编码中哪一个不是前缀码（）；A．（00，01，10，11）B．（0，1，00；000，001）；63．下面几个符号串编码集合中，不是前缀编码的是；A．{0,10,110,1111}B．{11,1；C
　所1999一、3 (6分）】A．结点数
B．叶结点数
C．非叶结点数
D．度为2的结点数
E．需要一张n个关键字的有序表F．需要对n个关键字进行动态插入
G．需要n个关键字的查找概率表
H．不需要任何前提62．下述编码中哪一个不是前缀码（
）。【中科院计算所 2000 一、2 （2分）】A．（00，01，10，11）
B．（0，1，00，11）
C．（0，10，110，111）
D．（1，01，000，001）63．下面几个符号串编码集合中，不是前缀编码的是（
）。A．{0,10,110,1111}
B．{11,10,001,101,0001}C．{00,010,}D．{b,c,aa,ac,aba,abb,abc}
【西安电子科技大学2001 应用 一、6（2分）】64. 当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组 A[l..n]中时，数组中第i个结点的左孩子为（
）【南京理工大学 1999一、18(2分）】A．A[2i](2i=&n)
B. A[2i+1](2i+1=& n)
D．无法确定65. 一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（
）A．A[2i](2i&=n)
B．A[2i+1](2i+1&=n)
D．条件不充分，无法确定【南京理工大学2000 一、4(1.5分）】66．从下列有关树的叙述中,选出5条正确的叙述(共5分) （
）A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。k-1B．当K≥1时高度为K的二叉树至多有2个结点。C．用树的前序周游和中序周游可以导出树的后序周游。D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。E．将一棵树转换成二叉树后,根结点没有左子树。F．一棵含有N个结点的完全二叉树,它的高度是?LOG2N?+1。G．在二叉树中插入结点,该二叉树便不再是二叉树。H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。 I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。J．用一维数组存储二叉树时,总是以前序周游存储结点。【山东工业大学 1995 三、 (5分)】 二、判断题1. 二叉树是度为2的有序树。【长沙铁道学院1997一、3(1分)】【中科院软件所1997一、9(1分)】2. 完全二叉树一定存在度为1的结点。【青岛大学 2002 一、4 （1分）】3. 对于有N个结点的二叉树，其高度为log2n。【上海海运学院 1998 一、6 （1分）】k4．深度为K的二叉树中结点总数≤2-1。【南京航空航天大学 1995 五、1 （1分）】5. 二叉树以后序遍历序列与前序遍历序列反映的同样的信息(他们反映的信息不独立）。【华南理工大学2002一、7 (1分）】6. 二叉树的遍历结果不是唯一的.【南京理工大学 1997 二、8 （2分）】7. 二叉树的遍历只是为了在应用中找到一种线性次序。【青岛大学 2001 四、4 （1分）】8. 树可用投影法进行中序遍历。 【青岛大学 2002 一、6 （1分）】9. 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。【上海海运学院 1995 一、4 （1分）】10. 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。【上海海运学院 1995 一、6 （1分）】11. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。【上海海运学院 1996 一、6 （1分）】12．对一棵二叉树进行层次遍历时，应借助于一个栈。【南京航空航天大学 1995 五、3 （1分）】13．用树的前序遍历和中序遍历可以导出树的后序遍历。【北京邮电大学 1999 二、3 （2分）】14．采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。【北京邮电大学2000一、2(1分）】15. 用一维数组存储二叉树时，总是以前序遍历顺序存储结点。【上海海运学院 1995 一、8 （1分）】16． 中序遍历二叉链存储的二叉树时，一般要用堆栈；中序遍历检索二叉树时，也必须使用堆栈。【上海海运学院1998一、7(1分）】17．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列【中科院软件所 1999 六、1-1 （2分）】18. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。【 长沙铁道学院 1998 一、2 (1分)】19．任何二叉树的后序线索树进行后序遍历时都必须用栈。【西安交通大学 1996 二、2 ( 3分) 】20．任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。【西安交通大学 1996 二、1 (3分)】21．由一棵二叉树的前序序列和后序序列可以唯一确定它。【中科院软件所 1997 一、3 （1分）】22．完全二叉树中，若一个结点没有左孩子，则它必是树叶。【东南大学 2001一、1-8（1分）】【中科院软件所1997一、2（1分）】【山东大学2001一、4 (1分)】23. 二叉树只能用二叉链表表示。【南京理工大学 1997 二、6 （2分）】24. 一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i(2i& n)，右儿子是2i+1（2i+1&n）。【南京理工大学 1997 二、11 （2分）】25. 给定一棵树，可以找到唯一的一棵二叉树与之对应。【青岛大学 2001 一、5 （1分）】26. 一棵树中的叶子数一定等于与其对应的二叉树的叶子数。【青岛大学 2002 一、5 （1分）】27. 用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。【上海海运学院1996一.5(1分）】28. 二叉树中每个结点至多有两个子结点,而对一般树则无此限制.因此,二叉树是树的特殊情形.【上海海运学院1997一.5(1分）】29．树形结构中元素之间存在一个对多个的关系。【燕山大学 1998 二、1 （2分）】i-130．在二叉树的第i层上至少有2个结点(i&=1)。【燕山大学 1998 二、3 （2分）】31．必须把一般树转换成二叉树后才能进行存储。【南京航空航天大学 1997 一、4 （1分）】32．完全二叉树的存储结构通常采用顺序存储结构。【南京航空航天大学 1996 六、3 （1分）】33．将一棵树转成二叉树，根结点没有左子树；【北京邮电大学 1999 二、2 （2分）】34．在二叉树中插入结点，则此二叉树便不再是二叉树了。【北京邮电大学 2000 一、5 （1分）】35．二叉树是一般树的特殊情形。【北京邮电大学 2000 一、9 （1分）
2002 一、6 （1分）】36．树与二叉树是两种不同的树型结构。【东南大学 2001 一、1-7 （1分）】37. 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子【合肥工业大学 2001 二、5 （1分）】38．在任意一棵非空二叉排序树，删除某结点后又将其插入，则所得二叉排序树与删除前原二叉排序树相同。【中科院软件所 1997 一、7 （1分）】39．度为二的树就是二叉树。【大连海事大学 2001 一、7 (1分)】k-240．深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 ?2?+1。【东北大学 1997 二、3 (2分)】41.下面二叉树的定义只有一个是正确的，请在正确的地方画“√”。（1）它是由一个根和两株互不相交的、称为左子树和右子树的二叉树组成。i-1（2）（a）在一株二叉树的级i上，最大结点数是2（i≥1）k-1（b）在一棵深度为k的二叉树中，最大结点数是2+1（k≥1）。（3）二叉树是结点的集合，满足如下条件：（a）它或者是空集；（b）或者是由一个根和两个互不相交的、称为左子树和右子树的二叉树组成。【中科院自动化所1995一、2（6分）】42. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。【合肥工业大学 2000 二、5 （1分）】43. 线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。【上海海运学院
一、7（1分）】44. 二叉树中序线索化后，不存在空指针域。【青岛大学 2000 四、3 （1分）】45．霍夫曼树的结点个数不能是偶数。【北京邮电大学 2000 一、6 （1分）】46. 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。【合肥工业大学2000二、4 (1分)】47. 哈夫曼树无左右子树之分。【青岛大学 2000 四、8 （1分）】48．当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。【南京航空航天大学 1995 五、6 （1分）】49．哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。【北京邮电大学 1999 二、5 （2分）】50. 用链表（llink-rlink）存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1个空指针。(
)【上海海运学院 1999 一、6（1分）】 三、填空题1．二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。【燕山大学 1998 一、5 （3分）】2．树在计算机内的表示方式有_(1)__，_(2)__，_(3)__。【哈尔滨工业大学 2000 二、4 (3分)】3．在二叉树中，指针p所指结点为叶子结点的条件是______。【合肥工业大学1999 三、7（2分）】4．中缀式a+b*3+4*（c-d）对应的前缀式为__(1)_，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(2)__。【西南交通大学 2000 一、6】5．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的____。【燕山大学1998一、9(1分)】6．具有256个结点的完全二叉树的深度为______。【燕山大学 1998 一、4 （1分）】7．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。【厦门大学 2000 六、2 （16%/3分）】8．深度为k的完全二叉树至少有___(1)____个结点，至多有___(2)____个结点。【厦门大学 2001 一、4 （14%/5分）】 【南京理工大学 1999 二、5 （4分）】9．深度为H 的完全二叉树至少有_(1)__个结点；至多有_(2)__个结点；H和结点总数N之间的关系是 (3)__。【中科院计算所1998 一、3（3分）1999 二、4（3分）】【中国科技大学 1998 一、3(4分）】10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。【厦门大学 2002 六、3 （4分）】11．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是______。【合肥工业大学 2000 三、6 （2分）】12．一棵有n个结点的满二叉树有__(1)_个度为1的结点、有__(2)_个分支 （非 终端）结点和__(3)_个叶子，该满二叉树的深度为_(4)__。【华中理工大学 2000 一、6 （3分））13．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是______。【北方交通大学 2001 二、1】14．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______【北方交通大学 2001 二、6】【南京理工大学 1999 二、4 （2分）】15．设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为______,最小结点数为______。【北京大学 1997 一、1 （4分）】16．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为______。【 长沙铁道学院 1997 二、3 (2分)】17．高度为K的完全二叉树至少有______个叶子结点。【合肥工业大学 1999 二、6（2分）】18．高度为8的完全二叉树至少有______个叶子结点。【合肥工业大学 2001 三、6（2分）】19．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。【厦门大学 2002 六、4（4分）】20．一个有2001个结点的完全二叉树的高度为______。【南京理工大学 1997 三、2（1分）】21．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。【南京理工大学 2000 二、9（3分）】22．一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是__(1)_；编号是i的结点所在的层次号是_(2)__（根所在的层次号规定为1层）。【南京理工大学 2001 二、2（2分）】23．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。【南京理工大学 2001 二、3（2分）】24．如果结点A有 3个兄弟，而且B是A的双亲，则B的度是______。【西安电子科技大学1999软件 一、4（2分）】25．高度为h的2-3树中叶子结点的数目至多为______。【西安电子科技大学1999软件 一、6（2分）】26．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为______。【北京轻工业学院 2000 一、3 (2分)】27．设一棵完全二叉树叶子结点数为k,最后一层结点数&2，则该二叉树的高度为______。【北京科技大学 1998 一、3】28．对于一个具有n个结点的二元树，当它为一棵_(1)_二元树时具有最小高度，当它为一棵_(2)_时，具有最大高度。【哈尔滨工业大学 2001 一、3 (2分)】29．具有N个结点的二叉树，采用二叉链表存储，共有______个空链域。【重庆大学 2000 一、8】30．8层完全二叉树至少有______个结点，拥有100个结点的完全二叉树的最大层数为______。【西南交通大学 2000 一、1】31．含4个度为2的结点和5个叶子结点的二叉树，可有______个度为1的结点。【北京工业大学 2001 一、6 (2分)】32．一棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为______。【山东大学 2001 三、2 (2分)】33． n（n大于1）个结点的各棵树中，其深度最小的那棵树的深度是_(1)__。它共有_(2)__个叶子结点和_(3)__个非叶子结点，其中深度最大的那棵树的深度是_(4)__，它共有_(5)__个叶子结点和_(6)__个非叶子结点。【山东大学 2001 三、7 (2分)】34． 每一棵树都能唯一的转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，对称序列是FEBGCHD，则它的后序序列是_(1)__。设上述二叉树是由某棵树转换而成，则该树的先根次序序列是_(2)__。【山东工业大学 1997 二、 (6分)】35．先根次序周游树林正好等同于按_(1)__周游对应的二叉树，后根次序周游树林正好等同于按__(2)_周游对应的二叉树。【山东工业大学 1999 二、1 （4分）】36．二叉树结点的对称序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E,则该二叉树结点的前序序列为_(1)__,则该二叉树对应的树林包括_(2)__棵树。【北京大学 1997 一、2 （4分）】37．二叉树的先序序列和中序序列相同的条件是______。【合肥工业大学 2000 三、7（2分）】38．已知一棵二叉树的前序序列为abdecfhg,中序序列为dbeahfcg，则该二叉树的根为_(1)__，左子树中有_(2)__， 右子树中有_(3)__。【南京理工大学 1996 二、1（6分）】39．设二叉树中每个结点均用一个字母表示，若一个结点的左子树或右子树为空，用 ．表示，现前序遍历二叉树，访问的结点的序列为ABD.G...CE.H..F．．，则中序遍历二叉树时，访问的结点序列为_(1)__;后序遍历二叉树时，访问的结点序列为_(2)__。【南京理工大学 1999 二、3（4分）】40．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是____。【青岛大学2000 六、3(2分）】41．现有按中序遍历二叉树的结果为abc，问有_(1)__种不同的二叉树可以得到这一遍历结包含各类专业文献、生活休闲娱乐、文学作品欣赏、中学教育、外语学习资料、行业资料、幼儿教育、小学教育、各类资格考试、高等教育、专业论文、应用写作文书、98数据结构.第6章 树和二叉树等内容。　
　　【】　
您可在本站搜索以下内容：
　 数据结构复习资料 第六章 树和二叉树_工学_高等教育_教育专区。数据结构复习资料第六章 树和二叉树 第六章 树和二叉树 掌握二叉树的概念及基本性质; 重点:...
　 第六章树和二叉树习题_数据结构_工学_高等教育_教育专区。习题六 树和二叉树一、单项选择题 1. 以下说法错误的是 ( ) A.树形结构的特点是一个结点可以有多...
s　7、树和二叉树的两个主要差别是(二叉树是有序树)和(二叉树的度最大为 2) 。 8、从概念上讲,树与二叉树是两种不同的数据结构,将树转化成二叉树的基本目的...
　(A)是一棵树;(B)是一棵二叉树; (C)是一棵树也是一棵二叉树;(D)既不是树也不是二叉树 (C)2.二叉树是非线性数据结构,所以。 (A)它不能用顺序存储...
　第6 章 树和二叉树一、单项选择题 1.树最适合用来表示___。 A.有序数据元素 C.元素之间具有分支层次关系的数据 B.无序数据元素 D.元素之间无关系的数据 2...
　 第6章_数据结构习题题目及答案_树和二叉树_参考答案_计算机软件及应用_IT/计算机_专业资料。一、基础知识题 6.1 设树 T 的度为 4,其中度为 1,2,3 和 ...
　 第六章树和二叉树习题_数... 1s页 免费 数据结构习题与答案--树... 6...7、 1、 先序序列和中序序列相同:空二叉树或没有左子树的二叉树。 2、中...
　 《数据结构》习题集:第6章 树和二叉树_工学_高等教育_教育专区。数据结构课后练习题 第 6 章 树和二叉树 第 6 章 树和二叉树一、 选择题 1. 有一“...
赞助商链接
别人正在看什么？
赞助商链接28728人阅读
======================================================================================================
& & &&& &在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为，出度为2的结点数为，则=+
& & &&& &二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
& & &&& && & &&& &(1)空二叉树——(a)；&&
& & &&& && & &&& &(2)只有一个根结点的二叉树——(b)；
& & &&& && & &&& &(3)只有左子树——(c)；
& & &&& && & &&& &(4)只有右子树——(d)；
& & &&& && & &&& &(5)完全二叉树——(e)
& & &&&&&注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
& & &&& &(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
& & &&& &(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
& & &&& &(3)深度——二叉树的层数，就是高度。
& & &&& &(1) 在二叉树中，第i层的结点总数不超过2^(i-1)；
& & &&& &(2) 深度为h的二叉树最多有2^h-1个结点(h&=1)，最少有h个结点；
& & &&& &(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
& & &&& &(4) 具有n个结点的完全二叉树的深度为int（log2n）+1
& & &&& &(5)有N个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：
& & &&& && & &&& &若I为结点编号则 如果I&1，则其父结点的编号为I/2；
& & &&& && & &&& &如果2*I&=N，则其左儿子（即左子树的根结点）的编号为2*I；若2*I&N，则无左儿子；
& & &&& && & &&& &如果2*I+1&=N，则其右儿子的结点编号为2*I+1；若2*I+1&N，则无右儿子。
& & &&& &(6)给定N个节点，能构成h(N)种不同的二叉树。
& & &&& && & &&& &h(N)为卡特兰数的第N项。h(n)=C(n,2*n)/(n+1)。
& & && & (7)设有i个枝点，I为所有枝点的道路长度总和，J为叶的道路长度总和J=I+2i
1.完全二叉树 （Complete Binary Tree）
& & && &&若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。
2.满二叉树 （Full Binary Tree）
& & && &&一个高度为h的二叉树包含正是2^h-1元素称为满二叉树。
二叉树四种遍历
&&& & & 1.先序遍历 （仅二叉树）
& & & &&& & & &&指先访问根，然后访问孩子的遍历方式
& & & & & & & &
非递归实现
& & & & & & & &&利用栈实现，先取根节点，处理节点，然后依次遍历左节点，遇到有右节点压入栈，向左走到尽头。然后从栈中取出右节点，处理右子树。
/*** PreOrderTraversal
* @param AL_ListSeq&T&& listOrder &OUT&
* @return BOOL
* @note Pre-order traversal
* @attention
template&typename T& BOOL
AL_TreeBinSeq&T&::PreOrderTraversal(AL_ListSeq&T&& listOrder) const
if (NULL == m_pRootNode) {
return FALSE;
listOrder.Clear();
//Recursion Traversal
PreOrderTraversal(m_pRootNode, listOrder);
return TRUE;
//Not Recursion Traversal
AL_StackSeq&AL_TreeNodeBinSeq&T&*& cS
AL_TreeNodeBinSeq&T&* pTreeNode = m_pRootN
while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
while (NULL != pTreeNode) {
listOrder.InsertEnd(pTreeNode-&GetData());
if (NULL != pTreeNode-&GetChildRight()) {
//push the child right to stack
cStack.Push(pTreeNode-&GetChildRight());
pTreeNode = pTreeNode-&GetChildLeft();
if (TRUE == cStack.Pop(pTreeNode)) {
if (NULL == pTreeNode) {
return FALSE;
return FALSE;
return TRUE;
& & & & & & & & 递归实现
* PreOrderTraversal
* @param const AL_TreeNodeBinSeq&T&* pCurTreeNode &IN&
* @param AL_ListSeq&T&& listOrder &OUT&
* @return VOID
* @note Pre-order traversal
* @attention Recursion Traversal
template&typename T& VOID
AL_TreeBinSeq&T&::PreOrderTraversal(const AL_TreeNodeBinSeq&T&* pCurTreeNode, AL_ListSeq&T&& listOrder) const
if (NULL == pCurTreeNode) {
//Do Something with root
listOrder.InsertEnd(pCurTreeNode-&GetData());
if(NULL != pCurTreeNode-&GetChildLeft()) {
PreOrderTraversal(pCurTreeNode-&GetChildLeft(), listOrder);
if(NULL != pCurTreeNode-&GetChildRight()) {
PreOrderTraversal(pCurTreeNode-&GetChildRight(), listOrder);
& & & &&2.中序遍历（仅二叉树）
& & & &&& & & &&指先访问左（右）孩子，然后访问根，最后访问右（左）孩子的遍历方式
& & & & & & & & 非递归实现
& & & & & & & &&利用栈实现，先取根节点，然后依次遍历左节点，将左节点压入栈，向左走到尽头。然后从栈中取出左节点，处理节点。然后处理其右子树。
* InOrderTraversal
* @param AL_ListSeq&T&& listOrder &OUT&
* @return BOOL
* @note In-order traversal
* @attention
template&typename T& BOOL
AL_TreeBinSeq&T&::InOrderTraversal(AL_ListSeq&T&& listOrder) const
if (NULL == m_pRootNode) {
return FALSE;
listOrder.Clear();
//Recursion Traversal
InOrderTraversal(m_pRootNode, listOrder);
return TRUE;
//Not Recursion Traversal
AL_StackSeq&AL_TreeNodeBinSeq&T&*& cS
AL_TreeNodeBinSeq&T&* pTreeNode = m_pRootN
while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
while (NULL != pTreeNode) {
cStack.Push(pTreeNode);
pTreeNode = pTreeNode-&GetChildLeft();
if (TRUE == cStack.Pop(pTreeNode)) {
if (NULL !=
pTreeNode) {
listOrder.InsertEnd(pTreeNode-&GetData());
if (NULL != pTreeNode-&GetChildRight()){
//child right exist, push the node, and loop it's left child to push
pTreeNode = pTreeNode-&GetChildRight();
//to pop the node in the stack
pTreeNode = NULL;
return FALSE;
return FALSE;
return TRUE;
& & & & & & & & 递归实现
* InOrderTraversal
* @param const AL_TreeNodeBinSeq&T&* pCurTreeNode &IN&
* @param AL_ListSeq&T&& listOrder &OUT&
* @return VOID
* @note In-order traversal
* @attention Recursion Traversal
template&typename T& VOID
AL_TreeBinSeq&T&::InOrderTraversal(const AL_TreeNodeBinSeq&T&* pCurTreeNode, AL_ListSeq&T&& listOrder) const
if (NULL == pCurTreeNode) {
if(NULL != pCurTreeNode-&GetChildLeft()) {
InOrderTraversal(pCurTreeNode-&GetChildLeft(), listOrder);
//Do Something with root
listOrder.InsertEnd(pCurTreeNode-&GetData());
if(NULL != pCurTreeNode-&GetChildRight()) {
InOrderTraversal(pCurTreeNode-&GetChildRight(), listOrder);
& & &&&&3.后序遍历（仅二叉树）
& & & &&& & & &&指先访问孩子，然后访问根的遍历方式
& & & & & & & & 非递归实现
& & & & & & & &&利用栈实现，先取根节点，然后依次遍历左节点，将左节点压入栈，向左走到尽头。然后从栈中取出左节点，处理节点。处理其右节点，还需要记录已经使用过的节点，比较麻烦和复杂。大致思路如下：
1.找到最左边的子节点2.如果最左边的子节点有右节点，处理右节点（类似1）3.从栈里弹出节点处理3.当碰到左右节点都存在的节点时，需要进行记录了回归节点了。然后以当前节点的右子树进行处理4.碰到回归节点时，把当前的最后一个元素消除（因为后面还会回归到这个点的）。
* PostOrderTraversal
* @param AL_ListSeq&T&& listOrder &OUT&
* @return BOOL
* @note Post-order traversal
* @attention
template&typename T& BOOL
AL_TreeBinSeq&T&::PostOrderTraversal(AL_ListSeq&T&& listOrder) const
if (NULL == m_pRootNode) {
return FALSE;
listOrder.Clear();
//Recursion Traversal
PostOrderTraversal(m_pRootNode, listOrder);
return TRUE;
//Not Recursion Traversal
AL_StackSeq&AL_TreeNodeBinSeq&T&*& cS
AL_TreeNodeBinSeq&T&* pTreeNode = m_pRootN
AL_StackSeq&AL_TreeNodeBinSeq&T&*& cStackR
AL_TreeNodeBinSeq&T&* pTreeNodeReturn = NULL;
while (TRUE != cStack.IsEmpty() || NULL != pTreeNode) {
while (NULL != pTreeNode) {
cStack.Push(pTreeNode);
if (NULL != pTreeNode-&GetChildLeft()) {
pTreeNode = pTreeNode-&GetChildLeft();
//has not left child, get the right child
pTreeNode = pTreeNode-&GetChildRight();
if (TRUE == cStack.Pop(pTreeNode)) {
if (NULL !=
pTreeNode) {
listOrder.InsertEnd(pTreeNode-&GetData());
if (NULL != pTreeNode-&GetChildLeft() && NULL != pTreeNode-&GetChildRight()){
//child right exist
cStackReturn.Top(pTreeNodeReturn);
if (pTreeNodeReturn != pTreeNode) {
listOrder.RemoveAt(listOrder.Length()-1);
cStack.Push(pTreeNode);
cStackReturn.Push(pTreeNode);
pTreeNode = pTreeNode-&GetChildRight();
//to pop the node in the stack
cStackReturn.Pop(pTreeNodeReturn);
pTreeNode = NULL;
//to pop the node in the stack
pTreeNode = NULL;
return FALSE;
return FALSE;
return TRUE;
& & & & & & & & 递归实现
* PostOrderTraversal
* @param const AL_TreeNodeBinSeq&T&* pCurTreeNode &IN&
* @param AL_ListSeq&T&& listOrder &OUT&
* @return VOID
* @note Post-order traversal
* @attention Recursion Traversal
template&typename T& VOID
AL_TreeBinSeq&T&::PostOrderTraversal(const AL_TreeNodeBinSeq&T&* pCurTreeNode, AL_ListSeq&T&& listOrder) const
if (NULL == pCurTreeNode) {
if(NULL != pCurTreeNode-&GetChildLeft()) {
PostOrderTraversal(pCurTreeNode-&GetChildLeft(), listOrder);
if(NULL != pCurTreeNode-&GetChildRight()) {
PostOrderTraversal(pCurTreeNode-&GetChildRight(), listOrder);
//Do Something with root
listOrder.InsertEnd(pCurTreeNode-&GetData());
& & & &&4.层次遍历
& & & &&& & & &&一层一层的访问，所以一般用广度优先遍历。
& & & & & & & & 非递归实现
利用链表或者队列均可实现，先取根节点压入链表或者队列，依次从左往右体访问子节点，压入链表或者队列。直至处理完所有节点。
* LevelOrderTraversal
* @param AL_ListSeq&T&& listOrder &OUT&
* @return BOOL
* @note Level-order traversal
* @attention
template&typename T& BOOL
AL_TreeBinSeq&T&::LevelOrderTraversal(AL_ListSeq&T&& listOrder) const
if (TRUE == IsEmpty()) {
return FALSE;
if (NULL == m_pRootNode) {
return FALSE;
listOrder.Clear();
AL_ListSeq&AL_TreeNodeBinSeq&T&*& listNodeO
listNodeOrder.InsertEnd(m_pRootNode);
//loop the all node
DWORD dwNodeOrderLoop = 0x00;
AL_TreeNodeBinSeq&T&* pNodeOrderLoop = NULL;
AL_TreeNodeBinSeq&T&* pNodeOrderChild = NULL;
while (TRUE == listNodeOrder.Get(pNodeOrderLoop, dwNodeOrderLoop)) {
dwNodeOrderLoop++;
if (NULL != pNodeOrderLoop) {
listOrder.InsertEnd(pNodeOrderLoop-&GetData());
pNodeOrderChild = pNodeOrderLoop-&GetChildLeft();
if (NULL != pNodeOrderChild) {
queueOrder.Push(pNodeOrderChild);
pNodeOrderChild = pNodeOrderLoop-&GetChildRight();
if (NULL != pNodeOrderChild) {
queueOrder.Push(pNodeOrderChild);
return FALSE;
return TRUE;
AL_QueueSeq&AL_TreeNodeBinSeq&T&*& queueO
queueOrder.Push(m_pRootNode);
AL_TreeNodeBinSeq&T&* pNodeOrderLoop = NULL;
AL_TreeNodeBinSeq&T&* pNodeOrderChild = NULL;
while (FALSE == queueOrder.IsEmpty()) {
if (TRUE == queueOrder.Pop(pNodeOrderLoop)) {
if (NULL != pNodeOrderLoop) {
listOrder.InsertEnd(pNodeOrderLoop-&GetData());
pNodeOrderChild = pNodeOrderLoop-&GetChildLeft();
if (NULL != pNodeOrderChild) {
queueOrder.Push(pNodeOrderChild);
pNodeOrderChild = pNodeOrderLoop-&GetChildRight();
if (NULL != pNodeOrderChild) {
queueOrder.Push(pNodeOrderChild);
return FALSE;
return FALSE;
return TRUE;
& & & & & & & &&递归实现 （无）
======================================================================================================
& & & & 树（tree）是包含n（n&0）个结点的有穷集合，其中：
每个元素称为结点（node）；有一个特定的结点被称为根结点或树根（root）。除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1&=i&=m）本身也是一棵树，被称作原树的子树（subtree）。
& & & &&树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。
& & & &&我们可以形式地给出树的递归定义如下:
单个结点是一棵树，树根就是该结点本身。设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称n1,n2,..,nk为结点n的子树。空集合也是树，称为空树。空树中没有结点。
树的四种遍历
&&& & & 1.先序遍历 （仅二叉树）
& & & &&& & & &&指先访问根，然后访问孩子的遍历方式
& & & &&2.中序遍历（仅二叉树）
& & & &&& & & &&指先访问左（右）孩子，然后访问根，最后访问右（左）孩子的遍历方式
& & &&&&3.后序遍历（仅二叉树）
& & & &&& & & &&指先访问孩子，然后访问根的遍历方式
& & & &&4.层次遍历
& & & &&& & & &&一层一层的访问，所以一般用广度优先遍历。
======================================================================================================
& & & & 包括一个数据元素及若干个指向其它子树的分支；例如，A，B，C，D等。
在数据结构的图形表示中，对于数据集合中的每一个数据元素用中间标有元素值的方框表示，一般称之为数据结点，简称结点。
& & & & 在C语言中，链表中每一个元素称为“结点”，每个结点都应包括两个部分：一为用户需要用的实际数据；二为下一个结点的地址，即指针域和数据域。
& & & & 数据结构中的每一个数据结点对应于一个储存单元，这种储存单元称为储存结点，也可简称结点
树结点（树节点）：
树节点相关术语：
节点的度：一个节点含有的子树的个数称为该节点的度；叶节点或终端节点：度为0的节点称为叶节点；非终端节点或分支节点：度不为0的节点；双亲节点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点；孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；兄弟节点：具有相同父节点的节点互称为兄弟节点；节点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；堂兄弟节点：双亲在同一层的节点互为堂兄弟；节点的祖先：从根到该节点所经分支上的所有节点；子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
& & & & 根据树结点的相关定义，采用“双亲孩子表示法”。其属性如下：
//Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2,
//the friend class can use it directly
AL_TreeNodeSeq&T&*
//Parent position
AL_ListSeq&AL_TreeNodeSeq&T&*&
//All Child tree node
树的几种表示法
& & & & 在实际中，可使用多种形式的存储结构来表示树，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系。
& & & &&1．双亲表示法
& & & &&& & & &&由于树中的每个结点都有唯一的一个双亲结点，所以可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，每个结点含两个域，数据域存放结点本身信息，双亲域指示本结点的双亲结点在数组中位置。
& & & &&& & & &&
& & & &&2．孩子表示法
& & & &&& & & &&1.多重链表：每个结点有多个指针域，分别指向其子树的根
& & & & & & & & & & & &&1）结点同构：结点的指针个数相等，为树的度k,这样n个结点度为k的树必有n(k-1)+1个空链域.
& & & & & & & & & & & &&& & & & & & & & & & & &&
& & & &&& & & &&& & & &&2）结点不同构：结点指针个数不等，为该结点的度d
& & & & & & & & & & & &&& & & & & & & & & & & &&
& & & &&& & & &&2.孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表
& & & &&& & & &&
& & & &&3．双亲孩子表示法
& & & &&& & & &&1.双亲表示法，PARENT（T，x）可以在常量时间内完成，但是求结点的孩子时需要遍历整个结构。
& & & &&& & & &&2.孩子链表表示法，适于那些涉及孩子的操作，却不适于PARENT（T，x）操作。
& & & &&& & & &&3.将双亲表示法和孩子链表表示法合在一起，可以发挥以上两种存储结构的优势，称为带双亲的孩子链表表示法
& & & &&& & & &&
& & & &&4．双亲孩子兄弟表示法 （二叉树专用）
& & & &&& & & &&又称为二叉树表示法，以二叉链表作为树的存储结构。
& & & &&& & & &&& & & &&& & & &&
& & & &&& & & &&
顺序存储结构
& & & &&在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构.　
& & & &&顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如c/c++）的数组来描述的。
& & & &&顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。
& & &&&&优点：
& & & &&& & & &&随机存取表中元素。缺点：插入和删除操作需要移动元素。
& & & & 本代码默认list可以容纳的item数目为100个，用户可以自行设置item数目。当list饱和时，由于Tree是非线性结构，动态扩展内存相当麻烦。因此示例中的Demo及代码将不会动态扩展内存。
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
以后的笔记潇汀会尽量详细讲解一些相关知识的，希望大家继续关注我的博客。
本节笔记到这里就结束了。
潇汀一有时间就会把自己的学习心得，觉得比较好的知识点写出来和大家一起分享。
编程开发的路很长很长，非常希望能和大家一起交流，共同学习，共同进步。
如果文章中有什么疏漏的地方，也请大家指正。也希望大家可以多留言来和我探讨编程相关的问题。
最后，谢谢你们一直的支持~~~
& & & &C++完整个代码示例（代码在VS2005下测试可运行）
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1887801次
积分：10328
积分：10328
排名：第458名
原创：62篇
转载：38篇
评论：37条
文章：25篇
阅读：720015
阅读：178083
(2)(1)(6)(9)(17)(36)(2)(1)(3)(6)(3)(5)(9)}