数据结构、算法及应用
张宪超主编
科学出版社
1.
数据结构的基本概念知识
数据结构的逻辑结构由数据节点和连接两个节点的边组成。
数据节点的数据类型：整型，实数型，布尔型，字符型，指针数据类型
结构的分类：讨论逻辑结构（
K,R
）一般以关系集
R
为主：
线性结构，属性结构，图结构。
数据的存储结构：顺序存储，连接方法，索引方法，散列方法，分析一下这些不同的数据存储方式：顺序存储就是把一组节点放在一片地址相邻得存储单元，节点中的逻辑关系用存储单元之间的自然关系来表达。顺序存储是为使用整数编码访问数据节点提供了便利。
链接方法是在节点的存储结构中附加指针域来存储节点的逻辑关系。链接方法中的数据节点有两部分组成：数据域存放节点本身的数据，指针域存放指向其后继结点指针。该方法使用于经常需要增删节点而动态变化的数据结构。
索引方法：索引表中的存储空间是附加在节点存储空间之外的，每一个元素就是指向相应的数据节点的指针。索引适合于大数据量的时候，减少对数据的读取。
散列方式是一种索引的扩展，散列方法利用散列函数进行索引值的计算，然后通过索引技术求出该节点的指针地址。主要思想就是利用节点的关键字码来确定其存储的地址。散列函数应该尽量的将地址均匀分布。
2.
树结构的复习
2.1
树结构的定义
树是由
n
个节点组成的有限集合。在这个集合中没有直接前驱的节点称为根节点。当
n==0
的时候，是一个空树；当
n>0
的时候，所有的节点中仅有一个是根节点，其余的可以分成
m
个不相交的子集合，每一个子集合都是满足树的定义，称为根的子树。
关于树的一些名词解释：
结点：树结构中等个每一个元素称为一个结点，该结点包括该元素的值和该元素的逻辑关系信息。
边：使用
<m,n>
表示，结点
m
指向
n
双亲结点和孩子结点：
<m,n>
则
m
是
n
的双亲结点，也称为父节点，
n
是
m
的子节点。
兄弟结点：如果两个结点有共同的双亲结点，则两个节点称为兄弟结点。
叶子结点：没有孩子结点的称为叶子结点
结点的度：就是该结点的孩子结点的书目
树的度：树结构中的所有节点的度的最大值
结点的层次：结点的层次从根节点开始算起，即为
0
，然后往后面加
树的深度：是所有节点中的层次的最大值。空树是
0
树的高度：输的高度是树的深入加
1.
路径：从输的一个结点
n
到另一个结点
m
，如果存在一个有限集合
S
连接两个结点，则是
mn
之间的一个路径
有序树：如果树中的结点的所有子树之间存在确定的次序关系，则称该树是有序树，反之是无序树。
森林：有多个互不相交的数组成的集合
树的基本性质
树中结点的数目是所有节点的度数加
1
度为
m
的树，其第
i
层上之多有
m^i
个节点
2.2
二叉树：所有节点的度小于等于
2
的树
完全二叉树：除了最后一层以外其他所有的结点树都达到最大值，二最后一层上的所有节点分布在该层最左边连续的位置上。其性质：叶子结点只能够在最后两层出现。对于任意一层结点，如果左子树的高度是
m
右子树不能够大于
m
，也不小于
m-1
。
满二叉树：所有分支节点都有非空的左子树和非空右子树，所有的叶子结点都在同一层，这样的树称为满二叉树。叶子结点都在最后一层。
扩充二叉树：把原二叉树所有节点出现空的子树的位置都增加特殊的节点——空树叶，得到的二叉树就是扩充二叉树。也就是对于节点的度是
2
的节点，不增加。节点度是
1
的增加一个空树叶，对于是
0
的节点，增加两个空树叶。新增加的空节点的书目是原来二叉树节点的数目加
1
；
template
<
class
T
>
class
BinaryTreeNode
{
public
:
T
element;
BinaryTreeNode
<
T
> * left;
BinaryTreeNode
<
T
> * right;
};
template
<
class
T
>
class
BinaryTree
{
private
:
BinaryTreeNode
* root;
public
:
void
visit(
BinaryTreeNode
<
T
> *
node
){
cout <<
node
->element << endl;
}
//
层次遍历，也就是广度优先遍历
void
level_order(
BinaryTreeNode
<
T
> *
root
){
queue
<
BinaryTreeNode
<
T
>* > nodeQueue;
BinaryTreeNode
<
T
>* pointer =
this
->root;
if
(pointer){
nodeQueue.push(pointer);
}
while
(!nodeQueue.empty()){
pointer=nodeQueue.front();
visit(pointer);
nodeQueue.pop();
if
(pointer->left){
nodeQueue.push(pointer->left);
}
if
(pointer->right){
nodeQueue.push(pointer->right);
}
}
}
//
深度优先遍历分为前序遍历，中序遍历和后续遍历
/*
前序遍历就是先序遍历，
1
访问根节点
2.
前序遍历左子树
3.
前序遍历右子树
*/
void
pre_order(
BinaryTreeNode
<
T
> *
root
){
if
(
root
!=
NULL
){
visit(
root
);
pre_order(
root
->left);
pre_order(
root
->right);
}
}
//
使用
stack
void
pre_order_no_recusion(
BinaryTreeNode
<
T
> *
root
){
stack
<
BinaryTreeNode
<
T
>*> nodeStack;
BinaryTreeNode
<
T
>* pointer=
root
;
while
(!nodeStack.empty|| pointer){
if
(pointer){
visit(pointer);
if
(pointer->right!=
NULL
){
nodeStack.push(pointer->right);
}
pointer=pointer->left;
}
else
{
pointer=nodeStack.top();
nodeStack.pop();
}
}
}
/*
中序遍历
*/
void
in_order(
BinaryTreeNode
<
T
>*
root
){
if
(
root
!=
NULL
){
in_order(
root
->left);
visit(
root
);
in_order(
root
->right);
}
}
void
in_order_no_recusion(
BinaryTreeNode
<
T
>*
root
){
stack
<
BinaryTreeNode
<
T
>*> nodeStack;
BinaryTreeNode
<
T
>* pointer=
root
;
while
(!nodeStack.empty()||pointer){
if
(pointer){
nodeStack.push(pointer);
pointer=pointer->left;
}
else
{
pointer=nodeStack.top();
visit(pointer);
pointer=pointer->right;
nodeStack.pop()
}
}
}
/*
*/
void
post_order(
BinaryTreeNode
<
T
>*
root
){
if
(
root
!=
NULL
){
post_order(
root
->left);
post_order(
root
->right);
visit(
root
);
}
}
void
post_order_no_recusion(
BinaryTreeNode
<
T
>*
root
){
stack
<
BinaryTreeNode
<
T
>* > nodeStack;
BinaryTreeNode
<
T
>* pointer =
root
;
BinaryTreeNode
<
T
>* pre=
root
;
while
(pointer){
for
(;pointer->left!=
NULL
;pointer=pointer->right){
nodeStack.push(pointer);
}
while
(pointer && (pointer->right ==
NULL
||pointer->right==pre)){
visit(pointer);
pre=pointer;
if
(nodeStack.empty()){
return
;
}
pointer=nodeStack.top();
nodeStack.pop();
}
nodeStack.push(pointer);
pointer= pointer->right;
}
}
};
转载于:https://www.cnblogs.com/hbhzsysutengfei/p/3439329.html