程序员日记|程序员日记记录专业的技术知识

二叉树的遍历，深度优先（前序，中序，后序），广度优先（层序）-4.5

程序员日记 2019-08-08

数据结构与常用算法 >> 树

定义二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树的所有结点，使得每个结点被访问一次且仅被访问一次。遍历方法-深度优先1.前序遍历若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，然后再前序遍历右子树如图2.中序遍历若二叉树为空，则空操作返回，否则从根结点开始（不是先访问根结点），中序遍历左子树，然后访问根结点，然后中序遍历右子树如图3.后序遍历若二叉树为空，则空操作返回，否则从左到右先叶子后结点的顺序遍历访问左右子树，最后访问根结点。如图遍历方法-广度优先1.层序遍历...

二叉树的存储结构-4.4

程序员日记 2019-08-08

数据结构与常用算法 >> 树

二叉树顺序存储结构二叉树由于其特殊性，使用顺序存储结构也能实现。1.一颗完全二叉树的顺序存储结构如图将其存入数组中是这样的2.一般二叉树的顺序存储结构我们把不存在的节点实则之为^;如图将其存入数组中是这样的3.极端情况，右斜树如图将其存入数组中的情况是这样的上面的例子我们可以非常清楚，非完全二叉树，需要分配多余的存储空间，这样是浪费的，所以一般来说顺序存储结构仅适用于完全二叉树二叉链表二叉树每个结点最多有两个孩子，所以可以为它设计一个数据域和两个数据指针分别指向左孩子和右孩子，我们称这样链表叫做...

二叉树的定义-4.3

程序员日记 2019-08-08

数据结构与常用算法 >> 树

定义二叉树（BinaryTree）是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。特点1.每个结点最多又两颗子树，二叉树不存在度大于2的结点。2.左子树和右子树是有顺序的，不能任意颠倒3.即时树中只有有一个子树，也要区分是左子树还是右子树五种基本形态1.空二叉树2.只有一个根结点3.根结点只有左子树4.根结点只有右子树5.根结点既有左子树又有右子树特殊二叉树1.斜树所有结点都只有左子树的二叉树...

树的几种存储结构-4.2

程序员日记 2019-08-08

数据结构与常用算法 >> 树

示例树1.双亲表示法在每个结点中，附设一个双亲指示器，指示其双亲结点到链表中的位置，附设一个长子指示器，指示同一个双亲下最左侧结点的位置，附设一个右兄弟指示器，指示该结点右侧兄弟位置的节点。双亲表示法实现/***双亲表示法*///结点结构classPTNode{public$data;//结点数据public$parent;//双亲位置public$firstChild;//长子位置（最左边子结点的位置）public$rightsib;//右边兄弟的位置}//树结构classPTree{publ...

树的基础概念-4.1

程序员日记 2019-08-07

数据结构与常用算法 >> 树

基础定义树（tree）是n(n>=0)个结点的有限集。空树n=0的树称为空树任意一颗非空树中1.有且仅有一个特定称为根（ROOT）的结点2.当n>1时，其余结点可以分为m(m>0)个互不相交的有限集T1，T2，...，Tm，其中每一个集合本身又是一棵树，并且称为根的子树如图树的定义需要注意1.n>0时，根结点是唯一的，不可能存在多个根结点。2.m>0时，子树的个数没有限制，但他们一定是互不相交的如图，这些不符合树的定义结点分类结点的度结点拥有的子树数称为结点的度叶节...