网站做实名认证,白云区建网站设计,WordPress批量修改文章,阿帕奇建设网站博客二叉树详解 树的概念及其结构树的概念树的相关概念树的表示方法孩纸兄弟表示法双亲表示法#xff08;并查集#xff09; 树的实际应用 二叉树二叉树的概念二叉树的种类二叉树的性质二叉树的存储结构 二叉树顺序结构的实现堆的概念及结构堆向上、向下调整法堆的插入堆的删除堆… 二叉树详解 树的概念及其结构树的概念树的相关概念树的表示方法孩纸兄弟表示法双亲表示法并查集 树的实际应用 二叉树二叉树的概念二叉树的种类二叉树的性质二叉树的存储结构 二叉树顺序结构的实现堆的概念及结构堆向上、向下调整法堆的插入堆的删除堆的创建堆实现总代码建堆时间复杂度的证明堆排序TopK问题 二叉树链式结构的实现创建二叉树前序遍历及其实现中序遍历及其实现后序遍历及其实现销毁二叉树求二叉树的高度求二叉树总节点个数求二叉树叶子节点个数求二叉树第k层节点个数二叉树查找值为x的节点二叉树总代码实现层序遍历判断是否为二叉树总代码 铁汁们今天给大家分享一篇二叉树全面知识总结来吧开造⛳️ 树的概念及其结构
树的概念
树的概念是一种非线性的数据结构它由n个有限的节点组成的一个具有层次关系的集合。树的结构类似于真实世界中的树它看起来就像一颗倒挂着的树即它的根是朝上的而叶子是朝下的。 说明
1.有一个特殊的节点根节点该节点没有父节点前驱节点
2.根节点除外其他节点被分成了M个互不相交的集合{a1, a2, a3…},每个集合又是一颗结构类似的子树每个子树又可以被分成根节点、左子树、右子树——》递归思想把大事化小树是递归定义的
3.其他节点都有一个父节点前驱节点并且可以有零个或多个子节点后继节点。一个节点可以有一个或多个子节点但每个节点最多只能有一个父节点 ——》说明子树是不相交的。 注意树形结构中子树之间不能有交集否则就不是树形结构。 树的相关概念 树的表示方法
树形结构的线性表树在进行存储时既要保存值域也要保存各个节点之间的关系。
树的表示方法双亲表示法、孩纸兄弟表示法、孩纸表示法、孩纸双亲表示法等多叉树。
孩纸兄弟表示法
孩纸兄弟表示法让根节点指向第一个节点让第一个节点指向靠的最近的兄弟节点依次往后直到无兄弟节点和兄弟节点无第一个节点。
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.htypedef int DataType;typedef struct Node //孩纸兄弟表示法
{struct Node* firstchild; struct Node* secondchild;DataType val; //值域
}Node;int main()
{Node* parent; //从根节点开始Node* child parent-firstchild; //让根节点指向第一个节点while (child) {printf(%d , child-val);child child-secondchild; //第一个节点指向靠的最近的兄弟节点}return 0;
}双亲表示法并查集 //c实现代码#define _CRT_SECURE_NO_WARNINGS 1
#includeiostream //合并查集最基本版用来1.合并两个集合 2.查找两个数是否在一个集合内using namespace std;const int N 1e5 10;
//每个集合都用一个树来表示树的编号就是整个集合的编号每个数都有个树根。每个节点用来存储其父节点p[x]表示节点x的父节点
//判断每个集合的树根p[x] x
//求x的集合编号while(p[x] ! x) x p[x];
//将两个集合编号合并因px是x的集合编号py是y的集合编号p[x] y(让x所在的集合变为y所在集合的儿子或者p[y] x让y所在的集合变为x所在集合的儿子)
int p[N];int find(int x) //查找每个数的树根集合编号路径压缩因每个节点均向上找树根当一个节点找到了树根则该节点所在的路径上所有的点父节点直接等于树根
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}int main()
{int n, m;cin n m;for (int i 1; i n; i) p[i] i; //因每个数都在不同的集合中让集合的编号的本身p[x] x,树根while (m--){char op[2];int a, b;cin op a b;if (*op I) p[find(a)] find(b); //两个集合的合并else //判断两数所在的集合是否相同即判断树根值是否向他{if (find(a) find(b)) printf(YES\n); //相同else printf(NO\n); //不相同}}return 0;
}树的实际应用
树的应用用于表示文件系统的目录,表示方法为孩子兄弟法。 二叉树
二叉树的概念
二叉树定义是由有限节点组成的集合该集合可能为空空树或不为空由一个根节点加上左子树和右子树组成。 注意 1.二叉树度小于等于2。 2.二叉树不存在度大于2的节点。 3.二叉树有左、右子树之分次序不能颠倒所以二叉树也为有序树。 二叉树都是由以下几种情况的树复合而成的
二叉树的种类
特殊的二叉树满二叉树、完全二叉树。
1.满二叉树 一个二叉树每一层节点达到了最大值度等于2则这个二叉树为满二叉树。 注意满二叉树高度为h满二叉树总结点树为2^n-1个。 现实生活中的满二叉树 2.完全二叉树 二叉树深度为n,1.我是文本 红色red前n-1层结点数都要达到最大值度为2最后一层结点数不一定达到最大值但最后一层节点一定是从左到右排布的。完全二叉树是一种特殊的满二叉树。 注意完全二叉树的总结点个数范围为[ 2^(n-1), 2^n-1]。 二叉树的性质 题目
二叉树的存储结构
二叉树一般可分为两种结构存储,一种为顺序存储一种为链式存储。
1.顺序存储 顺序结构存储数据实质就是用数组来存储一般数组只适用于存储满二叉树、完全二叉树若存储普通的二叉树则会造成空间浪费堆、栈、顺序表均为顺序存储结构均用数组来存储数据。二叉树顺序存储在逻辑结构上是一颗二叉树想象出来的结构在 color red物理结构上是一个数组实际存在的)。 2.链式存储
二叉树链式存储 用链表来表示二叉树节点之间的逻辑关系通常链表中每个节点由三个域组成数据域和左、右指针域左、右指针域分别存储该节点的左、右孩子的地址根节点通过其左右子节点指针连接到左右子树子节点可以依次连接到它们的子树。链式结构又可以分为二叉链、三叉链。
二叉链 每个节点包含数据元素和指向左右子节点的指针。通过这个指针可以实现从子节点到父节点的访问。二叉链结构使得在树中的任意节点上能够直接访问其父节点方便进行反向操作。但要注意根节点的父节点指针为空。
三叉链 每个节点除了包含数据元素和指向左右子节点的指针之外还包含一个指向父节点的指针。三叉链结构使得在树中的任意节点上能够同时访问其父节点和子节点方便进行各种树的操作。
二叉树顺序结构的实现
堆的概念及结构
堆堆中所有的元素按完全二叉树的顺序全部存储到一维数组中当根节点的值左、右子树的根节点的值任意父亲节点值左、右孩纸节点的值则该堆为小堆当根节点的值左、右子树的根节点的值任意父亲节点值左、右孩纸节点的值则该堆为大堆。 注意堆的性质 1.任意父亲节点值(或者)左、右孩纸节点的值。 2.堆的逻辑结构为完全二叉树堆是一颗完全二叉树物理结构为数组。 堆向上、向下调整法
给出一个数组就可以画出其对应得完全二叉树通过向上或向下调整法可以将其调整为一个小堆。 向上、向下调整法使用前提左、右子树必须都为堆。 向上调整法从根节点的左结点开始从左到右依次调整每一层的所有节点形成堆。
void AdjustUp(HPDataType* a, int child) //使用前提左、右子树均为堆向上调整从根节点的左结点开始数据从上往下依次向上调整形成堆
{int parent (child - 1) / 2; //父亲节点找父亲节点while (child 0) //{if (a[child] a[parent]) //该节点与父节点值进行比较swap(a[child], a[parent]); //交换形成小堆child parent; //递归parent (child - 1) / 2;}
}向下调整法从最后一个非叶子节点开始数据从下往上依次向下调整每个节点形成堆。
void AdjustDown(int* a, int n, int parent) //使用前提根的左、右子树均为堆向下调整从最后一个非叶子节点开始数据从下往上依次向下调整形成堆
{int child parent * 2 1; //孩纸节点初始化左孩子值比右孩纸值小找孩纸节点while (child n) //{if (child 1 n a[child] a[child 1]) //左、右孩纸值进行比较确保右孩纸存在且左孩子值比右孩纸值大swap(a[child], a[child 1]); //交换此时child节点中的值为孩纸节点的最小值if (a[child] a[parent]) //左孩子值与父节点值进行比较swap(a[child], a[parent]); //交换形成小堆parent child; //递归child parent * 2 1;}
}堆的插入
思路将数据直接插入到最后一个位置新插入的元素在向上调整。
void HeapPush(Heap* hp, HPDataType x) //向堆中插入一个元素
{assert(hp); //断言不能对空指针进行加、减、解引用操作if (hp-size hp-capacity) //空间满了不能进行插入数据如需插入数据需要realloc进行扩容{int newcapacity hp-capacity 0 ? 4 : hp-capacity * 2; //新容量HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * newcapacity); if (tmp NULL) //realloc开辟失败{perror(realloc failed);exit(-1);}hp-a tmp; //realloc开辟成功hp-capacity newcapacity; //容量进行更新为新容量}hp-a[hp-size] x; //在末尾插入一个元素hp-size;AdjustUp(hp-a, hp-size - 1); //在将新插入的元素进行向上调整形成堆
}堆的删除
思路将堆中最后一个元素覆盖堆顶元素堆顶元素在向下调整。
void HeapPop(Heap* hp) //删除堆顶元素
{assert(hp); //断言不能对空指针进行加、减、解引用操作hp-a[0] hp-a[hp-size-1]; //将最后一个元素覆盖堆顶元素hp-size--; AdjustDown(hp-a, hp-size, 0); //在将堆顶元素进行向下调整形成堆
}堆的创建
void HeapCreat(Heap* hp, int* b, int n) //建堆堆的创建
{assert(hp b); //断言不能对空指针进行加、减、解引用操作hp-a (HPDataType*)malloc(sizeof(HPDataType) * n); //malloc动态开辟数组空间 if (hp-a NULL) //malloc动态开辟失败{perror(malloc failed);exit(-1); //异常退出终止程序非0值表示不正常退出0表示正常退出}memcpy(hp-a, b, sizeof(HPDataType) * n); //此处需要将已知的数组建成堆将数组中所有值拷贝给动态开辟的数组hp-size hp-capacity n; for (int i (n-2)/2; i 0; i--) //向下调整法建堆从倒数第一个非叶子节点开始调整层数依次向上每层从右到左遍历每个节点每个节点都向下调整AdjustDown(hp-a, n, i);
}堆实现总代码
Heap.h#pragma once //用数组来模拟实现堆顺序表实现#includestdio.h
#includestdlib.h //malloc
#includeassert.h //assert
#includestring.h //memcpytypedef int HPDataType; typedef struct HeapNode //动态版
{HPDataType* a; //malloc动态开辟数组空间存储每个节点的值int size; //表示堆中实际有效节点的总个数int capacity; //容量
}Heap;//传址调用此处只需要改变结构体中的成员变量只需要传结构体的地址形参为一级指针顺序表若需要改变结构体的地址则形参为二级指针单链表。void HeapCreat(Heap* hp, int* b, int n); //建堆堆的创建void HeapPush(Heap* hp, HPDataType x); //向堆中插入一个元素void HeapDestory(Heap* hp); //销毁void HeapPop(Heap* hp); //删除堆顶元素HPDataType HeapTop(Heap* hp); //获取堆顶元素int HeapSize(Heap* hp); //获取堆中有效节点的总个数int HeapEmpty(Heap* hp); //判断堆是否为空void HeapPrint(Heap* hp); //打印堆中节点的值Heap.c#define _CRT_SECURE_NO_WARNINGS 1#includeHeap.hvoid swap(int* p1, int* p2) //交换两元素的值传址调用传值调用形参的改变不会影响实参的改变
{int tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustDown(int* a, int n, int parent) //使用前提根的左、右子树均为堆向下调整从最后一个非叶子节点开始数据从下往上依次向下调整形成堆
{int child parent * 2 1; //孩纸节点初始化左孩子值比右孩纸值小while (child n) //{if (child 1 n a[child] a[child 1]) //左、右孩纸值进行比较确保右孩纸存在且左孩子值比右孩纸值大swap(a[child], a[child 1]); //交换此时child节点中的值为孩纸节点的最小值if (a[child] a[parent]) //左孩子值与父节点值进行比较swap(a[child], a[parent]); //交换形成小堆parent child; //递归child parent * 2 1;}
}void AdjustUp(HPDataType* a, int child) //使用前提左、右子树均为堆向上调整从根节点的左结点开始数据从上往下依次向上调整形成堆
{int parent (child - 1) / 2; //父亲节点while (child 0) //{if (a[child] a[parent]) //该节点与父节点值进行比较swap(a[child], a[parent]); //交换形成小堆child parent; //递归parent (child - 1) / 2;}
}void HeapCreat(Heap* hp, int* b, int n) //建堆堆的创建
{assert(hp b); //断言不能对空指针进行加、减、解引用操作hp-a (HPDataType*)malloc(sizeof(HPDataType) * n); //malloc动态开辟数组空间 if (hp-a NULL) //malloc动态开辟失败{perror(malloc failed);exit(-1); //异常退出终止程序非0值表示不正常退出0表示正常退出}memcpy(hp-a, b, sizeof(HPDataType) * n); //此处需要将已知的数组建成堆将数组中所有值拷贝给动态开辟的数组hp-size hp-capacity n; for (int i (n-2)/2; i 0; i--) //向下调整法建堆从倒数第一个非叶子节点开始调整层数依次向上每层从右到左遍历每个节点每个节点都向下调整AdjustDown(hp-a, n, i);
}void HeapPush(Heap* hp, HPDataType x) //向堆中插入一个元素
{assert(hp); //断言不能对空指针进行加、减、解引用操作if (hp-size hp-capacity) //空间满了不能进行插入数据如需插入数据需要realloc进行扩容{int newcapacity hp-capacity 0 ? 4 : hp-capacity * 2; //新容量HPDataType* tmp (HPDataType*)realloc(hp-a, sizeof(HPDataType) * newcapacity); if (tmp NULL) //realloc开辟失败{perror(realloc failed);exit(-1);}hp-a tmp; //realloc开辟成功hp-capacity newcapacity; //容量进行更新为新容量}hp-a[hp-size] x; //在末尾插入一个元素hp-size;AdjustUp(hp-a, hp-size - 1); //在将新插入的元素进行向上调整形成堆
}void HeapDestory(Heap* hp) //销毁
{assert(hp);//断言不能对空指针进行加、减、解引用操作free(hp-a); //释放malloc动态开辟的空间hp-a NULL; //防止该空间被其他变量存储了该地址通过该地址访问此空间不能访问已经释放的空间会造成野指针hp-size hp-capacity 0;
}void HeapPop(Heap* hp) //删除堆顶元素
{assert(hp); //断言不能对空指针进行加、减、解引用操作hp-a[0] hp-a[hp-size-1]; //将最后一个元素覆盖堆顶元素hp-size--; AdjustDown(hp-a, hp-size, 0); //在将堆顶元素进行向下调整形成堆
}HPDataType HeapTop(Heap* hp) //获取堆顶元素
{return hp-a[0];
}int HeapSize(Heap* hp) //获取堆中有效节点的总个数
{return hp-size;
}int HeapEmpty(Heap* hp) //判断堆是否为空为空则为true,不为空则为false
{if (hp-size 0) return 0;else return 1;
}void HeapPrint(Heap* hp) //打印堆中节点的值
{assert(hp);for (int i 0; i hp-size; i) //遍历堆中元素通过数组的下标来遍历完全二叉树中的每个节点printf(%d , hp-a[i]);printf(\n);
}
Test.c#define _CRT_SECURE_NO_WARNINGS 1
#pragma once#includeHeap.hint main()
{Heap hp;int b[4] { 3, 2, 1 ,4};int n sizeof(b) / sizeof(int);HeapCreat(hp, b, n);HeapPrint(hp);for (int i 0; i 5; i){int x;scanf(%d, x);HeapPush(hp, x);}HeapPrint(hp);HeapPop(hp);HeapPrint(hp);printf(%d\n, HeapTop(hp));printf(%d\n, HeapSize(hp));if (HeapEmpty(hp))printf(YES\n);elseprintf(NO\n);HeapDestory(hp);return 0;
}建堆时间复杂度的证明 堆排序 注意在进行堆排序建堆时升序建大堆、 降序建小堆。 原因堆排序是为了对数组进行排序不是进行打印数组便于进行其他一系列操作。
排升序如果建小堆只可以第一次获得最小的数若要将剩余的元素进行排升序只能将剩余的元素看成个堆但各个元素对应的节点之间的关系已全部打乱需要将剩余的元素重新建成堆代价太大时间复杂度为O(n*longn)。
排升序建大堆将第一个最大的数与最后一个元素进行交换个数减1在从剩余的n-1个找出次大的数在与最后一个元素交换个数减1如此反复时间复杂度为O(nlong)。
#define _CRT_SECURE_NO_WARNINGS 1
#includestdio.hvoid swap(int* p1, int* p2) //传址调用形参的改变会影响实参的改变
{int tmp *p1;*p1 *p2;*p2 tmp;
}void down(int* a, int n, int parent) //向下调整法建堆建大堆
{int child parent * 2 1; //左孩纸节点while (child n) //边界{if (child 1 n a[child] a[child 1])//找到左孩纸与右孩纸节点中的最大值swap(a[child], a[child 1]);if(a[parent] a[child]) //建大堆swap(a[child], a[parent]);parent child; //循环处理child parent * 2 1;}
}void Heapsort(int* a, int n) //堆排序对数组进行排序升序建大堆
{for (int i (n - 2) / 2; i 0; i--) //向下调整法建堆从下标为i-1-1)/2的节点开始down(a, n, i);int end n - 1; //最后一个元素所对应的下标值while (end 0){swap(a[0], a[end]); //堆中最大的树与最后一个树进行交换down(a, end, 0); //将剩余的n-1个元素建大堆end--;}for (int i 0; i 6; i) printf(%d , a[i]);}int main()
{int a[6];for (int i 0; i 6; i)scanf(%d, a[i]);Heapsort(a, sizeof(a) / sizeof(int)); //堆排序return 0;
}TopK问题
TopK问题
求数据中的前k个大的数或者前k个小的数该数据个数的范围非常的大一般情况是建个堆但在内存中不能一次性将所有数据全部加载到内存中此时考虑将数据存入文件中即在文件中找TopK问题实际应用场景世界前500名富豪游戏中前100名活跃的玩家等。 在文件中找前K个大的数 1.将所有数据先存入文件中去在从文件中读取建成前K个数小堆。 2.在依次将文件中剩余的数据读取每读取一个数分别与堆中第一个树进行比较比它大两数据值进行交换该数往下沉建成小堆如此反复最终堆中的K个数为文件中最大的前K个数。 #define _CRT_SECURE_NO_WARNINGS 1
#includestdio.h
#includestdlib.h //malloc, srand
#includetime.h //time(时间戳void swap(int* p1, int* p2) //传址调用
{int tmp *p1;*p1 *p2;*p2 tmp;
}void AdjustDown(int* a, int n, int parent) //使用前提根的左、右子树均为堆向下调整从最后一个非叶子节点开始数据从下往上依次向下调整形成堆
{int child parent * 2 1; //孩纸节点初始化左孩子值比右孩纸值小while (child n) //{if (child 1 n a[child] a[child 1]) //左、右孩纸值进行比较确保右孩纸存在且左孩子值比右孩纸值大swap(a[child], a[child 1]); //交换此时child节点中的值为孩纸节点的最小值if (a[child] a[parent]) //左孩子值与父节点值进行比较swap(a[child], a[parent]); ///交换形成小堆parent child; //递归child parent * 2 1;}
}void CreatNData() //在文件中创造数据
{int n 100000;const char* file data.txt; FILE* fin fopen(file, w); //以写的方式将文件打开if (fin NULL) //文件打开失败{perror(fopen failed);exit(-1); //异常退出终止程序负数}for (int i 0; i n; i) //创造n个随机数{int x rand() % 10000; //数据值得范围为0~9999fprintf(fin, %d\n, x); //将n个树写到文件中%d\n,每个数据占一行}fclose(fin); //关闭文件
}/*思路一、从文件中读出k个数据放在数组中fscanf有格式将k个数建成小堆不可以是大堆最大的数据会堵在堆顶不下去
* 二、依次将文件中剩余的n-k个数据读取过来与堆顶进行比较大于则往下沉
* 此时堆中剩余的k个数为最大的前k个数且为升序
*/
void HeapTopK(int k) //topk
{const char* file data.txt;FILE* fout fopen(file, r); //以读的方式将文件打开if (file NULL) //文件打开失败{perror(fopen failed);exit(-1); //异常退出终止程序负数}//一、从文件中读出k个数据放在数组中fscanf有格式将k个数建成小堆不可以是大堆最大的数据会堵在堆顶不下去int* mink (int*)malloc(sizeof(int) * k); //malloc创造一个动态数组用来存储文件中的前k个数if (mink NULL) //malloc开辟失败{perror(malloc failed);exit(-1);//异常退出终止程序负数}for (int i 0; i k; i) //从文件中读出k个数据fscanf(fout, %d, mink[i]); for (int i (k-2)/2; i 0; i--)//将k个数建成小堆AdjustDown(mink, k, i);// 二、依次将文件中剩余的n - k个数据读取过来与堆顶进行比较大于则往下沉int x 0;while (fscanf(fout, %d, x) ! EOF)//将文件中剩余的n - k个数据读取{ //fscanf返回值为读取的个数读取失败或者读取为NULL,则返回EOF~EOF(-1 0)if (x mink[0]) //与堆顶进行比较大于则往下沉mink[0] x;AdjustDown(mink, k, 0);}for (int i 0; i k; i)printf(%d , mink[i]);free(mink); //释放malloc动态开辟的空间mink NULL;fclose(fout); //关闭文件
}int main()
{srand((unsigned int)time(NULL)); //生成随机数srand~time~rand//CreatNData(); //创造数据int k;scanf(%d, k); //topkHeapTopK(k);return 0;
}二叉树链式结构的实现
创建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* i) //由前序遍历将数组中的值创建二叉树
{ if (a[*i] #) // #代表空节点{(*i); //数组向后走一位构建下一个节点return NULL; }BTNode* root (BTNode*)malloc(sizeof(BTNode)); //malloc动态开辟内存创建新节点if (root NULL) //malloc动态开辟失败{perror(malloc failed); exit(-1); //终止程序异常退出0表示正常退出非0表示异常退出}root-val a[*i]; //数组中值不为空将该值赋给新节点(*i); //数组向后走一位构建下一个节点//该节点的左、右节点均创建完成该节点在其左、右节点进行链接root-left BinaryTreeCreate(a, n, i); //递归处理创建左节点左节点遇到空递归结束root-right BinaryTreeCreate(a, n, i); //递归处理创建右节点右节点遇到空递归结束return root; //返回树的根节点
}前序遍历及其实现
void BinaryTreePrevOrder(BTNode* root) //前序遍历根、左、右
{if (root NULL) //空树return ;printf(%c , root-val); //根BinaryTreePrevOrder(root-left); //递归处理左BinaryTreePrevOrder(root-right); //递归处理右
} 中序遍历及其实现
void BinaryTreeInOrder(BTNode* root) //中序遍历左、根、右
{if (root NULL) //空树return;BinaryTreeInOrder(root-left); //递归处理左printf(%c , root-val); //根BinaryTreeInOrder(root-right); //递归处理右
} 后序遍历及其实现
void BinaryTreePostOrder(BTNode* root) //后序遍历左、右、根
{if (root NULL) //空树return;BinaryTreePostOrder(root-left); //递归处理左BinaryTreePostOrder(root-right); //递归处理右printf(%c , root-val); //根
}销毁二叉树
/*采用后序遍历不可采用前序遍历原因销毁根节点之前需要存储左子树的根便于可以找到左子树也需要存储右子树的根便于可以找到右子树*/
void BinaryTreeDestory(BTNode* root) //销毁后序遍历
{if (root NULL) //空树,未动态开辟任何节点return;BinaryTreeDestory(root-left); //递归处理左BinaryTreeDestory(root-right); //递归处理右free(root); //销毁根
}求二叉树的高度
int BinaryTreeHeight(BTNode* root) //树的高度
{if (root NULL) //空树return 0;int leftheight BinaryTreeHeight(root-left); //左子树的高度int rightheight BinaryTreeHeight(root-right); //右子树的高度return leftheight rightheight ? leftheight 1 : rightheight 1; //找出左、右子树高度大的树根1
}求二叉树总节点个数
int BinaryTreeSize(BTNode* root) //树的总节点个数分治法、递归法将其分为根、左子树、右子树对应的子树又可以分成根、左、右子树
{if (root NULL) //空树return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1; //左子树的节点右子树的节点根节点1
}求二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root) //树中叶子节点的个数分治法、递归法将其分为根、左子树、右子树对应的子树又可以分成根、左、右子树
{if (root NULL) //空树return 0;if (root-left NULL root-right NULL) //叶子节点的特征该左、右节点均为空则该节点为叶子节点return 1;return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); //左子树叶子节点个数右子树叶子节点个数
}求二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k) //树中第k层节点的总个数将第k层转换为1层将k-1层转换为第2层..直到k1则为第k层
{if (root NULL) //空树return 0;if (k 1) //第k层return 1; return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) //在树中查找是否存在值为x的节点
{if (root NULL) //空树return 0;if (root-val x) //找到了return root;BTNode* ret NULL; ret BinaryTreeFind(root-left, x); //递归左子树if (ret) //若左子树找到了直接返回return ret;ret BinaryTreeFind(root-right, x); //左子树找不到在找右子树if (ret) //右子树找到了直接返回return ret;return NULL; //找不到
}
二叉树总代码实现
BinaryTree.h#define _CRT_SECURE_NO_WARNINGS 1#includestdio.h
#includestdlib.h //malloc
#includestring.h //strlentypedef char BTDataType; //二叉树节点值的类型适用于任意数据类型typedef struct BinaryTreeNode //树中的节点
{struct BinaryTreeNode* left; //指针域左孩纸struct BinaryTreeNode* right; //右孩纸BTDataType val; //数据域
}BTNode;BTNode* BinaryTreeCreate(BTDataType* a, int n, int* i); //由前序遍历将数组中的值创建二叉树void BinaryTreePrevOrder(BTNode* root);//前序遍历根、左、右void BinaryTreeInOrder(BTNode* root); //中序遍历左、根、右void BinaryTreePostOrder(BTNode* root); //后序遍历左、右、根void BinaryTreeDestory(BTNode *root); //销毁int BinaryTreeHeight(BTNode* root); //树的高度int BinaryTreeSize(BTNode* root); //树的总节点个数int BinaryTreeLeafSize(BTNode* root); //树中叶子节点的个数int BinaryTreeLevelKSize(BTNode* root, int k); //树中第k层节点的总个数BTNode* BinaryTreeFind(BTNode* root, BTDataType x); //在树中查找是否存在值为x的节点
BinaryTree.c#define _CRT_SECURE_NO_WARNINGS 1#includeBinaryTree.hBTNode* BinaryTreeCreate(BTDataType* a, int n, int* i) //由前序遍历将数组中的值创建二叉树
{ if (a[*i] #) // #代表空节点{(*i); //数组向后走一位构建下一个节点return NULL; }BTNode* root (BTNode*)malloc(sizeof(BTNode)); //malloc动态开辟内存创建新节点if (root NULL) //malloc动态开辟失败{perror(malloc failed); exit(-1); //终止程序异常退出0表示正常退出非0表示异常退出}root-val a[*i]; //数组中值不为空将该值赋给新节点(*i); //数组向后走一位构建下一个节点//该节点的左、右节点均创建完成该节点在其左、右节点进行链接root-left BinaryTreeCreate(a, n, i); //递归处理创建左节点左节点遇到空递归结束root-right BinaryTreeCreate(a, n, i); //递归处理创建右节点右节点遇到空递归结束return root; //返回树的根节点
}void BinaryTreePrevOrder(BTNode* root) //前序遍历根、左、右
{if (root NULL) //空树return ;printf(%c , root-val); //根BinaryTreePrevOrder(root-left); //递归处理左BinaryTreePrevOrder(root-right); //递归处理右
}void BinaryTreeInOrder(BTNode* root) //中序遍历左、根、右
{if (root NULL) //空树return;BinaryTreeInOrder(root-left); //递归处理左printf(%c , root-val); //根BinaryTreeInOrder(root-right); //递归处理右
}void BinaryTreePostOrder(BTNode* root) //后序遍历左、右、根
{if (root NULL) //空树return;BinaryTreePostOrder(root-left); //递归处理左BinaryTreePostOrder(root-right); //递归处理右printf(%c , root-val); //根
}
/*采用后序遍历不可采用前序遍历原因销毁根节点之前需要存储左子树的根便于可以找到左子树也需要存储右子树的根便于可以找到右子树*/
void BinaryTreeDestory(BTNode* root) //销毁后序遍历
{if (root NULL) //空树,未动态开辟任何节点return;BinaryTreeDestory(root-left); //递归处理左BinaryTreeDestory(root-right); //递归处理右free(root); //销毁根
}int BinaryTreeSize(BTNode* root) //树的总节点个数分治法、递归法将其分为根、左子树、右子树对应的子树又可以分成根、左、右子树
{if (root NULL) //空树return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1; //左子树的节点右子树的节点根节点1
}int BinaryTreeLeafSize(BTNode* root) //树中叶子节点的个数分治法、递归法将其分为根、左子树、右子树对应的子树又可以分成根、左、右子树
{if (root NULL) //空树return 0;if (root-left NULL root-right NULL) //叶子节点的特征该左、右节点均为空则该节点为叶子节点return 1;return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); //左子树叶子节点个数右子树叶子节点个数
}int BinaryTreeLevelKSize(BTNode* root, int k) //树中第k层节点的总个数将第k层转换为1层将k-1层转换为第2层..直到k1则为第k层
{if (root NULL) //空树return 0;if (k 1) //第k层return 1; return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}BTNode* BinaryTreeFind(BTNode* root, BTDataType x) //在树中查找是否存在值为x的节点
{if (root NULL) //空树return 0;if (root-val x) //找到了return root;BTNode* ret NULL; ret BinaryTreeFind(root-left, x); //递归左子树if (ret) //若左子树找到了直接返回return ret;ret BinaryTreeFind(root-right, x); //左子树找不到在找右子树if (ret) //右子树找到了直接返回return ret;return NULL; //找不到
}int BinaryTreeHeight(BTNode* root) //树的高度
{if (root NULL) //空树return 0;int leftheight BinaryTreeHeight(root-left); //左子树的高度int rightheight BinaryTreeHeight(root-right); //右子树的高度return leftheight rightheight ? leftheight 1 : rightheight 1; //找出左、右子树高度大的树根1
}Test.c#define _CRT_SECURE_NO_WARNINGS 1#includeBinaryTree.hint main()
{BTDataType arr[] ABD##E#H##CF##G##; int n strlen(arr);int j 0;BTNode* root BinaryTreeCreate(arr, n, j); //由前序遍历将数组中的值创建二叉树BinaryTreePrevOrder(root); //前序遍历printf(\n);BinaryTreeInOrder(root); //中序遍历printf(\n);BinaryTreePostOrder(root); //后序遍历printf(\n);printf(%d\n, BinaryTreeHeight(root)); //树的高度printf(%d\n,BinaryTreeSize(root)); //树的总节点个数printf(%d\n, BinaryTreeLeafSize(root)); //树中叶子节点的个数printf(%d\n, BinaryTreeLevelKSize(root, 3)); //树中第k层节点的总个数BTNode* ret BinaryTreeFind(root, F); //在树中查找是否存在值为x的节点if (ret ! NULL) printf(找到了\n); elseprintf(找不到\n);BinaryTreeDestory(root); //销毁return 0;
} 层序遍历 void BinaryTreeLevelOrder(BTNode* root) //层次遍历用队列实现上一层带下一层当上一层节点全部出队则下一层所有节点均入队了
{Queue plist;QueueInit(plist); //初始化队列队列中用于存储树中的节点if (root NULL) //空树return;QueuePush(plist, root); //将根插入队列中while (!QueueEmpty(plist)) //{BTNode* front QueueFront(plist); //获取队头元素printf(%d , front-val); //打印树中节点的值if (front-left) //左孩纸不为空空节点不能入队QueuePush(plist, front-left); //将该节点的左孩子入队if (front-right) //右孩纸不为空空节点不能入队QueuePush(plist, front-right); //将该节点的右孩子入队QueuePop(plist); //删除队头元素}printf(\n);QueueDestroy(plist); //二叉树的销毁
}判断是否为二叉树 int BinaryTreeComplete(BTNode* root) //判断其是否为二叉树最后一层非空节点从左到右连续分布
{Queue plist;QueueInit(plist); //初始化队列队列中用于存储树中的节点if (root NULL) //空树return;QueuePush(plist, root); //将根插入队列中while (!QueueEmpty(plist)) //{BTNode* front QueueFront(plist); //获取队头元素if (front NULL) //队头为空节点break;QueuePush(plist, front-left); //左孩纸入队空节点也需入队QueuePush(plist, front-right); //右孩纸入队空节点也需入队QueuePop(plist); //删除非空节点}while (!QueueEmpty(plist)) //{BTNode* front QueueFront(plist); //获取队头元素QueuePop(plist); //删除队头节点if (front ! NULL) //队头为非空节点{QueueDestroy(plist); return false; //不是完全二叉树}QueuePop(plist); //删除队头节点}QueueDestroy(plist); //销毁return true; //是完全二叉树printf(\n);
}总代码
Tset.c#define _CRT_SECURE_NO_WARNINGS 1#includeQueue.h/*void test()
{Queue plist;QueueInit(plist);QueuePush(plist, 1);QueuePush(plist, 2);QueuePush(plist, 3);QueuePush(plist, 4);QueuePush(plist, 5);QueuePush(plist, 6);while (!QueueEmpty(plist)){printf(%d , QueueFront(plist));QueuePop(plist);}printf(\n);QueueDestroy(plist);
}int main()
{test(); //测试队列先进先出return 0;
}
*/
BTNode* BuyNode(int x)
{BTNode* root (BTNode*)malloc(sizeof(BTNode));root-left NULL;root-right NULL;root-val x;return root;
}void BinaryTreeLevelOrder(BTNode* root)
{Queue plist;QueueInit(plist);if (root NULL)return;QueuePush(plist, root);while (!QueueEmpty(plist)){BTNode* front QueueFront(plist);printf(%d , front-val);if (front-left)QueuePush(plist, front-left);if (front-right)QueuePush(plist, front-right);QueuePop(plist);}printf(\n);QueueDestroy(plist);
}int BinaryTreeComplete(BTNode* root)
{Queue plist;QueueInit(plist);if (root NULL)return;QueuePush(plist, root);while (!QueueEmpty(plist)){BTNode* front QueueFront(plist);if (front NULL)break;QueuePush(plist, front-left);QueuePush(plist, front-right);QueuePop(plist);}while (!QueueEmpty(plist)){BTNode* front QueueFront(plist);QueuePop(plist); //if (front ! NULL){QueueDestroy(plist);return false;}QueuePop(plist);}QueueDestroy(plist);return true;printf(\n);
}int main()
{BTNode* n1 BuyNode(1);BTNode* n2 BuyNode(6);BTNode* n3 BuyNode(7);BTNode* n4 BuyNode(2);BTNode* n5 BuyNode(3);BTNode* n6 BuyNode(4);BTNode* n7 BuyNode(5);n1-left n2;n1-right n3;n2-left n4;n2-right n5;n3-left n6;n3-right n7;BinaryTreeLevelOrder(n1);if (BinaryTreeComplete(n1))printf(是完全二叉树\n);elseprintf(不是完全二叉树\n);return 0;
}
Queue.c#define _CRT_SECURE_NO_WARNINGS 1#includeQueue.hvoid QueueInit(Queue* p) //初始化
{assert(p); //断言检查指针的有效性防止对空指针进行解引用加减操作p-front NULL;p-rear NULL;p-size 0;
}void QueuePush(Queue* p, QDataType x) //入队
{assert(p); //断言检查指针的有效性防止对空指针进行解引用加减操作QNode* newnode(QNode*)malloc(sizeof(QNode)); //malloc动态开辟新的节点if (newnode NULL) //开辟空间失败{perror(malloc); //报错原因exit(-1); //终止程序异常结束}newnode-data x; newnode-next NULL;if (p-rear NULL) //注意头插特殊处理链表为空{p-front p-rear newnode;}else //尾插 需要找尾节点{p-rear-next newnode; p-rearp-rear-next;}p-size; //链表中有效元素个数加
}bool QueueEmpty(Queue* p) //判断队列是否为空
{assert(p); //断言检查指针的有效性防止对空指针进行解引用加减操作return p-front NULL; //为空则为真返回非0值若不为空为假则返回0
}void QueuePop(Queue* p) //出队
{assert(p); //断言检查指针的有效性防止对空指针进行解引用加减操作assert(!QueueEmpty(p)); //断言链表为空则不能进行删除 if (p-front-next NULL) //注意当链表中只剩一个元素因为尾指针、头指针同时指向该节点释放该节点需要将尾指针、头指针都置成NULL,否则会造成野指针指向已经被释放的空间{free(p-front);p-front p-rear NULL;}else //链表中剩余至少有1个元素{QNode* next p-front-next;free(p-front);p-front next;}p-size--; //链表中有效元素个数加-
}QDataType QueueFront(Queue* p) //获取队头元素
{assert(p); //断言检查指针的有效性防止对空指针进行解引用加减操作assert(!QueueEmpty(p)); //断言链表为空则不能获取到队头的元素return p-front-data;
}QDataType QueueBack(Queue* p) //获取队尾元素
{assert(p); //断言检查指针的有效性防止对空指针进行解引用加减操作assert(!QueueEmpty(p)); //断言链表为空则不能获取到队尾的元素return p-rear-data;
}int QueueSize(Queue* p) //获取队列中有效元素的个数
{assert(p); //断言检查指针的有效性防止对空指针进行解引用加减操作assert(!QueueEmpty(p)); //断言链表为空则不能获取到有效元素的总个数return p-size;
}void QueueDestroy(Queue* p) //销毁
{assert(p); //断言检查指针的有效性防止对空指针进行解引用加减操作while (p-front) //遍历链表{QNode* next p-front-next;free(p-front);p-front next;}p-front p-rear NULL;p-size 0;
}Queue.h#define _CRT_SECURE_NO_WARNINGS 1#includestdio.h
#includestdlib.h //malloc
#includeassert.h //assert
#includestdbool.h //bool类型typedef struct BinaryTreeNode* QDataType;typedef int BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;
}BTNode;typedef struct QueueNode //链式结构表示队列
{QDataType data; struct QueueNode* next;
}QNode;typedef struct Queue //队列结构
{QNode* front; //队头QNode* rear; //队尾int size; //有效元素个数
}Queue;void QueueInit(Queue* p); //初始化
void QueuePush(Queue* p, QDataType x); //入队
void QueuePop(Queue* p); //出队
QDataType QueueFront(Queue* p); //获取队头元素
QDataType QueueBack(Queue* p); //获取队尾元素
int QueueSize(Queue* p); //获取队列中有效元素的个数
bool QueueEmpty(Queue* p); //判断队列是否为空
void QueueDestroy(Queue* p); //销毁铁铁们二叉数全面知识总结就到此结束啦若博主有不好的地方请指正欢迎铁铁们留言请动动你们的手给作者点个鼓励吧你们的鼓励就是我的动力✨
