网站建设逻辑,网站订制公司,做网站和做系统有什么区别,网站建设助手 西部数码二叉树 前言引入二叉树——二叉树的独特之处一、二叉树的结构 的 核心思想二、二叉树的代码实现binary tree.h binary tree.c#xff08;一#xff09;手动构建二叉树 测试用#xff08;二#xff09;二叉树销毁#xff08;三#xff09;节点个数#x… 二叉树 前言引入二叉树——二叉树的独特之处一、二叉树的结构 的 核心思想二、二叉树的代码实现binary tree.h binary tree.c一手动构建二叉树 测试用二二叉树销毁三节点个数四二叉树第k层节点个数五 二叉树查找值为x的节点 — 前序遍历(六) 二叉树前序遍历(七) 二叉树中序遍历(八) 二叉树后序遍历(九) 层序遍历—— 队列实现 深度优先遍历 和 广度优先遍历深度优先遍历DFS广度优先遍历BFS 十判断二叉树是否是完全二叉树十一树的高度十二前序遍历 构建二叉树 test.c 前言
引入二叉树——二叉树的独特之处
在学习二叉树之前我们已经学习了从最开始的顺序表到后面的栈和队列再到堆然后就到了我们现在的二叉树
我们前面学习了堆及其结构所带来的性质
堆根据其性质我在【数据结构】二叉树的顺序结构及实现理论学习篇这篇博客里详细的讲述了堆的性质大家可通过此篇来掌握可得到 min 或 max 值 从而解决TopK问题此问题也在前面的链接的那篇文章中有讲述
既然堆结构有这样的作用和意义那么请大家思考一个问题二叉树结构真正的意义是什么 在对于数据的存储方面数据结构的增删查改 在二叉树结构中插入数据倒不如直接用顺序表实现的二叉树结构的本质-顺序表去直接存储数据来的方便 但在二分查找数据并删除数据 时 顺序表要先排序成有序遍历一遍数组时间复杂度是O(N^2)且找到想要的数据并且想要实现删插数据的功能时顺序表的数据需要挪动时间复杂度是O(N)而链表实现的二叉树 则不用挪动数据通过堆的性质构建出有一定性质结构的二叉树根据这些性质结构通过中序遍历二叉树可快速找出想要的数据时间复杂度是ON*logN 由此可见普通的链式二叉树没有意义 而我们现在学习普通链式二叉树重点不在于对其数据的增删查改而是在于通过学习二叉树的结构以及其性质为后面更复杂的 搜索二叉树AVL红黑树等 打下基础。 一、二叉树的结构 的 核心思想
二叉树的结构的核心思想就是 —— 递归 而 递归的本质 就在于 将一个复杂庞大的问题 逐步分解成 模式一样、最小规模 的子问题 分治层层分包
递归代码逻辑运行的理解 函数栈帧的创建和销毁 建议大家先去了解一下 函数栈帧的创建和销毁的运行机制
谨记函数递归返回的不是最外层而是上一层
树的结构本来就是递归结构所以更适合用递归来实现 二、二叉树的代码实现
binary tree.h
#pragma once#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includeassert.h
#includestdbool.htypedef int BTDataType;typedef struct BinaryTreeNode {BTDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;// 二叉树销毁
void BinaryTreeDestory(BTNode* root);// 二叉树节点个数
int BinaryTreeSize(BTNode* root);// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);binary tree.c
一手动构建二叉树 测试用
手动构建二叉树 —— 保存成文本文件记录这段代码用于下一次检测二叉树代码的正确性的样本打造自己的 代码库。 自己画二叉树的图顺着图来链接各节点就好。
//创建树节点
BTNode* BuyNode(BTDataType x) {BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL) {perror(malloc fail);exit(-1);}node-val x;node-left NULL;node-right NULL;return node;
}int main() {//手动构建二叉树 —— 保存成文本文件记录这段代码用于下一次检测二叉树代码的正确性的样本打造自己的代码库BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);BTNode* node7 BuyNode(7);BTNode* node8 BuyNode(8);BTNode* node9 BuyNode(9);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;node2-right node7;node3-left node8;node6-right node9}二二叉树销毁
前序也可以只是要用两个临时的指针变量去存放root-left 和 root-right 这两个节点的地址避免释放内存后找不到下一节点的指针了
// 二叉树销毁 —— 后序递归递到最深处逐层往回归释放内存 //前序也可以只是要用两个临时的指针变量去存放root-left 和 root-right 这两个节点的地址避免释放内存后找不到下一节点的指针了
void BinaryTreeDestroy(BTNode* root) { //一级指针形参 不影响实参if (root NULL) //递归返回的条件碰到NULL就开始返回了return;BinaryTreeDestory(root-left);BinaryTreeDestory(root-right); //递到最深处free(root);//rootNULL; //思考这里将root节点置空有用吗}思考这里将root节点置空有用吗 答BinaryTreeDestroy用于接收的只是一级指针接收到的只是root节点里面的内容所以只是root的一份临时拷贝形参 置空要到外面才能滞空。 三节点个数
先行版
// 节点个数
int TreeSize(BTNode* root)
{int size 0; //思考这样 int size会出现什么问题if (root NULL)return 0;elsesize;TreeSize(root-left);TreeSize(root-right);return size;
}int size 0; // 思考这样 int size会出现什么问题 每次函数调用递归int size都为0无法做到记数的作用。
static局部变量版 //节点个数
int TreeSize(BTNode* root)
{static int size 0;if (root NULL)return 0;elsesize;TreeSize(root-left);TreeSize(root-right);return size;
}static int size0; // 局部的静态变量的初始化 只会执行一次只会在第一次调用时执行后面就不会再初始化为0了
【关于static的知识点补充后在后续补充到时候会把链接放这里敬请期待】
也正是因为static有这样的特性 引出问题下一次再想调用这个函数会出现什么情况 下一次再调用时static修饰的变量并未被销毁还存放上一次调用函数的数据并且在作用域外也没有办法对static局部变量进行修改
解决方面如下方版本改为 定义全局变量在下一次调用函数之前初始化一下
一路记数下去版
int size0;//定义全局变量//节点个数
int BinaryTreeSize(BTNode* root) {if (root NULL)return 0;elsesize;BinaryTreeSize(root-left);BinaryTreeSize(root-right);return size;
}递归版
// 二叉树节点个数
int size0;//定义全局变量int BinaryTreeSize(BTNode* root) {if (root NULL)return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right)1;}更优化的写法
int BinaryTreeSize(BTNode* root) {// 若根节点为空空则返回0否则返回 BinaryTreeSize(root-left) BinaryTreeSize(root-right)1return rootNULL?0:BinaryTreeSize(root-left) BinaryTreeSize(root-right)1;}四二叉树第k层节点个数
核心思想 root的第k层相对与root-left,root-right的第k-1层。
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k) {assert(k 0);if (root 0)return 0;if (k 1) //当k1时到第k层了return 1;//root的第k层相对与root-left,root-right的第k-1层return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}五 二叉树查找值为x的节点 — 前序遍历
思路就是先遍历左子树左子树找不到再去找右子树。
// 二叉树查找值为x的节点 前序遍历
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) //空树 递归返回的条件return NULL;if (root-val x)return root;BTNode* ret NULL; //用一个指针变量来保存返回的指针ret BinaryTreeFind(root-left, x); if (ret) //如果ret不为空则返回retreturn ret;ret BinaryTreeFind(root-right, x); //ret为空则继续遍历右子树if (ret)return ret;return NULL;
}也是根据这样的思路有的同学可能会出现这样的错误
// 二叉树查找值为x的节点 前序遍历
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) //空树 递归返回的条件return NULL;if (root-val x)return root;return BinaryTreeFind(root-left, x) || BinaryTreeFind(root-right, x) //如果左子树找到了就不用再遍历右子树了
}思考一下这样会导致什么问题。
解析逻辑运算符|| 逻辑或 。确实是能做到 判断左边若为true则结束判断。 但判断完了其返回的是数C语言中判断真假非0为真0则为假而不是 函数返回类型 BTNode* BinaryTreeFind (BTNode* root, BTDataType x) 中的BTNode* 。返回的就不是指针了。
【关于 逻辑或 || 运算符 的知识点补充后在后续补充到时候会把链接放这里敬请期待】 (六) 二叉树前序遍历
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root) {if (root NULL) {printf(NULL);return;}printf(%d, root-val);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);
}(七) 二叉树中序遍历
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root) {if (root NULL) {printf(NULL);return;}BinaryTreeInOrder(root-left);printf(%d, root-val);BinaryTreeInOrder(root-right);
}(八) 二叉树后序遍历
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root) {if (root NULL) {printf(NULL);return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%d, root-val);
}(九) 层序遍历—— 队列实现
队列先进先出
核心思路上一层带下一层
需要包含Queue.h Queue.c 文件
// 层序遍历—— 队列实现
void BinaryTreeLevelOrder(BTNode* root) {Que q;QueueInit(q);if(root)QueuePush(q, root); //存放头节点的地址QNode里的data存放地址值while (!QueueEmpty(q)) {BTNode* front QueueFront(q); //取出用BTNode*来保存 //取头节点读取printf头节点printf(%d,front-val);if (front-left) //再顺带把其下一层带上QueuePush(q, front-left);if (front-right)QueuePush(q,front-right);QueuePop(q); //再排出其左节点}printf(\n);QueueDestroy(q);
}学习完 二叉树的 前、中、后序遍历 以及 层序遍历 我们来介绍两个概念
深度优先遍历 和 广度优先遍历
深度优先遍历DFS
广义前、中、后序遍历都是都往深走只是访问节点的时机不同严格前序先递归到最深处才往回走
广度优先遍历BFS
层序遍历 [ 队列配合 ] 非递归 十判断二叉树是否是完全二叉树
完全二叉树前n-1层都是满的最后一层不满但是连续的 非完全二叉树非空节点不连续中间有空节点 要录空不然看不出来
核心判断条件层序遍历录到空后若后面还有节点剩下的若不为空则说明是非二叉树。
// 层序遍历进阶应用——判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root) {Que q;QueueInit(q);if (root ! NULL)QueuePush(q,root);while(!QueueEmpty(q)) {BTNode* front QueueFront(q); //因为传入的是BTNode的地址从队列中取出也需要BTNode*if (front NULL) //遇空开始判断后面是否还有节点break;QueuePush(q, front-left);QueuePush(q, front-right);QueuePop(q);}// 已经遇到空节点如果队列中后面的节点还有非空就不是完全二叉树while (!QueueEmpty(q)) {BTNode* front QueueFront(q); //挨个判断剩下的节点是否都为空都为空则为完全二叉树QueuePop(q);if (front ! NULL) {QueueDestroy(q);return false;}}QueueDestroy(q);return true;
} 十一树的高度
核心思路对比左树和右树的高度大的那一棵的高度1 。
先行版
//树的高度
int TreeHeight(BTNode* root) {if (root NULL)return 0;return TreeHeight(root-left) TreeHeight(root-right) ? TreeHeight(root-left) 1 : TreeHeight(root-right) 1;
}这样会存在什么问题是否高效
虽然使用的是三目运算符使代码更简洁但代码运行是否高效并不是看你代码简不简洁而是要看你计算机到底要跑多久多少次。你人是爽了但你电脑也快跑死了。
☆★存在的问题 return TreeHeight(root-left) TreeHeight(root-right) ? TreeHeight(root-left) 1 : TreeHeight(root-right) 1;
前半部分 TreeHeight(root-left) TreeHeight(root-right) ,递归计算出 leftTreeHeight 和 rightTreeHeight 。 但由于递归计算完后并没有变量将其递归结果进行保存 判断出来结果后再进行 TreeHeight(root-left) 1 的运算又展开一次深度递归进行运算 。
这样进行了大量的重复计算本来递归要进行的计算就多了计算还要重复的。 改良版 根据这个问题进行改良将递归结果用变量进行保存 。
//树的高度 —— 优化版
int TreeHeight(BTNode* root) {if (root NULL)return 0;int leftHeight TreeHeight(root-left);int rightHeight TreeHeight(root-right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;
}fmax 版本
int fmax(int x,int y) {if (x y)return x;elsereturn y;
}//树的高度 —— 终版
int TreeHeight(BTNode* root) {if (root NULL)return 0;return fmax(TreeHeight(root-left), TreeHeight(root-right)) 1; //TreeHeight(root-left)在传过去之前就已经计算出结果并将结果用int x形参接收储存。
}运行结果
手动构建的二叉树 十二前序遍历 构建二叉树
// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(char* str, int* pi) {if (str[*pi]#) {(*pi);return NULL;}BTNode* root (BTNode*)BuyNode(str[(*pi) ]);root-left BinaryTreeCreate(str, pi);root-right BinaryTreeCreate(str, pi);}int main() {char a[] ABD##E#H##CF##G##;int i 0;int size sizeof(a) / sizeof(a[0]);BinaryTreeCreate(a,i);} test.c
int main()
{// 手动构建BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;PrevOrder(node1);printf(\n);InOrder(node1);printf(\n);PostOrder(node1);printf(\n);printf(%d\n, TreeSize(node1));//size 0;printf(%d\n, TreeSize(node1));TreeDestroy(node1);node1 NULL;return 0;
}
