线索二叉树的遍历

二叉树遍历是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问.访问结点所做的操作依赖于具体的应用问 题. 遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础. 除了先序遍历.中序遍历.后序遍历外,还可以对二叉树进行层序遍历.设二叉树的根节点所在层数为:层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历.

层次遍历应该没有递归算法递归实际就是一种深度优先的算法而层次遍历实际是广度优先的遍历算法,所以递归不适用比如假设有递归算法,现遍历i层的开始,对i层第一个元素遍历后需调用递归函数遍历其孩子,递归调用完成后才继续遍历i层第二个元素,这样就不是层次遍历了.

建立线索二叉树,或者说对二叉树线索化,实质上就是遍历一棵二叉树.在遍历过程中,访问结点的操作是检查当前的左,右指针域是否为空,将它们改为指向前驱结点或后续结点的线索.为实现这一过程,设指针始终指向刚刚访问的结点,即若指针指向当前结点,则指针指向它的前驱,以便设线索. 另外,在对一颗二叉树加线索时,必须首先申请一个头结点,建立头结点与二叉树的根结点的指向关系,对二叉树线索化后,还需建立最后一个结点与头结点之间的线索.

遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次.由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示. 二叉树有三种遍历方法,先序遍历,首先访问根,再先序遍历左子树,最后先序遍历右子树.中序遍历,首先中序遍历左子树,再访问根,最后遍历右子树.后序遍历,首先后序遍历左子树,再后序遍历右子树,最后访问根.

二叉树是十分重要的数据结构,主要用来存放数据,并且方便查找等操作,在很多地方有广泛的应用.二叉树有很多种类,比如线索二叉树,二叉排序树,平衡二叉树等.二叉树的建立采用的是递归的思想,给定一个指向根节点的指针,然后递归调用ceate函数,自动生成一个二叉树.

1.数据:所有能被计算机识别.存储和处理的符号的集合. 2.数据元素:是数据的基本单位,具有完整确定的实际意义. 3.数据对象:具有相同性质的数据元素的集合,是数据的一个子集. 4.数据结构:是相互之间存在一种或多种特定关系的数据元素的集合. 5.数据类型:是一个值的集合和定义在该值上的一组操作的总称. 6.抽象数据类型:由用户定义的一个数学模型与定义在该模型上的一组操作,它由基本的数据类型构成. 7.算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,是一系列输入转换为输出的计算步骤.

<数据结构>主要学习线性表.栈的队列和数组.树与二叉树.图.详细内容如下: 1.线性表:线性表的定义和基本操作.线性表的实现.顺序存储结构: 2.栈的队列和数组:栈和队列的基本概念.栈和队列的顺序存储结构.栈和队列的链式存储结构.栈和队列的应用.特殊矩阵的压缩存储: 3.树与二叉树:树的概念.二叉树的定义及其主要特征.二叉树的顺序存储结构和链式存储结构.线索二叉树的基本概念和构造: 4.图:图的概念.图的存储及基本操作.图的基本应用及其复杂度分析.

后序遍历是二叉树遍历的一种,也叫做后根遍历.后序周游,可记做左右根.后序遍历有递归算法和非递归算法两种.在二叉树中,先左后右再根.巧记:左右根.序遍历的非递归算法是三种顺序中最复杂的,原因在于,后序遍历是先访问左.右子树,再访问根节点,而在非递归算法中,利用栈回退到时,并不知道是从左子树回退到根节点,还是从右子树回退到根节点,如果从左子树回退到根节点,此时就应该去访问右子树,而如果从右子树回退到根节点,此时就应该访问根节点.所以相比前序和后序,必须得在压栈时添加信息,以便在退栈时可以知道是从左子

二叉树深度就是层数.二叉树结点的度数指该结点所含子树的个数,二叉树结点子树个数最多的那个结点的度为二叉树的度.二叉树的根结点所在的层数为1,根结点的孩子结点所在的层数为2,以此下去.深度是指所有结点中最深的结点所在的层数. 二叉树是一个连通的无环图,并且每一个顶点的度不大于3.有根二叉树还要满足根结点的度不大于2.有了根结点之后,每个顶点定义了唯一的父结点,和最多2个子结点.然而,没有足够的信息来区分左结点和右结点.如果不考虑连通性,允许图中有多个连通分量,这样的结构叫做森林.遍历是对树的一种最