二叉排序树的建立_怎么建立二叉排序树_二叉排序树的创建(13)

Assign (s, t), Create

(s, cs)

Equal (s, t), Length

(s)

Concat (s, t)

Substr (s, pos, len)

Index (s, t)

Replace (s, t, v)

Delete (s, pos, len) Assign(s,t)将变量t赋值给s，Create(s,cs)根据字串创建变量s。 判断串相等，求串长度。如Length(“”)=0。 串连接。如Concat(“ab”,”cd”)=”abcd”。 取子串，pos为开始位置，len为子串长度。 求子串t在主串s中的位置。如Index(“abc”,”ab”)=1，Index(“a bc”,”bc”)=3。 把串s中的字串t替换成v。如Replace(“aaa”,”aa”,”a”)=”aa”。 删除串s的一部分。

注：完成习题集4.1~4.6。

串的存储结构

表 错误！文档中没有指定样式的文字。.6 串的存储结构

定长顺序串

堆分配存储表示

块链存储表示

基础知识和算法

树及有关概念 最大长度固定，超过最大长度则作截断处理 串的长度几乎没有限制 块内存储空间连续，块间不连续 树和二叉树

树，根，子树；结点，结点的度，叶子（终端结点），分支结点（非终端结点），内部结点，树的度；孩子，双亲，兄弟，祖先，子孙，堂兄弟；层次（根所在层为第1层），深度，高度；有序树，无序树，二叉树是有序树；森林。

二叉树

二叉树（二叉树与度为2的树不同，二叉树的度可能是0，1，2）；左孩子，右孩子。 二叉树的五种基本形态。

二叉树的性质

10i-1bb) 二叉树的第i层上至多有2个结点。

kcc) 深度为k的二叉树至多有2-1个结点。

k 满二叉树：深度为k，有2-1个结点。

完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。

dd) 叶子结点n0，度为2的结点为n2，则n0 = n2+1。

考虑结点个数：n = n0 + n1 + n2

考虑分支个数：n-1 = 2n2 + n1

可得n0 = n2+1

例：1) 二叉树有n个叶子，没有度为1的结点，共有 个结点。 2) 完全二叉树的第3层有2个叶子，则共有 个结点。

分析：1) 度为2的结点有n-1个，所以共2n-1个结点。 2) 注意考虑到符合条件的二叉树的深度可能是3或4，所以有5、10或11个结点。

ee)

ff) n个结点的完全二叉树深度为?logn??1。 n个结点的完全二叉树，结点按层次编号

有： i的双亲是?n/2?，如果i = 1时为根（无双亲）；

i的左孩子是2i，如果2i>n，则无左孩子；

i的右孩子是2i + 1，如果2i + 1>n则无右孩子。

二叉树的存储结构

gg) 顺序存储结构

用数组、编号i的结点存放在[i-1]处。适合于存储完全二叉树。

hh) 链式存储结构

二叉链表：

typedef struct BTNode {

DataType data;

struct BTNode *lchild, *rchild;

} BTNode, *BinTree;

三叉链表：

typedef struct BTNode {

DataType data;

struct BTNode *lchild, *rchild, *parent;

} BTNode, *BinTree; 10 本书中约定根结点在第1层，也有约定根在第0层的，则计算公式会有所不同。

例：用二叉链表存储n个结点的二叉树(n>0)，共有(_a_)个空指针域；采用三叉链表存储，

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25557-13.html