链表:
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便插入和删除操作。
树:
树(tree)是包含n(n>0)个结点的有穷集合,其中:
(1)每个元素称为结点(node);
(2)有一个特定的结点被称为根结点或树根(root)。
(3)除根结点之外的其余数据元素被分为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的子树。  空集合也是树,称为空树。空树中没有结点。
树的种类:
无序树:树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树;  有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树;  二叉树:每个节点最多含有两个子树的树称为二叉树;  完全二叉树  满二叉树  霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树
二叉树遍历:
遍历方案
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
⑴访问结点本身(N),
⑵遍历该结点的左子树(L),
⑶遍历该结点的右子树(R)。
以上三种操作有六种执行次序:  NLR、LNR、LRN、NRL、RNL、RLN。
注意:  前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。
三种遍历的命名
根据访问结点操作发生位置命名:
① NLR:前序遍历(PreorderTraversal亦称(先序遍历))
——访问根结点的操作发生在遍历其左右子树之前。
② LNR:中序遍历(InorderTraversal)
——访问根结点的操作发生在遍历其左右子树之中(间)。
③ LRN:后序遍历(PostorderTraversal)
——访问根结点的操作发生在遍历其左右子树之后。
注意: 由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。
NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
遍历算法
1.中序遍历的递归算法定义:  若二叉树非空,则依次执行如下操作:
⑴遍历左子树;
⑵访问根结点;
⑶遍历右子树。
2.先序遍历的递归算法定义:  若二叉树非空,则依次执行如下操作:
⑴ 访问根结点;
⑵ 遍历左子树;
⑶ 遍历右子树。
3.后序遍历得递归算法定义:  若二叉树非空,则依次执行如下操作:
⑴遍历左子树;
⑵遍历右子树;
⑶访问根结点。
4.层次遍历
斐波那契数:
首先介绍斐波那契数列,斐波那契数列的排列是:1,1,2,3,5,8,13,21,34,55,89,144……  依次类推下去,你会发现,它后一个数等于前面两个数的和。在这个数列中的数字,就被称为斐波那契数。2是第3个斐波那契数。这个级数与大自然植物的关系极为密切。几乎所有花朵的花瓣数都来自这个级数中的一项数字:菠萝表皮方块形鳞苞形成两组旋向相反的螺线,它们的条数必须是这个级数中紧邻的两个数字(如左旋8行,右旋13行);还有向日葵花盘……倘若两组螺线条数完全相同,岂不更加严格对称?可大自然偏不!直到最近的1993年,人们才对这个古老而重要的级数给出真正满意的解释:此级数中任何相邻的两个数,次第相除,其比率都最为接近0.618034……这个值,它的极限就是所谓的"黄金分割数"。
它有一个递推关系,
 f(1)=1
 f(2)=1
 f(n)=f(n-1)+f(n-2),其中n>=2
 3f(n)=f(n+2)+f(n-2)
当前位置: 首页 > 技术研究 > 其他 > 链表、树、斐波那契数

链表、树、斐波那契数

发布于:2015-4-5 其他 0条评论 1,295 views
链表:
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,链表比较方便插入和删除操作。
树:
树(tree)是包含n(n>0)个结点的有穷集合,其中:
(1)每个元素称为结点(node);
(2)有一个特定的结点被称为根结点或树根(root)。
(3)除根结点之外的其余数据元素被分为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的子树。  空集合也是树,称为空树。空树中没有结点。
树的种类:
无序树:树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树;  有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树;  二叉树:每个节点最多含有两个子树的树称为二叉树;  完全二叉树  满二叉树  霍夫曼树:带权路径最短的二叉树称为哈夫曼树或最优二叉树
二叉树遍历:
遍历方案
从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:
⑴访问结点本身(N),
⑵遍历该结点的左子树(L),
⑶遍历该结点的右子树(R)。
以上三种操作有六种执行次序:  NLR、LNR、LRN、NRL、RNL、RLN。
注意:  前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。
三种遍历的命名
根据访问结点操作发生位置命名:
① NLR:前序遍历(PreorderTraversal亦称(先序遍历))
——访问根结点的操作发生在遍历其左右子树之前。
② LNR:中序遍历(InorderTraversal)
——访问根结点的操作发生在遍历其左右子树之中(间)。
③ LRN:后序遍历(PostorderTraversal)
——访问根结点的操作发生在遍历其左右子树之后。
注意: 由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。
NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
遍历算法
1.中序遍历的递归算法定义:  若二叉树非空,则依次执行如下操作:
⑴遍历左子树;
⑵访问根结点;
⑶遍历右子树。
2.先序遍历的递归算法定义:  若二叉树非空,则依次执行如下操作:
⑴ 访问根结点;
⑵ 遍历左子树;
⑶ 遍历右子树。
3.后序遍历得递归算法定义:  若二叉树非空,则依次执行如下操作:
⑴遍历左子树;
⑵遍历右子树;
⑶访问根结点。
4.层次遍历
斐波那契数:
首先介绍斐波那契数列,斐波那契数列的排列是:1,1,2,3,5,8,13,21,34,55,89,144……  依次类推下去,你会发现,它后一个数等于前面两个数的和。在这个数列中的数字,就被称为斐波那契数。2是第3个斐波那契数。这个级数与大自然植物的关系极为密切。几乎所有花朵的花瓣数都来自这个级数中的一项数字:菠萝表皮方块形鳞苞形成两组旋向相反的螺线,它们的条数必须是这个级数中紧邻的两个数字(如左旋8行,右旋13行);还有向日葵花盘……倘若两组螺线条数完全相同,岂不更加严格对称?可大自然偏不!直到最近的1993年,人们才对这个古老而重要的级数给出真正满意的解释:此级数中任何相邻的两个数,次第相除,其比率都最为接近0.618034……这个值,它的极限就是所谓的"黄金分割数"。
它有一个递推关系,
 f(1)=1
 f(2)=1
 f(n)=f(n-1)+f(n-2),其中n>=2
 3f(n)=f(n+2)+f(n-2)

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据