做网站文字大小,建设视频网站设计意义,免费psd模板素材,网站的建设服务一、定义
树(Tree)是n(n0)个结点的有限集。当n0时成为空树,在任意一棵非空树中: 1、有且仅有一个特定的称为根(Root)的结点; 2、当n1时,其余结点可分为m(m日)个互不相交的有限集T1、T2、...、 Tm#xff0c;其中每一个集合本身又是一棵树#xff0c;并且称为根的…一、定义
树(Tree)是n(n0)个结点的有限集。当n0时成为空树,在任意一棵非空树中: 1、有且仅有一个特定的称为根(Root)的结点; 2、当n1时,其余结点可分为m(m日)个互不相交的有限集T1、T2、...、 Tm其中每一个集合本身又是一棵树并且称为根的子树(SubTree)。
需要注意的是
1、n6时根结点是唯一的坚决不可能存在多个根结点。
2、m0时,子树的个数是没有限制的但它们互相是一定不会相交的。 二、节点分类
刚才所有图片中每一个圈圈我们就称为树的一个结点。结点拥有的子树数称为结点的度-
(Degree)树的度取树内各结点的度的最大值。
1、度为0的结点称为叶结点(Leaf)或终端结点;
2、度不为0的结点称为分支结点或非终端结点除根结点外分支结点也称为内部结点。 三、结点间的关系
结点的子树的根称为结点的孩子(Child)相应的该结点称为孩子的双亲(Parent)同一双亲的孩子之间互称为兄弟(Sibling)。
结点的祖先是从根到该结点所经分支上的所有结点。
四、节点的层次
结点的层次(Level)从根开始定一起根为第一层根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度(Depth)或高度。
五、其他概念
如果将树中结点的各子树看成从左至右是有次序的不能互换的则称该树为有序树否则称为无序树。森林(Forest)是 m(m0)棵互不相交的树的集合。对树中每个结点而言其子树的集合即为森林。
六、树的存储结构
1、双亲表示法
双亲表示法,言外之意就是以双亲作为索引的关键词的一种存储方式。
我们假设以一组连续空间存储树的结点同时在每个结点中附设一个指示其双亲结点在数组中位置的元素。
也就是说每个结点除了知道自己是谁之外还知道它的粑粑妈妈在哪里。
定义一个结构体
#define MAXSIZE 100typedef struct PTNode {int data; //结点数据int parent; //双亲位置
}PTNode;typedef struct {PTNode node[MAXSIZE];int r; //根的位置int n; //节点数目
}PTree; 这样的存储结构我们可以根据某结点的parent指针找到它的双亲结点,所用的时间复杂度是0(1)索引到parent的值为-1时表示找到了树结点的根。
可是如果我们要知道某结点的孩子是什么?那么不好意思请遍历整个树结构 2、孩子表示法 3、双亲孩子表示法 //孩子节点
typedef struct CTNode {int child; //孩子结点的下标struct CTNode* next; //指向下一个孩子结点的指针
}*ChildPtr;//表头结构
typedef struct {int data; //存放在树中的节点数据int paraent; //存放双亲的下标ChildPtr friendchild; //指向第一个孩子的指针
}CTBox;//树结构
typedef struct {CTBox node[MAXSIZE];int r, n;
}CTTree;
七、二叉树
1、定义
二叉树Binary Tree是n(n0个结点的有限集合,该集合或者为空集空二叉树或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
注意
每个结点最多有两棵子树所以二叉树中不存在度大于2的结点。注意:不是都需要两棵子树而是最多可以是两棵没有子树或者有一棵子树也都是可以的。)
左子树和右子树是有顺序的次序不能颠倒。
即使树中某结点只有一棵子树,也要区分它是左子树还是右子树下面是完全不同的二叉树: 2、五种基本形态
1空二叉树
2只有一个根结点
3根结点只有左子树
4根结点只有右子树
5根结点既有左子树又有右子树
3、特殊二叉树
1斜树
斜树是一定要斜的但斜也要斜寻有范儿 2满二叉树
在一棵二叉树中如果所有分支结点都存在左子树和右子树并且所有叶子都在同一层上,这样的二叉树称为满二叉树。 特点
叶子只能出现在最下一层。非叶子结点的度一定是2。在同样深度的二叉树中满二又树的结点个数一定最多同时叶子也是最多。
3完全二叉树
对一棵具有n个结点的二叉树按层序编号如果编号为i(1in)的结点与同样深度的满二叉树中编号为i的结点位置完全相同则这棵二叉树称为完全二叉树。 这个也是满二叉树
特点
叶子结点只能出现在最下两层。最下层的叶子一定集中在左部连续位置。倒数第二层若有叶子结点一定都在右部连续位置。如果结点度为1则该结点只有左孩子。同样结点树的二叉树完全二叉树的深度最小。
注意:满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树。
重点
二叉树的性质一:在二叉树的第i层上至多2^(i-1)个结点(i1)
二叉树的性质二:深度为k的二叉树至多有2^k-1个结点(k1)
二叉树的性质三:对任何一棵二叉树T如果其终端结点数为n0度为2的结点数为n2则n0n21 打岔一下在纸面上写写画画很重要的
二叉树的性质四:具有n个结点的完全二叉树的深度为 ,向下取整 二叉树的性质五:如果对一棵有n个结点的完全二叉树(其深度为[log2n]1)的结点按层序编号对任一结点i(1in)有以下性质:
如果i 1则结点i是二叉树的根无双亲;如果i 1则其双亲是结点如果2i n则结点i无左孩子(结点i为叶子结点);否则其左孩子是结点2i如果2i1 n则结点i无右孩子;否则其右孩子是结点2i1 4、存储结构
1顺序存储 对于完全二叉树是十分方便的但是一般二叉树就不行了空间会造成极大的浪费
2链式存储
结点结构 代码
typedef struct BiNode {int data;struct BiTNode* lchild, * rchild;
}BiTNode,*BiTree; 5、二叉树的遍历 1先序遍历 根——左子树——右子树 ABDHIEJCFKG
2中序遍历 左子树——根——右子树 HDIBEGAFKCG
3后序遍历 左子树——右子树——根 HIDJEBKFGCA
4层序遍历 ABCDEFGHIJK
八、二叉树的建立和遍历算法 代码包括递归和非递归遍历
#define _CRT_SECURE_NO_WARNINGS 1;
#include stdio.h
#include stdlib.h typedef struct TreeNode {char val;struct TreeNode* left;struct TreeNode* right;
} TreeNode;TreeNode* createTree(char** str) {//*str就是 char数组的指针if (**str #) {(*str); //指针偏移return NULL;}TreeNode* node (TreeNode*)malloc(sizeof(TreeNode));node-val **str;(*str);//这里递归实现从根节点开始往左子树里填node-left createTree(str);node-right createTree(str);return node;
}// 递归遍历
void preOrderRecursive(TreeNode* root) {if (root NULL) return;printf(%c , root-val);preOrderRecursive(root-left);preOrderRecursive(root-right);
}void inOrderRecursive(TreeNode* root) {if (root NULL) return;inOrderRecursive(root-left);printf(%c , root-val);inOrderRecursive(root-right);
}void postOrderRecursive(TreeNode* root) {if (root NULL) return;postOrderRecursive(root-left);postOrderRecursive(root-right);printf(%c , root-val);
}// 非递归遍历使用栈来辅助
#define MAX_SIZE 100
typedef struct {TreeNode* data[MAX_SIZE];int top;
} Stack;void initStack(Stack* s) {s-top -1;
}int isEmpty(Stack* s) {return s-top -1;
}int isFull(Stack* s) {return s-top MAX_SIZE - 1;
}void push(Stack* s, TreeNode* node) {if (isFull(s)) return;s-data[(s-top)] node;
}TreeNode* pop(Stack* s) {if (isEmpty(s)) return NULL;return s-data[(s-top)--];
}void preOrderNonRecursive(TreeNode* root) {if (root NULL) return;Stack s;initStack(s);push(s, root);while (!isEmpty(s)) {TreeNode* node pop(s);printf(%c , node-val);if (node-right) push(s, node-right);if (node-left) push(s, node-left);}
}void inOrderNonRecursive(TreeNode* root) {Stack s;initStack(s);TreeNode* cur root;while (cur || !isEmpty(s)) {while (cur) {push(s, cur);cur cur-left;}cur pop(s);printf(%c , cur-val);cur cur-right;}
}void postOrderNonRecursive(TreeNode* root) {if (root NULL) return;Stack s1, s2;initStack(s1);initStack(s2);push(s1, root);while (!isEmpty(s1)) {TreeNode* node pop(s1);push(s2, node);if (node-left) push(s1, node-left);if (node-right) push(s1, node-right);}while (!isEmpty(s2)) {TreeNode* node pop(s2);printf(%c , node-val);}
}int main() {char input[101];scanf(%s, input);char* str input;TreeNode* root createTree(str);// 递归遍历 preOrderRecursive(root);printf(\n);inOrderRecursive(root);printf(\n);postOrderRecursive(root);printf(\n);// 非递归遍历 preOrderNonRecursive(root);printf(\n);inOrderNonRecursive(root);printf(\n);postOrderNonRecursive(root);printf(\n);return 0;
}这里的递归好理解对于非递归 九、线索二叉树 结构体
//二叉树的二又线索存储表示
typedef struct BiThrNode{TElemType data;struct BiThrNode *lchild, *rchild;int LTag, RTag;
}BiThrNode, *BiThrTree;
用实线表示孩子节点虚线表示前驱后继
中序线索代码实现
结构体
typedef struct Thread {struct Thread* left_node, * right_node;//左右指针int data;//需要存放的数据/*默认0代表左右孩子 1代表前驱或者后继*/int left_type;//类型标志int right_type;//类型标志
}Node;Node* pre;//前驱结点的变量
Node* head;//头指针 指向某种遍历的第一个结点
线索化
void inOrderThreadTree(Node* node)
{//如果当前结点为NULL 直接返回if (node NULL) {return;}//先处理左子树inOrderThreadTree(node-left_node);if (node-left_node NULL){//设置前驱结点node-left_type 1;node-left_node pre;}//如果结点的右子节点为NULL 处理前驱的右指针if (pre !NULL pre-right_node NULL){//设置后继pre-right_node node;pre-right_type 1;}//每处理一个节点 当前结点是下一个节点的前驱pre node;//最后处理右子树inOrderThreadTree(node-right_node);
}
遍历
void inOrderTraverse(Node* root)
{//从根节点开始先找到最左边if (root NULL){return;}Node* temp root;//先找到最左边结点 然后根据线索化直接向右遍历while (temp ! NULL temp-left_type 0){temp temp-left_node;}while (temp ! NULL){//输出temp temp-right_node;}
}
这里停一下时间不多前驱后继就不写了哈
十、树、森林继二叉树的相互转换
1、树转换为二叉树
树转换成相应的二叉树分两个步骤:
在树中所有的兄弟结点之间加一连线对每个结点除了保留与其长子的连线外去掉该结点与其他孩子的连线
只有左子树 2、森林到二叉树的转换
森林转换为二叉树分两个步骤:
先将森林中的每棵树变为二叉树再将各二叉树的根结点视为兄弟从左至右连在一起就形成了一棵二叉树 3、二叉树到树、森林的转换
若结点x是其双亲y的左孩子则把x的右孩子右孩子的右孩子…,都与y用连线连起来。去掉所有双亲到右孩子之间的连线 4、树与森林的遍历
树的遍历分为两种方式:一种是先根遍历另一种是后根遍历。
先根遍历:先访问树的根结点然后再依次先根遍历根的每棵子树。后根遍历:先依次遍历每棵子树,然后再访问根结点。 先根遍历ABEFCGDHIJ
后根遍历EFBGCHIJDA 森林的遍历也分为前序遍历和后序遍历其实就是按照树的先根遍历和后根遍历依次访问森林的每一棵树。 我们的惊人发现:树、森林的前根序遍历和二叉树的前序遍历结果相同树、森林的后根序遍历和二叉树的中序遍历结果相同!
十一、哈夫曼树
1、定义
我们先把这两棵二叉树简化成叶子结点带权的二叉树注:树结点间的连线相关的数叫做权,Weight) 。 结点的路径长度:从根结点到该结点的路径上的连接数。 第一幅图C的就是3树的路径长度:树中每个叶子结点的路径长度之和。 第一幅图为1233 9结点带权路径长度:结点的路径长度与结点权值的乘积。 第一幅图C的就是3*70210树的带权路径长度:-WPL(Weighted Path Length)是树中所有叶子结点的带权路径长度之和。第一幅图为1*52*153*703*10 275
WPL的值越小说明构造出来的二叉树性能越优。
构造过程
1、构造森林全是根; 2、选用两小造新树;
3、删除两小添新人 ;4、重复2、3剩单根。 2、哈夫曼树的构建
结构体
//哈夫曼树结点结构
typedef struct {int weight;//结点权重int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
}HTNode, *HuffmanTree;
构建 //HT为地址传递的存储哈夫曼树的数组w为存储结点权重值的数组n为结点个数
void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
{if(n1) return; // 如果只有一个编码就相当于0int m 2*n-1; // 哈夫曼树总节点数n就是叶子结点*HT (HuffmanTree) malloc((m1) * sizeof(HTNode)); // 0号位置不用HuffmanTree p *HT;// 初始化哈夫曼树中的所有结点for(int i 1; i n; i){(pi)-weight *(wi-1);(pi)-parent 0;(pi)-left 0;(pi)-right 0;}//从树组的下标 n1 开始初始化哈夫曼树中除叶子结点外的结点for(int i n1; i m; i){(pi)-weight 0;(pi)-parent 0;(pi)-left 0;(pi)-right 0;}//构建哈夫曼树for(int i n1; i m; i){int s1, s2;Select(*HT, i-1, s1, s2);(*HT)[s1].parent (*HT)[s2].parent i;(*HT)[i].left s1;(*HT)[i].right s2;(*HT)[i].weight (*HT)[s1].weight (*HT)[s2].weight;}
}
3、重难点哈夫曼编码
1. 计算字符串中每个字符的频率
2. 按照字符出现的频率进行排序组成一个队列 Q
3. 把这些字符作为叶子节点开始构建一棵哈夫曼树
4. 对字符进行编码 哈夫曼树和编码都不唯一只有树的WPL(带权路径长度)才是唯一的
代码实现
#include stdio.h
#include stdlib.h// 定义哈夫曼树节点结构
typedef struct HuffmanNode {char data; // 字符int freq; // 频率struct HuffmanNode* left, * right; // 左右子节点
} HuffmanNode;// 定义优先级队列结构
typedef struct PriorityQueue {int size; // 队列当前大小int capacity; // 队列容量HuffmanNode** array; // 存储哈夫曼树节点的数组指针
} PriorityQueue;// 创建哈夫曼树节点
HuffmanNode* createNode(char data, int freq) {HuffmanNode* node (HuffmanNode*)malloc(sizeof(HuffmanNode)); // 分配内存空间node-data data; // 设置节点字符node-freq freq; // 设置节点频率node-left node-right NULL; // 初始化左右子节点为空return node; // 返回节点指针
}// 创建优先级队列
PriorityQueue* createPriorityQueue(int capacity) {PriorityQueue* queue (PriorityQueue*)malloc(sizeof(PriorityQueue)); // 分配内存空间queue-size 0; // 初始化队列大小为0queue-capacity capacity; // 设置队列容量queue-array (HuffmanNode**)malloc(queue-capacity * sizeof(HuffmanNode*)); // 分配内存空间return queue; // 返回队列指针
}// 交换两个节点
void swapNodes(HuffmanNode** a, HuffmanNode** b) {HuffmanNode* temp *a;*a *b;*b temp;
}// 向下堆化
void minHeapify(PriorityQueue* queue, int idx) {int smallest idx;int left 2 * idx 1; // 计算左子节点索引int right 2 * idx 2; // 计算右子节点索引// 找出三个节点中最小的节点if (left queue-size queue-array[left]-freq queue-array[smallest]-freq) {smallest left;}if (right queue-size queue-array[right]-freq queue-array[smallest]-freq) {smallest right;}// 如果最小节点不是当前节点交换节点并递归向下堆化if (smallest ! idx) {swapNodes(queue-array[idx], queue-array[smallest]);minHeapify(queue, smallest);}
}// 插入节点
void insertNode(PriorityQueue* queue, HuffmanNode* node) {queue-size; // 队列大小加1int i queue-size - 1; // 获取最后一个位置的索引queue-array[i] node; // 将节点插入最后一个位置// 如果插入节点的频率小于父节点的频率向上调整while (i queue-array[i]-freq queue-array[(i - 1) / 2]-freq) {swapNodes(queue-array[i], queue-array[(i - 1) / 2]);i (i - 1) / 2;}
}// 提取最小节点
HuffmanNode* extractMin(PriorityQueue* queue) {if (queue-size 0) return NULL; // 如果队列为空返回空指针HuffmanNode* root queue-array[0]; // 获取根节点queue-array[0] queue-array[queue-size - 1]; // 将最后一个节点移到根节点位置queue-size--; // 队列大小减1minHeapify(queue, 0); // 向下堆化return root; // 返回根节点
}// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(char data[], int freq[], int size) {PriorityQueue* queue createPriorityQueue(size); // 创建优先级队列// 将字符和频率构建成哈夫曼树节点并插入优先级队列中for (int i 0; i size; i) {insertNode(queue, createNode(data[i], freq[i]));}// 从优先级队列中不断取出最小的两个节点构建哈夫曼树直到队列中只剩一个节点while (queue-size ! 1) {HuffmanNode* left extractMin(queue);HuffmanNode* right extractMin(queue);// 创建新节点作为父节点频率为左右子节点频率之和HuffmanNode* top createNode(\0, left-freq right-freq);top-left left;top-right right;// 插入新节点到队列中insertNode(queue, top);}// 返回根节点return extractMin(queue);
}// 打印哈夫曼编码
void printHuffmanCodes(HuffmanNode* root, int arr[], int top) {// 遍历树生成编码if (root-left) {arr[top] 0;printHuffmanCodes(root-left, arr, top 1);}if (root-right) {arr[top] 1;printHuffmanCodes(root-right, arr, top 1);}// 当遍历到叶子节点时打印字符及其编码if (!root-left !root-right) {printf(%c: , root-data);for (int i 0; i top; i) {printf(%d, arr[i]);}printf(\n);}
}// 主函数
int main() {char data[] { a, b, c, d, e, f }; // 字符集合int freq[] { 5, 9, 12, 13, 16, 45 }; // 字符频率int size sizeof(data) / sizeof(data[0]); // 字符集合大小// 构建哈夫曼树HuffmanNode* root buildHuffmanTree(data, freq, size);int arr[100]; // 存储编码的数组int top 0; // 记录编码// 打印哈夫曼编码printf(哈夫曼编码:\n);printHuffmanCodes(root, arr, top);return 0;
}有点难啧我再想想
