国外网站设计师,郑州新闻头条最新消息,做照片模板下载网站好,wordpress用户中心在创作不易#xff0c;友友们给个三连吧#xff01;#xff01;
一、前言 前期我们解释过二叉树的顺序结构#xff08;堆#xff09;为什么比较适用于完全二叉树#xff0c;因为如果用数组来实现非完全二叉树#xff0c;那么数组的中间部分就可能会存在大量的空间浪费。 … 创作不易友友们给个三连吧
一、前言 前期我们解释过二叉树的顺序结构堆为什么比较适用于完全二叉树因为如果用数组来实现非完全二叉树那么数组的中间部分就可能会存在大量的空间浪费。 而二叉树的链式结构即用链表结构来存储二叉树这里就没有什么限制了所有的二叉树都可以用链式结构来存储因为链式结构存在两个指针分别指向自己的左右孩子无论是少了左孩子还是少了右孩子只需要让相应的指针指向NULL就可以了。 虽然链式结构可以表示所有类型的二叉树但是由于二叉树本身存储数据的价值并不大链表、顺序表远远优于二叉树所以实现增删查改是没有太大意义的学习链式二叉树真正的意义是学会如何去控制、遍历二叉树的结构为我们后期学习搜索二叉树做好铺垫。而以下的学习中要重点理解二叉树中的递归思想和分治思想 !
二、链式二叉树的实现
2.1 节点结构体的创建 创建的方式和单链表的很相似唯一的区别就是要有两个指针一个指向自己的左孩子一个指向自己的右孩子
typedef int BTDataType;//方便我们后面要存储其他类型的数据的时候方便修改
typedef struct BinaryTreeNode
{BTDataType data;//二叉树节点的数据域struct BinaryTreeNode* left;//左孩子struct BinaryTreeNode* right;//右孩子
}BTNode;2.2 二叉树节点的创建 二叉树节点构建方式和单链表节点的构建方式相同
BTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL)//如果创建不成功{perror(malloc fail);exit(1);}//如果创建成功newnode-data x;newnode-left newnode-right NULL;return newnode;
}
2.3 前序遍历
为了能够深入前中后续遍历我们先手动创建一个二叉树后面都按照这个二叉树来研究 下面我先给出前中后续的遍历结果再逐个分析要注意没有箭头默认指向空 分析前序 前序的顺序是根、左子树、右子树首先1是根接着访问1的左子树2,2也是根再访问2的左子树33也是根再访问3的左子树N接着访问3的右子树N回归到2对于2来说他的左子树已经访问完了然后访问右子树N回归1对于1来说他的左子树已经访问完了该访问他的右子树4了4是根接着访问4的左子树5,5也是根接着访问5的左子树N再访问5的右子树N然后回归5对于4来说左子树访问完了接着访问6,6的左子树是N然后访问6的右子树N。此时所有节点都访问完了。 大家可以看看上面的图我画的框框1这个根右边的2 3 N N N 和4 5 N N 6 N N 分别表示1的左右子树而对于2这个根来说3 N N 和 N分别代表2的左右子树对于4这个根来说5 N N和6 N N分别代表4的左右子树对于3、5、6 这三个根来说他们的左右子树都是N和N。 那么怎么写前序遍历的代码呢根据上一段的思路我们可以发现对于根1来说他的左子树是以2为根的树他的右子树是以4为根的树而对于2来说他的左子树是以3为根的树右子树是N对于4来说他的左子树是以5为根的树他的右子树是以6为根的树 而对于3、5、6来说他们其实也是根左右子树都是N。所以将问题转化为递归问题。
void PreOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}
画一下递归展开图 时间复杂度是ON 因为每个节点都遍历了一次
空间复杂度也是Oh 通过上图可以看出当开辟h个的函数栈帧后后续的空间都是在前一个空间释放后复用的所以最多同时只有h个栈帧空间被开辟根据空间可以重复利用的特点空间复杂度是oN!
中序遍历和后序遍历的方法是一样的后面就不分析了
2.4 中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}
2.5 后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}
2.6 层序遍历 层序遍历是一层一层遍历之前无论是前序、中序、还是后序遍历都是根据父子关系父亲会指向自己的左右孩子转化成递归问题去遍历的 但是链式二叉树的指针指向并不指向兄弟节点所以这边如果要一层一层遍历需要用到队列。 选择队列的原因是利用队列队头出队尾进的特点下面进行分析 Queue.h void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)//如果不为NULL就进队列QueuePush(q, root);while (!QueueEmpty(q))//队列为空就是遍历完成{BTNode* front QueueFront(q);//让每一次循环过来的节点变成根部再去访问左右子树QueuePop(q);//记录完一个元素就出队列printf(%d , front-data);if(front-left)QueuePush(q, front-left);//左节点不为空进队列if (front-right)QueuePush(q, front-right);//右节点不为空进队列}printf(\n);//遍历完了就可以销毁队列了QueueDestory(q);
}
2.7 二叉树节点个数 我们先按照按照军棋里的模式来解释分治思想 假设军长要统计总人数有两个方法一个是军长一级一级去视察数人这显然是效率比较低的 而另一个方法就是分而治之——利用自己的职权将任务移交给下级军长把任务分配给两个旅长然后旅长统计过来的人数加上自己就是全军人数旅长又分配给连长将两个连长统计的人数加上自己就是全旅人数以此类推…… int BinaryTreeSize(BTNode* root)
{return root NULL ? 0 : BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}
2.8 二叉树叶子节点个数 还是利用分治思想叶子节点的特征是左右子树都为NULL我们还是按照分治思想将这个任务拆分下去 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);
}
2.9 二叉树第k层节点
还是利用分治思想将求第k层节点转化为求左子树的k-1层节点加上右子树的k-1层节点。 int BinaryTreeLevelKSize(BTNode* root,int k)
{if (root NULL)return 0;if (k 1)return 1;return BinaryTreeLevelKSize(root-left,k-1) BinaryTreeLevelKSize(root-right,k-1);
}
2.10 二叉树的高度
还是利用分治思想求高度转化为比较左右子树的大小再1 int BinaryTreeHeight(BTNode* root)
{if (root NULL)return 0;return BinaryTreeHeight(root-left) BinaryTreeHeight(root-right) ? BinaryTreeHeight(root-left) 1 : BinaryTreeHeight(root-right) 1;
} 其实这样写是有问题的因为每次我递归比较完后并没有记录最大值所以导致每次递归的时候最大值都得再重新递归一次如果树节点高度特别高的话就很可能会出现这样的问题。 改进版
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;
}所以我们在递归时使用三目表达式要注意如果比较的过程已经递归一次了比较的结果就不要再去递归了可以及时的记录值
2.11 二叉树查找值为x的节点
还是利用分治思想,转化为在左子树和右子树中找 BTNode* BTFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 BTFind(root-left, x);if (ret1)return ret1;BTNode* ret2 BTFind(root-right, x);if (ret2)return ret2;return NULL;
}
2.12 通过前序遍历数组构建二叉树 之前我们构建二叉树是一个节点一个节点去手动连接这次我们尝试自己利用前序遍历数组去构建二叉树比如abc##de#g##f### BTNode* BTCreate(char*arr,int*pi)
{if (arr[*pi] #){(*pi);return NULL;}BTNode* root BuyNode(arr[*pi]);(*pi);root-left BTCreate(arr, pi);root-right BTCreate(arr, pi);return root;
} 递归展开图 2.13 二叉树销毁 二叉树要销毁就要遍历每个节点因为我们如果先销毁根那么就很可能找不到他的左子树和右子树了除非销毁根之前记录一下但是这样比较麻烦所以我们选择后序遍历先销毁左子树再销毁右子树再销毁根。
void BTDestory(BTNode* root)
{if (root NULL)return;BTDestory(root-left);BTDestory(root-right);free(root);//root NULL;没用
}
注意这里的参数是一级指针而root本身也是指针所以在这里对root置NULL是没有意义的所以要使用的话要在main函数中手动置空这里不用二级指针的原因是为了保持接口一致性
2.14 判断二叉树是否是完全二叉树 完全二叉树的特点就是前h-1层是满的最后一层从前往后要到最后才会访问到NULL所以们可以分析一下他的特点 bool BTComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);//记录该结果然后再pop出去QueuePop(q);if (front NULL)break;QueuePush(q, root-left);QueuePush(q, root-right);}//跳出循环后检查后面的节点是不是还有非空节点有的话就是非完全二叉树while (!QueueEmpty(q)){BTNode* front QueueFront(q);//记录该结果然后再pop出去QueuePop(q);if (front){QueueDestory(q);//队列一定别忘了销毁return false;}QueueDestory(q);return true;}
} 2.15 判断两颗二叉树是否完全相同
我们还是用分治思想前序遍历比较 bool IsBTSame(BTNode* root1, BTNode* root2)
{if (root1 NULL root2 NULL)return true;if (root1 NULL || root2 NULL)return false;//此时节点肯定不为NULL了可以解引用找到valif (root1-data ! root2-data)return false;//不相等的话只能去找自己的左右子树左右子树都返回true最后结果才能返回truereturn IsBTSame(root1-left, root2-left) IsBTSame(root1-right, root2-right);
}
三、链式二叉树实现的全部代码
前两个文件只是因为层序遍历和判断完全二叉树会用到重点还是看后面两个文件
3.1 queue.h
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
struct BinaryTreeNode;//为了防止嵌套调用这里声明一下
typedef struct BinaryTreeNode* QDatatype;//方便后面修改存储数据的数据类型
typedef struct QueueNode//队列结点的数据结构
{QDatatype data;//存储数据struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;//指向队头用于出队头删QNode* ptail;//指向队尾用于入队尾插int size;//记录有效元素个数
}Queue;//创建一个队列相关结构体
void QueueInit(Queue* pq);//队列的初始化
void QueuePush(Queue* pq, QDatatype x);//队列的入队尾插
void QueuePop(Queue* pq);//队列的出队(头删)
QDatatype QueueFront(Queue* pq);//获取队列头部元素
QDatatype QueueBack(Queue* pq);//获取队列尾部元素
int QueueSize(Queue* pq);//获取队列中有效元素个数
bool QueueEmpty(Queue* pq);//判断队列是否为空
void QueueDestory(Queue* pq);//队列的销毁3.2 queue.c
#includeQueue.h
void QueueInit(Queue* pq)
{assert(pq);//判断传的是不是空指针pq-phead pq-ptail NULL;pq-size 0;//因为队列不像栈一样有一个top表示栈顶元素的下标//所以如果我们想知道这个队列的有效数据个数就必须遍历队列//由于其先进先出的特性我们默认只能访问到头元素和尾元素//所以必须访问一个头元素就出队列一次这样才能实现遍历//但是这样的代价太大了为了方便我们直接用size
}void QueuePush(Queue* pq, QDatatype x)
{assert(pq);//入队必须从队尾入QNode* newnode (QNode*)malloc(sizeof(QNode));//创建一个新节点if (newnodeNULL)//如果新节点申请失败退出程序{perror(malloc fail);}//新节点创建成功给新节点初始化一下newnode-data x;newnode-next NULL;//开始入队//如果直接尾插的话由于会用到ptail-next,所以得考虑队列为空的情况if (pq-ptail NULL)//如果为空直接把让新节点成为phead和ptail{//按道理来说如果ptail为空phead也应该为空// 但是有可能会因为我们的误操作使得phead不为空这个时候一般是我们写错的问题//所以使用assert来判断一下有问题的话会及时返回错误信息assert(pq-phead NULL);pq-phead pq-ptail newnode;}else{pq-ptail-next newnode;pq-ptail newnode;}pq-size;
}void QueuePop(Queue* pq)
{assert(pq);//如果队列为空没有删除的必要assert(!QueueEmpty(pq));//队列中的出队列相当于链表的头删//如果直接头删那么如果队列只有一个有效数据的话那么我们将phead的空间释放掉但是没有将ptail给置空//这样会导致ptail成为一个野指针所以我们需要考虑只有一个节点多个节点的情况if (pq-phead-next NULL)//一个节点的情况,直接将这个节点释放并置空即可{free(pq-phead);pq-phead pq-ptail NULL;//置空防止野指针}else//多个节点的情况直接头删{QNode* next pq-phead-next;//临时指针记住下一个节点free(pq-phead);pq-phead next;//让下一个节点成为新的头}pq-size--;
}QDatatype QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//队列如果为空则不可能找得到队列头元素//队列不为空的时候直接返回phead指向的数据return pq-phead-data;
}QDatatype QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));//队列如果为空则不可能找得到队尾元素//队列不为空的时候直接返回ptail指向的数据return pq-ptail-data;
}int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}bool QueueEmpty(Queue* pq)//链表为空的情况可以根据容量也可以根据ptailNULLpheadNULL
{assert(pq);return pq-ptail NULL pq-phead NULL;
}void QueueDestory(Queue* pq)
{assert(pq);//判断传的是不是空指针//要逐个节点释放QNode* pcur pq-phead;while (pcur){QNode* next pcur-next;free(pcur);pcur next;}pq-phead pq-ptail NULL;pq-size 0;
}3.3 BT.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
#includeQueue.h
typedef int BTDataType;//方便我们后面要存储其他类型的数据的时候方便修改
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x);
void PreOrder(BTNode* root);//前序遍历
void InOrder(BTNode* root);//中序遍历
void PostOrder(BTNode* root);//后序遍历
void LevelOrder(BTNode* root);//层序遍历
int BTSize(BTNode* root);//二叉树节点个数
int BTLeafSize(BTNode* root);//二叉树的叶子节点个数
int BTLevelKSize(BTNode* root, int k);//二叉树第k层的节点个数
int BTHeight(BTNode* root);//二叉树的高度
BTNode* BTFind(BTNode* root, BTDataType x);//二叉树找值为x的点
BTNode* BTCreate(char* arr,int*pi);//根据前序数组创建二叉树
void BTDestory(BTNode* root);//销毁二叉树
bool BTComplete(BTNode* root);//判断是否完全二叉树
bool IsBTSame(BTNode* root1, BTNode* root2);//判断两个二叉树是否完全相等3.4 BT.c
#includeBTtree.hBTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL)//如果创建不成功{perror(malloc fail);exit(1);}//如果创建成功newnode-data x;newnode-left newnode-right NULL;return newnode;
}void PreOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)//如果不为NULL就进队列QueuePush(q, root);while (!QueueEmpty(q))//队列为空就是遍历完成{BTNode* front QueueFront(q);//让每一次循环过来的节点变成根部再去访问左右子树QueuePop(q);//记录完一个元素就出队列printf(%d , front-data);if(front-left)QueuePush(q, front-left);//左节点不为空进队列if (front-right)QueuePush(q, front-right);//右节点不为空进队列}printf(\n);//遍历完了就可以销毁队列了QueueDestory(q);
}int BTSize(BTNode* root)
{return root NULL ? 0 : BTSize(root-left) BTSize(root-right) 1;
}int BTLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL)return 1;return BTLeafSize(root-left) BTLeafSize(root-right);
}int BTLevelKSize(BTNode* root,int k)
{if (root NULL)return 0;if (k 1)return 1;return BTLevelKSize(root-left,k-1) BTLevelKSize(root-right,k-1);
}int BTHeight(BTNode* root)
{if (root NULL)return 0;int LeftHeight BTHeight(root-left);int RightHeight BTHeight(root-right);return LeftHeight RightHeight ? LeftHeight 1 : RightHeight 1;
}BTNode* BTFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-data x)return root;BTNode* ret1 BTFind(root-left, x);if (ret1)return ret1;BTNode* ret2 BTFind(root-right, x);if (ret2)return ret2;return NULL;
}BTNode* BTCreate(char*arr,int*pi)
{if (arr[*pi] #){(*pi);return NULL;}BTNode* root BuyNode(arr[*pi]);(*pi);root-left BTCreate(arr, pi);root-right BTCreate(arr, pi);return root;
}void BTDestory(BTNode* root)
{if (root NULL)return;BTDestory(root-left);BTDestory(root-right);free(root);//root NULL;没用
}bool BTComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);//记录该结果然后再pop出去QueuePop(q);if (front NULL)break;QueuePush(q, root-left);QueuePush(q, root-right);}//跳出循环后检查后面的节点是不是还有非空节点有的话就是非完全二叉树while (!QueueEmpty(q)){BTNode* front QueueFront(q);//记录该结果然后再pop出去QueuePop(q);if (front){QueueDestory(q);//队列一定别忘了销毁return false;}QueueDestory(q);return true;}
}bool IsBTSame(BTNode* root1, BTNode* root2)
{if (root1 NULL root2 NULL)return true;if (root1 NULL || root2 NULL)return false;//此时节点肯定不为NULL了可以解引用找到valif (root1-data ! root2-data)return false;//不相等的话只能去找自己的左右子树左右子树都返回true最后结果才能返回truereturn IsBTSame(root1-left, root2-left) IsBTSame(root1-right, root2-right);
}
