数据结构 树 基础

数据结构 树 部分 1 数据结构 树（Ⅰ）基础 §1 引论 1、树的递归定义：树是满足以下条件，至少包含一个节点的有限集合： （1）有一个特别指定的节点，树根 （2）其他节点分划成 n≥0 个不相交的集合，每个集合又都是树（根的子树） 2、术语： 节点：包含信息项和指向其他节点的分支 度：一个节点子树的数目 树中度数最大的节点的度树的度 叶子：终端节点 度为 0 祖先 父亲 兄弟 孩子 树的高度（深度） 3、树的示 （1）链式表示 （2）左孩子右兄弟表示 （3）2-度树表示（二叉树）将上述表示绕根节点顺时针旋转 45 度 §2 二叉树 1、定义：二叉树或者是节点个数为 0 的空树；或者是节点个数有限的节点集合，节点中有一个是根节点， 根节点有两个不相交的二叉树子树，分别称为左子树和又子树 2、二叉树的性质举例： （1）二叉树第 i 层的最大节点个数：2𝑖−1 （2）深度为 k 的二叉树的最大节点个数为2𝑘 − 1 （3）对任何非空二叉树，𝑛0为叶节点个数，𝑛2为度为 2 的节点个数，则：𝑛0=𝑛2 + 1； 3、二叉树的表示 （1）顺序存储：特别适合于存储完全二叉树（上一层排满后，本层开始自左至右依次排开） 下面的引理保证我们在知道父节点 左（右）孩子节点时总能找到另两个（如果有的话）： 1>当 1当 2i≤n时，i号节点的左孩子节点为 l(i) = 2i 3>当 2i + 1≤n时，i号节点的右孩子节点的位置是 r(i) = 2i + 1 （2）链式存储 typedef struct node * treePointer; struct node { int data; treePointer leftChild,rightChild; }; data leftChild rightChild 1 1 2 3 4 5 6 数据结构 树 部分 2 §3 二叉树遍历 遍历：访问树中每个节点 一次且仅一次 1、栈实现（以递归为例，可以改为循环） 中序遍历 LVR 先序遍历 VLR 后序遍历 LRV 遍历的代码是非常简洁且优美的递归程序 （1）、LVR void inOrder(treePointer ptr) { if(ptr) { inOrder(ptr->leftChild); printf(“%d”,data); inOrder(ptr->rightChild); } } （2）、VLR （3）、LRV 2、队列实现 层序遍历 void levelOrder(treePointer ptr) { int front = 0,rear = 0; treePointer queue[MAX_QUEUE_SIZE]; if(!ptr) return; addQueue(ptr);//入队

函数

excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载

for( ; ;) { ptr = deleteQueue();//队首出队 if(ptr)//队首仍是节点 { printf(“%d”,data); if(ptr->leftChild) addQueue(ptr->leftChild); if(ptr->rightChild) addQueue(ptr->rightChild); } else break; } } §4 二叉树其他操作举例（体会递归操作的简洁优美） 1、二叉树复制 2、判断二叉树是否相等 数据结构 树 部分 3 §5 线索二叉树 1、线索：任何一种形态的二叉树，总是存在着很多的空的链域，在这些空的链域中存放指针，规则如下 （1）ptr->leftChild 为空，指向 中序遍历中 该节点的 前驱结点 （2）ptr->rightChild 为空，指向 中序遍历中 该节点的 后继结点 若没有前趋和后继，我们设置一个指向树根的新节点 root，全部指向它 例如： 2、线索二叉树的中序遍历 threadTree insucc(threadPointer ptr)//寻找中序后继 threadTree inOrder(threadPointer ptr)//中序遍历 3、线索二叉树节点的插入（建立线索二叉树） 以向节点 s 插入其右孩子为例讨论 case1:s 的右子树为空 case2:s 的右子树 T 不为空，插入后 T 成为 r 的右子树 void insertRightChild(threadPointer s,threadPointer r) { threadPointer temp; r->rightChild = s->rightChild; r->rightThread = s->rightThread; r->leftChild = s; r->leftThread = true; s->rightChild = r; s->rightThread = false; if(!r-> rightThread) temp = insucc(r); temp->leftChild = r; } §6 堆 1、优先级队列 删除操作以关键字的优先级为基准，总是删除优先级最高或者优先级最低的元素 2、大根堆 定义：大根树中每个节点的关键字总是不小于孩子节点的关键字（如果有的话） 大根堆 = 大根

书

关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf

&& 完全二叉树（完全二叉树的顺序存储） （类似可定义小根树与小根堆） 大根堆的操作主要涉及节点的上滑与下滑 （1）大根堆节点的插入（大根堆的建立） 现要在以下大根堆中插入一节点，其关键字值是 21. 大根堆的插入操作，首先将该节点放入当前二叉树下一位置，然后逐步上滑，直至该元素到达正确的位置 1 1 2 3 4 5 6 root data int leftThread int rightThread treePointer leftChild treePointer rightChild 数据结构 树 部分 4 （2）大根堆 根 的删除（根总是优先出队） 删除的节点一定是树根，下面进行下滑操作，取根的左、右孩子与当前最末端的节点，比较其大小，将其 中优先级最高者置于根，（优先级最高者必是左右孩子中的一个），将最末端指针沿着上滑的孩子方向逐步 下滑至合适的位置。 element pop(element* heap,int *n)//element 为大根堆元素,*n 为大根堆中节点个数 { int parent ,child; element temp,item; if(n == 0)……//堆空的处理 item = heap[1];//弹出的元素 根 //以下构造弹出后的大根堆 temp = heap[(*n)--]; parent = 1; child = 2; while(child <= *n) { if(child < *n && heap[child].key < heap[child + 1].key) child++; if(temp.key >= heap[child].key) break; heap[parent] = heap[child]; parent = child; child = child * 2; } heap[parent] = temp; //应将最后一个节点删除 *n = *n -1; return item; } §7 二叉查找树基础 1、定义：二叉查找树是一棵树，可以是空树，否则要满足以下条件 （1）树中每个节点有一个唯一的关键字 1 20 15 5 14 10 2 21 1 21 15 20 14 10 2 5 数据结构 树 部分 5 （2）如果有左子树，则左子树的所有关键字小于根的关键字 （3）如果有右子树，则右子树的所有关键字大于根的关键字 （4）左右子树都是二叉查找树 2、查找 element* search(treePointer tree,int k) { if(!tree)return NULL;//树空 if(k == tree->key) return tree; if(k < tree->key) return search(tree->leftChild,k); if(k > tree->key) return search(tree->rightChild); } 2、插入节点（二叉查找树的建立）（代码略去） （1）首先确认待插入元素是否存在，若存在不允许插入，若不存在，返回最后一次查找时指针的位置 （2）如果找到，或者树为空，新建一个节点，在树不为空的基础上，比较与返回的最后一次查找的指针所 指位置关键字的大小关系，确认插在其右还是其左。 （3）新插入的节点一定是叶子 3、删除节点 （1）删除叶子和只有一个孩子的节点很简单 （2）删除有两个孩子的节点： 先用左子树中关键字最大孩子的节点值或右子树中关键字最小孩子的节点值替换待删除的节点，然后删除 该节点；所选用的节点也只能是叶子 4、二叉查找树的合并与分裂 （1）三路合并 （2）二路合并 （3）split 成三路 5、二叉查找树经过一系列操作后很可能高度倾斜，n 个节点的树的深度可能成为 n，所以有各种平衡二叉 查找树，如 AVL 红-黑树 2-3 树 2-3-4 树 𝐵+-树等 §8 选拔树 1、引子 给定 k 组有序序列，每组序列称为一路，要把 k 路归并为一路。 2、优胜树 （1）完全二叉树 每个节点的值是各个孩子中关键字值得优胜者 （2）顺序存储 根节点作为本轮选拔的优胜者弹出 （3）每一轮的选拔都从上轮被选拔出一个元素的那一路进入一个新元素，开始进行下一轮选拔，遴选的过 程需要定位兄弟与父亲节点的位置 （4）考虑中间某一路的选拔结束，可以设置标记位 3、淘汰树 考虑优胜树的选拔过程，输出优胜值后需要重构，为简化重构的过程，产生了淘汰树。 （1）每个节点的值是两个孩子中关键字的输者 （2）增加一个 0 号节点，表示一轮选拔过程的优胜者 数据结构 树 部分 6 §9 森林 1、定义：森林是 n≥0 棵不相交树的集合 2、森林转换为二叉树： 设森林由树𝑇1,𝑇2, … , 𝑇𝑛组成，与之对应的二叉树B(𝑇1,𝑇2, … , 𝑇𝑛)，满足以下条件： （1）n = 0，B 是空树 （2）n>0，则 B 的根是𝑇1的根，根的左子树是B(𝑇11,𝑇12, … , 𝑇1𝑛)，其中𝑇11,𝑇12, … , 𝑇1𝑛是𝑇1的子树，根的右 子树是B(𝑇2, … , 𝑇𝑛)； 关于森林的遍历在此不予讨论。 §10 二叉树的计数 本节讨论有 n 个节点的二叉树有几种形态。具有 n个结点的不同形态的二叉树的数目在一些涉及二叉树的 平均情况复杂性分析中是很有用的 结论是： 含有 n 个节点的二叉树形态有 1 𝑛 + 1 ( 2𝑛 𝑛 ) 二叉树计数的推导有多种，可以从由中序和先序遍历结果可确定二叉树形态 以及 矩阵乘法的结合律等中 推导出来。作简要说明： 设 Bn是含有 n个结点的不同二叉树的数目 由于二叉树是递归的定义的，所以我们很自然地得到关于 Bn的下面的递归方程： (1) 即一棵具有 n>1个结点的二叉树可以看成是由一个根结点一棵具有 i个结点的左子树和一棵具有 n-i-1个 结点的右子树所组成 (1)式的解是 (2) 即所谓的 Catalan数。因此，当 n=3时,B3=5于是，含有 3个结点的不同的二叉树有 5棵，如图所示 含有 3个结点的不同二叉树