-
有根树的递归定义
- 或者为空，或者为一个根节点和多个根的子树的集合
-
基本概念
- 度：节点的子树数目就是节点的度，树中度的最大值是树的度
- 祖先：根结点到该结点的路径上的各个结点都是该结点的祖先。
- 直接上属：双亲
- 子孙：某结点的所有下属结点，都是该结点的子孙。
- 直接下属：子女
- 结点的层次：规定根结点在第一层，其子女结点的层次等于它的层次加一。
- 结点的深度：结点的深度即为结点的层次；离根最远结点的层次即为树的深度。
- 结点的高度：规定叶结点的高度为 1，其双亲结点的高度等于它的高度加一。树的高度等于根节点的高度
- 有序树：节点的各棵子树有次序
- 无序树：节点的各棵子树可以互换位置
- 同一结点的子女互称兄弟
- 森林：森林是 m（m≥0）棵树的集合
二叉树¶
- 结点的一个有限集合，或者为空；或者由一个根结点加上两棵分别称为左子树右子树的互不相交的二叉树组成
- 性质
- 深度为 k 的二叉树最少 \(k\) 个结点，最多 \(2^k-1\) 个（满二叉树）；n 个节点的完全二叉树深度 \(\lceil\log_2(n+1)\rceil\)
- 设叶节点 \(n_0\) 个，非叶节点 \(n_2\) 个，则 \(n_0=n_2+1\)
- 满二叉树：有 \(2^k-1\) 个结点的二叉树
- 完全二叉树：除第 k 层外全满（堆的要求）
- 二叉树的顺序表示：
-
-
链表表示
难点¶
非递归遍历二叉树¶
- 前序遍历
-
template <class T> void BinaryTree<T>:: PreOrder (void (*visit) (BinTreeNode<T> *t) ) { stack<BinTreeNode<T>*> S; BinTreeNode<T> *p = t; S.Push (NULL); while (p != NULL) { visit(p); //访问结点 if (p->rightChild != NULL) S.Push (p->rightChild); //预留右指针在栈中 if (p->leftChild != NULL) p = p->leftChild; //进左子树 else S.Pop(p); //左子树为空 } }; -
中序遍历
-
template <class T> void BinaryTree<T>:: InOrder (void (*visit) (BinTreeNode<T> *t)) { stack<BinTreeNode<T>*> S; BinTreeNode<T> *p = t; do { while (p != NULL) { //遍历指针向左下移动 S.Push (p); //该子树沿途结点进栈 p = p->leftChild; } if (!S.IsEmpty()) { //栈不空时退栈 S.Pop (p); visit (p); //退栈, 访问 p = p->rightChild; //遍历指针进到右子女 } } while (p != NULL || !S.IsEmpty ()); }; -
后序遍历
- 定义栈的结点
template <class T> void BinaryTree<T>:: PostOrder (void (*visit) (BinTreeNode<T> *t) { Stack<stkNode<T>> S; stkNode<T> w; BinTreeNode<T> * p = t; //p是遍历指针 do { while (p != NULL) { w.ptr = p; w.tag = L; S.Push (w); p = p->leftChild; } int continue1 = 1; //继续循环标记, 用于R while (continue1 && !S.IsEmpty ()) { S.Pop (w); p = w.ptr; switch (w.tag) { //判断栈顶的tag标记 case L: w.tag = R; S.Push (w); continue1 = 0; p = p->rightChild; break; case R: visit (p); break; } } } while (!S.IsEmpty ()); //继续遍历其他结点 cout << endl; };
层次遍历¶
- 使用一个先进先出队列，在处理上一层时，将其下一层的结点直接进到队列（的队尾）。在上一层结点遍历完后，下一层结点正好处于队列的队头，可以继续访问它们。
template <class T>
void BinaryTree<T>::
LevelOrder (void (*visit) (BinTreeNode<T> *t)) {
if (t == NULL)
return;
Queue<BinTreeNode<T> * > Q;
BinTreeNode<T> *p = t;
Q.EnQueue (p);
while (!Q.IsEmpty ()) {
Q.DeQueue (p);
visit (p);
if (p->leftChild != NULL)
Q.EnQueue (p->leftChild);
if (p->rightChild != NULL)
Q.EnQueue (p->rightChild);
}
};
难点¶
线索化二叉树¶
- 通过遍历二叉树可以将二叉树中所有节点的数据排列在一个线性序列中，可以找到前驱和后继
-
直接为每个节点添加 pred 和 succ 指针造成了浪费，没有充分使用原先树中的边。
-
利用空余的 left 和 right 指针存储前后继，使用标志位 ltag、rtag 指明指针是指示子女还是前驱后继，一般用 left 存前驱，right 存后继
- 标志位=0 表示存储的是子女结点，=1 表示存储线索
-
实际上对于原始存在的左右节点，其 tag 均为 0，对于新创建的为1.
-
中序线索化二叉树
| rightChild\rtag | ==0 | ==1 |
|---|---|---|
| ==NULL | 无此情况 | 无后继 |
| !=NULL | 后继为当前结点右子树的中序下的第一个结点 | 后继为子女结点 |
| leftChild\ltag | ==0 | ==1 |
|---|---|---|
| ==NULL | 无此情况 | 无前驱 |
| !=NULL | 前驱为当前结点左子树中序下的最后一个结点 | 前驱为左子女结点 |
| ##### *具体实现 |
template<T>
TreadNode<T>*ThreadTree<T>::First(ThreadNode<T>*current){
//返回以current为根的中序线索二叉树中中序序列下的第一个结点
ThreadNode<T>*p=current;
while(p->ltag==0)p=p->leftChild;
return p;
}
//线索遍历
template<T>
TreadNode<T>*ThreadTree<T>::Next(ThreadNode<T>*current){
ThreadNode<T>*p=current->rightChild;
if(current->rtag==0)return First(p);
else return p;
}
template<T>
TreadNode<T>*ThreadTree<T>::Last(ThreadNode<T>*current){
//返回以current为根的中序线索二叉树中中序序列下的最后一个结点
ThreadNode<T>*p=current;
while(p->rtag==0)p=p->rightChild;
return p;
}
//线索遍历
template<T>
TreadNode<T>*ThreadTree<T>::Prior(ThreadNode<T>*current){
ThreadNode<T>*p=current->leftChild;
if(current->ltag==0)return Last(p);
else return p;
}
-
中序遍历建立线索化二叉树
template <class T> struct ThreadNode { //线索二叉树的结点类 int ltag, rtag; //线索标志 ThreadNode<T> *leftChild, *rightChild;//线索或子女指针 T data; //结点数据 ThreadNode ( const T item) //构造函数 : data(item), leftChild (NULL), rightChild (NULL), ltag(0), rtag(0) {} }; template <class T> class ThreadTree { //线索化二叉树类 protected: ThreadNode<T> *root; //树的根指针 void createInThread (ThreadNode<T> *current, ThreadNode<T> *& pre); //中序遍历建立线索二叉树 ThreadNode<T> *parent (ThreadNode<T> *t); //寻找结点t的双亲结点 public: ThreadTree () : root (NULL) { } //构造函数 void createInThread(); //建立中序线索二叉树 ThreadNode<T> *First (ThreadNode<T> *current); //寻找中序下第一个结点 ThreadNode<T> *Last (ThreadNode<T> *current); //寻找中序下最后一个结点 ThreadNode<T> *Next (ThreadNode<T> *current); //寻找结点在中序下的后继结点 ThreadNode<T> *Prior (ThreadNode<T> *current); //寻找结点在中序下的前驱结点 ……… }; template <class T> void ThreadTree<T>::createInThread () { ThreadNode<T> *pre = NULL; //前驱结点指针 if (root != NULL) { //非空二叉树, 线索化 createInThread (root, pre); //中序遍历线索化二叉树 pre->rightChild = NULL; pre->rtag = 1; //后处理中序最后一个结点 } }; template <class T> void ThreadTree<T>:: createInThread (ThreadNode<T> *current,ThreadNode<T> *& pre) { //通过中序遍历，添加缺失的边进行连接, 对二叉树进行线索化 if (current == NULL) return; createInThread (current->leftChild, pre); //递归, 左子树线索化 if (current->leftChild == NULL) { //建立当前结点的前驱线索 current->leftChild = pre; current->ltag = 1; } if (pre != NULL && pre->rightChild == NULL) //建立前驱结点的后继线索 { pre->rightChild = current; pre->rtag = 1; } pre = current; //前驱跟上,当前指针向前遍历 createInThread (current->rightChild, pre); //递归, 右子树线索化 };//就是左中右的中序遍历模式，对于中结点双向连接 -
建立过程示例：
树与森林¶
树的存储表示¶
- 广义表表示
-
-
双亲表示
-
-
链表表示
-
-
指针节点表示
-
-
子女兄弟表示
- firstchild指向第一个子女节点，nextSibling指向下一个兄弟，即横向沿链扫描
树的遍历¶
-
树的二叉树表示：将树转化为子女兄弟表示
-
先根次遍历
- 树的先根遍历结果与其对应二叉树表示的前序遍历结果相同
-
先访问根节点再依次遍历子树
-
后根次遍历
- 树的后根遍历结果与其对应二叉树表示的中序遍历结果相同
-
先遍历子树在访问根节点
-
广度优先（层次）遍历
森林与二叉树的转换¶
-
-
森林转化为二叉树
- 二叉树 B 的根是 F 第一棵树 \(T_1\) 的根
- 左子树为 \(B(T_{11},\dots,T_{1m})\) 即 \(T_1\) 的根的子树
-
右子树为 \(B(T_2,\dots,T_n)\) 即除 \(T_1\) 外其他树构成的森林
-
二叉树转化为森林
- \(F\) 中第一颗树 \(T_1\) 的根为 \(B\) 的根
- \(T_1\) 的根的子树森林 \({T_{11},\dots,T_{1m}}\) 是由 B 的根的左子树 \(LB\) 转化而来
- \(F\) 中除了 \(T_1\) 之外其余的树组成的森林 \({T_2,T_3,\dots,T_n}\) 是由 \(B\) 的根的右子树 \(RB\) 转换而成的森林
森林的遍历¶
- 森林的先根次序遍历
- 先根遍历森林的第一棵子树森林，然后再遍历森林中除第一棵树外其他树组成的森林
-
-
森林的后根次序遍历
- 先访问第一棵子树的根结点的子树森林，然后访问森林的根结点\(r_1\), 然后再遍历森林中除第一棵树外其他树组成的森林
-
-
森林的广度优先遍历
- 先遍历各棵树的根节点
- 遍历各棵树根结点的所有子女
- 逐层向下进行遍历
堆¶
- 下标从0开始时结点间的序号关系
- 父节点 \(\lfloor (i-1)/2\rfloor\)
-
左右子女 \(2i+1,2i+2\)
-
最小堆示例
template <class E> class MinHeap : public MinPQ<E> { //最小堆继承了（最小）优先级队列 public: MinHeap (int sz = DefaultSize); //构造函数 MinHeap (E arr[], int n); //构造函数 ～MinHeap() { delete [ ] heap; } //析构函数 bool Insert (E& x); //插入 bool Remove (E& x); //删除 bool IsEmpty () const //判堆空否 { return currentSize == 0; } bool IsFull () const //判堆满否 { return currentSize == maxHeapSize; } void MakeEmpty () { currentSize = 0; } //置空堆 private: E *heap; //最小堆元素存储数组 int currentSize; //最小堆当前元素个数 int maxHeapSize; //最小堆最大容量 void siftDown (int start, int m); //调整算法 void siftUp (int start); //调整算法 }; template <class E> MinHeap<E>::MinHeap (int sz) { maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize; heap = new E[maxHeapSize]; //创建堆空间 if (heap == NULL) { cerr << “堆存储分配失败！” << endl; exit(1); } currentSize = 0; //建立当前大小 }; template <class E> MinHeap<E>::MinHeap (E arr[], int n) { maxHeapSize = (DefaultSize < n) ? n : DefaultSize; heap = new E[maxHeapSize]; if (heap == NULL) { cerr << “堆存储分配失败！” << endl; exit(1); } for (int i = 0; i < n; i++) heap[i] = arr[i]; currentSize = n; //复制堆数组, 建立当前大小 int currentPos = (currentSize-2)/2; //找最初调整位置:最后分支结点 while (currentPos >= 0) { //逐步向上扩大堆 siftDown (currentPos, currentSize-1); //局部自上向下下滑调整 currentPos--; } }; template <class E> void MinHeap<E>::siftDown (int start, int m ) { //私有函数: 从结点start开始到m为止, 自上向下比较, //如果子女的值小于父结点的值, 则关键码小的上浮, //继续向下层比较, 将一个集合局部调整为最小堆。 int i = start, j = 2*i+1; //j是i的左子女位置 E temp = heap[i]; while (j <= m) { //检查是否到最后位置 if ( j < m && heap[j] > heap[j+1] ) j++; //让j指向两子女中的小者 if ( temp <= heap[j] ) break; //小则不做调整 else { heap[i] = heap[j]; i = j; j = 2*j+1; } //否则小者上移, i, j下降 } heap[i] = temp; //回放temp中暂存的元素 }; template <class E> void MinHeap<E>::siftUp (int start) { //私有函数: 从结点start开始到结点0为止, 自下向上 //比较, 如果子女的值小于父结点的值, 则相互交换, //这样将集合重新调整为最小堆。关键码比较符<= //在E中定义。 int j = start, i = (j-1)/2; E temp = heap[j]; while (j > 0) { //沿父结点路径向上直达根 if (heap[i] <= temp) break; //父结点值小, 不调整 else { heap[j] = heap[i]; j = i; i = (i-1)/2; } //父结点结点值大, 调整 } heap[j] = temp; //回送 }; template <class E> bool MinHeap<E>::Insert (const E& x ) { //公共函数: 将x插入到最小堆中 if ( currentSize == maxHeapSize ) //堆满 { cerr << "Heap Full" << endl; return false; } heap[currentSize] = x; //插入 siftUp (currentSize); //向上调整 currentSize++; //堆计数加1 return true; }; template <class E> bool MinHeap<E>::Remove (E& x) { if ( !currentSize ) { //堆空, 返回false cout << "Heap empty" << endl; return false; } x = heap[0]; heap[0] = heap[currentSize-1]; currentSize--; siftDown(0, currentSize-1); //自上向下调整为堆 return true; //返回最小元素 }; -
上浮操作通常在插入新元素到堆中时使用。当一个新元素被添加到堆的末尾时，它可能会破坏堆的性质。为了修复这个性质，我们需要将这个元素向上移动到合适的位置，以恢复堆的性质。
-
下沉操作用在删除堆顶元素或者调整堆中某个元素的值时。在删除堆顶元素后，通常将堆的最后一个元素移动到堆顶，这样会破坏堆的性质。为了修复这个性质，需要将这个元素向下移动到合适的位置
-
构建堆：从最后一个开始倒序下沉调整
-
-
修改元素
- 如果在最大堆中增加了一个元素的值，或者在最小堆中减少了一个元素的值，这个元素可能会违反堆的性质，因为它可能变得比其父节点大（最大堆）或小（最小堆）。在这种情况下，需要进行上浮操作。
- 如果在最大堆中减少了一个元素的值，或者在最小堆中增加了一个元素的值，这个元素可能会违反堆的性质，因为它可能变得比其孩子节点小（最大堆）或大（最小堆）。在这种情况下，需要进行下沉操作。
Huffman 树¶
- 带权路径长度达到最小的扩充二叉树
路径长度¶
- 路径长度 PL：连接两结点的路径上的分支数（边）
- 内部路径长度 IPL：各非叶节点到根节点的路径长度之和
- 外部路径长度 EPL：各叶节点到根节点的路径长度之和
- \(PL=EPL+IPL\)
- 完全二叉树路径长度最小，有 \(PL=\sum^n_{i=1}\lfloor\log_2i\rfloor\)
带权路径长度 WPL¶
- 把叶结点看成“外结点”，非叶结点看成“内结点”，并赋予叶节点一个权值。这样的二叉树称为相应权值的扩充二叉树。
- 扩充二叉树中只有度为 2 的内结点和度为 0 的外结点。根据二叉树的性质，有 n 个外结点就有 n-1 个内结点，总结点数为 2 n-1。
- \(WPL=\sum_{i=1}^1w_i*l_i\) (权值乘以路径长度)
Huffman 树构造方式¶
-
初始状态：给定 n 个权值 \({w_0,w_1,\cdots,w_{n-1}}\) 构造有 n 棵扩充二叉树的森林 \(F={T_0,\cdots,T_{n-1}}\)，每颗子树都只有一个带特定权值的根节点，左右子树为空
-
重复以下，直至剩下一棵树：
- 选择两颗根节点权值最小的扩充二叉树，作为左右子树构造新二叉树，新二叉树根节点的权值为左右子树上根节点的权值之和
- 在 F 中删去两颗二叉树并把新的加入 F
-
-
Huffman 编码
- 根据字符出现频率决定对字符的编码，使用变长二进制编码
- 总编码长度就是表示报文中全部字母需要的二进制位的数目，就是 Huffman 树的带权路径长度 WPL
- CAST CAST SAT AT A TASA
