栈的存储方式有顺序存储和链式存储。
栈的基本运算:(1) 入栈运算,在栈顶位置插入元素;
(2) 退栈运算,删除元素(取出栈顶元素并赋给一个指定的变量);
(3)读栈顶元素,将栈顶元素赋给一个指定的变量,此时指针无变化。
队列: 指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。
用
指针指向队头 元素的前一个位置 。
队列是“先进先出”( FIFO )或 “后进后出”( LILO )的线性表。
队列运算包括:(1) 入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。
队列的顺序存储结构一般采用队列循环的形式。
循环队列 s=0 表示队列空;s=1 且 front=rear 表示队列满。
计算循环队列的元素个数:“尾指针减头指针”,若为负数,再加其容量即可。
1.6 树与二叉树
树是一种简单的非线性结构,其所有元素之间具有明显的层次特性。
在树结构中,每一个结点只有一个前件,称为父结点。
没有前件的结点只有一个,称为树的根结点,简称树的根。
每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深
度。
二叉树的特点:(1) 非空二 叉 树只有一个根结点;
(2) 每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则
个
结点。
完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。
二叉树 基本性质:
(1)在二 叉 树的第
2
k-1
(k ≥ 1) 个结点;
(2)深度为
个结点;
(3)度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个;
(4)具有 n 个结点的二叉树,其深度至少为[log
2
n]+1,其中[log
2
n]表示取 log
2
n 的整数部分
(5)具有 n 个结点的完全二叉树的深度为[log
2
n]+1;
(6) 设完全二叉树共有 n 个结点。如果从根结点开始,按层序(每一层从左到右)用自然数 1,2,…n 给结点进行编号
(k=1,2….n),有以下结论:
① 若 k=1,则该结点为根结点,它没有父结点;若 k>1,则该结点的父结点编号为 INT(k/2);
② 若 2k≤n,则 k 结点的左子结点编号为 2k;否则该结点无左子结点(也无右子结点);
③ 若 2k+1≤n,则编号为 k 的结点的右子结点编号为 2k+1;否则该结点无右子结点。
补充:增加度为 1 的结点不会影响二叉树的叶子结点数,每增加一个度为 2 的结点便会增加一个叶子结点,没有度为 2 的
结点时叶子结点数为 1。
已知完全二叉树有 x 个结点,求其叶子结点数:
① 确定层数为 k;②第 k 层的结点数 y=x-(2
k-1
-1);
③ 第 k-1 层的叶子结点数 n=2
(k-1)-1
-y/2<若 y/2 有余,则要加 1>;④最后 y+n。
二 叉 树存储结构采用 链式存储结构,对于满二 叉 树与完全二 叉 树可以按层序进行顺序存储。
二 叉 树的遍历:
(1)前序遍历( DLR ),首先访问根结点,然后遍历左子树,最后遍历右子树;
(树根在第一,下走不跳结点)
(2)中序遍历( LDR ),首先遍历左子树,然后访问根结点,最后遍历右子树;
(有左先左,再寻根,后找右。最左边的结点最先遍历,最右边的结点最后遍历)
3 / 13