【初阶数据结构】 左右逢源的分支诗律 二叉树3

1. 遍历方式

1. 层序遍历

OJ层序遍历

在这里题目本身是要判断是否是完全二叉树,回顾一下完全二叉树性质是除了最后一层其他层全满,最后一层节点靠左依次排列中间不能有空缺位置,在这里我们怎么思考这个问题呢?
不论什么情况只要不是完全二叉树,她一定会有一个空节点在非空节点的前面,因为NULL会比最后一个节点先入队列

入队列过程

检查非空节点我这里列出来了两种情况,一种完全二叉树,一种非完全二叉树

bool isCompleteTree(struct TreeNode* root) {     Queue q; QueueInit(&q); QueuePush(&q,root);     while (!QueueEmpty(&q)) { TreeNode*front = QueueFront(&q); QueuePop(&q);            if(front==NULL)            {                break;            } QueuePush(&q, front->left); QueuePush(&q, front->right); }    while (!QueueEmpty(&q))    {        TreeNode*front = QueueFront(&q);        QueuePop(&q);        if(front)        {            return false;        }    } return true; }

有小伙伴不想自己写队列的可以直接复制这里代码,然后做题,我把`队列代码也列在这里
可看看直接调用即可

queue代码

typedef struct TreeNode TreeNode; typedef struct TreeNode* QDataType; typedef struct QNode { struct QNode* next; QDataType x; }QNode; typedef struct Queue { QNode* ptail; QNode* phead; int size; }Queue; void QueueInit(Queue* pq) { assert(pq); pq->ptail = pq->phead = NULL; pq->size = 0; } void QueueDestory(Queue* pq) { assert(pq); while (pq->phead) { QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; } pq->ptail =pq->phead = NULL; pq->size = 0; //当queue是malloc的结构体才要free在函数外面 //free(pq); //pq } void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("newnode malloc fail"); } newnode->next = NULL; newnode->x = x; if (pq->phead == NULL) { pq->phead = pq->ptail = newnode; pq->size++; } else { pq->ptail->next = newnode; pq->ptail = newnode; pq->size++; } } void QueuePop(Queue* pq) { assert(pq && pq->size > 0); if (pq->size == 1) { pq->ptail = NULL; } QNode* next = pq->phead->next; free(pq->phead); pq->phead = next; pq->size--; } QDataType QueueFront(Queue* pq) { assert(pq && pq->size > 0); return pq->phead->x; } QDataType QueueBack(Queue* pq) { assert(pq && pq->size > 0); return pq->ptail->x; } bool QueueEmpty(Queue* pq) { return pq->size == 0; } int QueueSize(Queue* pq) { return pq->size; } void QueuePrint(Queue* pq) { assert(pq && pq->size > 0); QNode* cur = pq->phead; while (cur) { printf("%d ", cur->x); cur = cur->next; } }

2. 前序遍历

在第一期我们讲过了二叉树的前序中序后序遍历,但是那只是打印数据,并没有存储数据
这一期我们将学习将遍历的数据在数组里存起来,并返回

OJ前序遍历

前序遍历,二叉树1讲得比较清楚,这里我就不做赘述,主要讲讲返回值
int* returnSize
这里是指的是数组大小,你返回一个数组,不知道数组大小很容易访问越界,不知道有多少个数据
int* preorderTraversal
这里返回的就是装有遍历序列的数组

//前序遍历 void PrevOrder(BTNode* root, int* a, int* pi) { if (root == NULL) { return ; } //存根节点数据 a[*pi] = root->val; (*pi)++; PrevOrder(root->left, a, pi); PrevOrder(root->right, a, pi); } //计算数组大小 int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right)+1; } int* preorderTraversal(BTNode* root, int* returnSize) { if (root == NULL) { return NULL; } *returnSize = TreeSize(root); int* a = (int*)malloc((*returnSize)*sizeof(int)); int i = 0; PrevOrder(root, a, &i); return a; }

后面两种遍历方式代码如下:(自取)

3. 中序遍历

OJ中序遍历

void InOrder(BTNode* root, int* a, int* pi) { if(root==NULL)    {        return;    } InOrder(root->left, a, pi);      a[*pi]=root->val;    (*pi)++; InOrder(root->right, a, pi); } int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right)+1; } int* inorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = TreeSize(root); int* a = (int*)malloc((*returnSize)*sizeof(int));    if (root == NULL) { return NULL; } int i = 0; InOrder(root, a, &i); return a; }

4. 后序遍历

OJ后序遍历

void BackOrder(BTNode* root, int* a, int* pi) { if(root==NULL)    {        return;    } BackOrder(root->left, a, pi); BackOrder(root->right, a, pi);    a[*pi]=root->val;    (*pi)++; } int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right)+1; } int* postorderTraversal(struct TreeNode* root, int* returnSize) { *returnSize = TreeSize(root); int* a = (int*)malloc((*returnSize)*sizeof(int));    if (root == NULL) { return NULL; } int i = 0; BackOrder(root, a, &i); return a; }

2. 二叉树的创建

当然这里的题目还要难点你还要进行中序遍历,前面有不做赘述
OJ二叉树的创建与遍历
在这里由于篇幅我只做了左树的遍历

typedef struct BnariyTree { char val; struct BnariyTree* left; struct BnariyTree* right; }BTNode; BTNode* CreatTree(int* pi,char* a) { if (a[*pi] == '#') { return NULL; } BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); } node->val = a[*pi]; (*pi)++; node->left = CreatTree(pi, a); (*pi)++; node->right = CreatTree(pi, a); return node; }

3. 二叉树的销毁

先销毁左子树再销毁右子树再销毁根节点

void DestoryTree(BTNode* root) { if (root == NULL) { return; } DestoryTree(root->left); DestoryTree(root->right); free(root); }

最优二叉树(哈夫曼树)

哈夫曼树，又称最优二叉树，是一类带权路径长度 WPL 最小的二叉树，由 David A. Huffman 于 1952 年提出，核心用于数据压缩（哈夫曼编码）。
这里简单提一提,
一开始会再一个集合里面放一堆节点数为1的二叉树组成一个的森林
数值大小就称作他的权,数值越大,权越大

选取两个数值每次选取根节点大小最小的两颗二叉树,根节点求和,和的值做为权当新的根节点,合成新的二叉树

哈夫曼树为什么叫最优二叉树?
因为他都是两两合成根节点,没有度为1的节点
哈夫曼编码
你可以自己定向 左为0,向右为1
这样每一个节点都只有唯一的编码

在这里原来集合里的节点为1个的二叉树,都会有唯一编码,注意这里只有度为0的节点才有编码,也就是原集合中的节点编码
哈夫曼编码

编码长度可以不同但是
1>:0000 3>:001
2>:0001 4>:01