西安网站建设 盈科,wordpress主题柚子皮,科技创新绘画作品图片,句容建设质检站网站在二叉树(中)了解了堆的相关概念后还实现了堆#xff0c;并且还实现了堆排序#xff0c;以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构#xff0c;会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树#xff0c;接下来就开始本篇的学习吧…在二叉树(中)了解了堆的相关概念后还实现了堆并且还实现了堆排序以及解决了TOP-K问题。接下来在本篇中将继续学习二叉树中的链式结构会学习二叉树中的前、中、后三种遍历并实现链式结构的二叉树接下来就开始本篇的学习吧 1.链式二叉树的结构
要实现链式结构的二叉树首先就要将二叉树的结构设计好也就是要将二叉树结点的结构设计好要将各结点关联起来通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 其结构如下
typedef int BTDataType;
// 二叉树链式结构
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;}BTNode;在实现链式结构的二叉树的程序中是将程序的文件分为以下三个文件 2.二叉树的创建
由于在实现链式结构的二叉树中不同于堆一样都是完全二叉树因此这就使得二叉树的结构较为多样这时我们就不再去像前面顺序结构的二叉树一样实现插入删除等功能直接手动的创建一个二叉树该函数的返回值就为二叉树的根结点
BTNode* CreateTree()
{BTNode* node1 NewNode(1);BTNode* node2 NewNode(2);BTNode* node3 NewNode(3);BTNode* node4 NewNode(4);BTNode* node5 NewNode(5);node1-left node2;node1-right node3;node2-left node4;node2-right node5;return node1;
} 3. 前中后序遍历
在实现了链式二叉树的结构后接下来就可以来实现二叉树的前中后序遍历在此之前先来了解前中后序遍历的概念 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历 1前序遍历(Preorder Traversal 亦称先序遍历)访问根结点的操作发生在遍历其左右树之前 访问顺序为根结点、左子树、右子树 2中序遍历(Inorder Traversal)访问根结点的操作发生在遍历其左右子树之中间访问顺序为左子树、根结点、右子树 3后序遍历(Postorder Traversal)访问根结点的操作发生在遍历其左右子树之后访问顺序为左子树、右子树、根结点 来通过以下的二叉树示例来进一步理解以上的遍历规则前序遍历 在以上图示的二叉树中若要进行前序遍历则先要访问跟结点A之后再访问A的左结点B之后访问B的左结点D再访问D的左节点再访问D的右结点因为D的左节点和右结点都为NULL所以返回去访问B的右结点因为B的右结点为NULL所以返回去访问A的右结点C之后访问C的左结点E再访问E的左节点再访问E的右结点因为E的左节点和右结点都为NULL所以返回去访问F结点
因此通过以上分析就可以得出前序遍历结果为 A B D C E F
中序遍历: 在以上图示的二叉树中若要进行中序遍历则先要访问跟结点D的左结点但因为D的左右结点都为NULL所以先访问结点D之后访问D的跟结点B因为B的右结点为NULL,再访问B的跟结点A之后因为E的左右结点都为NULL所以先访问结点E再访问E的跟节点C之后访问C的右结点F 因此通过以上分析就可以得出中序遍历结果为D B A E C F
后序遍历: 在以上图示的二叉树中若要进行后序遍历则先要访问跟结点D的左结点但因为D的左结点为NULL之后再访问D的右结点但因为D的右结点为NULL所以先访问结点D之后访问B的右结点但因为B的右结点为NULL所以之后访问结点B,之后因为E的左右结点都为NULL所以先访问结点E之后再访问C的右节点F再访问节点C最后再访问C的跟结点A
因此通过以上分析就可以得出中序遍历结果为D B E F C A 完成了以上二叉树的示例的分析接下来我们就来试着实现前中后序遍历的代码
3.1前序遍历
先是在Tree.h文件内完成前序遍历函数的声明
//前序遍历
void PreOrder(BTNode* root);将该函数命名为PreOrder函数的参数是指向二叉树结点的结构体指针
之后就是在Tree.c内完成函数的定义
以下前序遍历函数是一个递归函数递归的结束的结束条件是当访问的结点值为NULL时使用printf将结点内的值打印出
//前序遍历
void PreOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}
图解遍历
我们来通过以下示例将前序遍历的的递归过程完整的展示一遍
以下就是该二叉树在前序遍历函数中的函数递归栈帧图在这当中红色的线表示递推过程绿色的线表示回归的过程 3.2中序遍历
先是在Tree.h文件内完成中序遍历函数的声明
//中序遍历
void InOrder(BTNode* root);
将该函数命名为InOrder函数的参数是指向二叉树结点的结构体指针
之后就是在Tree.c内完成函数的定义 以下中序遍历函数是一个递归函数递归的结束的结束条件是当访问的结点值为NULL时使用printf将结点内的值打印出
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
} 图解遍历
我们来通过以下示例将中序遍历的的递归过程完整的展示一遍
以下就是该二叉树在中序遍历函数中的函数递归栈帧图在这当中红色的线表示递推过程绿色的线表示回归的过程 3.3后序遍历
先是在Tree.h文件内完成后序遍历函数的声明
//后序遍历
void PostOrder(BTNode* root);
将该函数命名为PostOrder函数的参数是指向二叉树结点的结构体指针
之后就是在Tree.c内完成函数的定义 以下后序遍历函数是一个递归函数递归的结束的结束条件是当访问的结点值为NULL时使用printf将结点内的值打印出
//后序遍历
void PostOrder(BTNode* root)
{if (root NULL){return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}图解遍历
我们来通过以下示例将后序遍历的的递归过程完整的展示一遍
以下就是该二叉树在后序遍历函数中的函数递归栈帧图在这当中红色的线表示递推过程绿色的线表示回归的过程 4.结点个数以及高度等
在实现了链式二叉树的结构和前中后序遍历后接下来我们来试着实现一些求二叉树结点层次等的函数
4.1二叉树结点个数
先是在Tree.h文件内完成二叉树结点个数函数的声明
// 二叉树结点个数
int BinaryTreeSize(BTNode* root); 将该函数命名为BinaryTreeSize,函数的参数是指向二叉树结点的结构体指针
之后就是在Tree.c内完成函数的定义
在求二叉树的函数中你可能会想到用一个变量size来作结点个数的计数变量那么我们就试着使用这种方法来实现二叉树结点个数的个数
int BinaryTreeLeafSize(BTNode* root,int size)
{if (root 0){return 0;}size;BinaryTreeLeafSize(root-left,size) ;BinaryTreeLeafSize(root-right,size);return size;
}
以上就是按照这种想法来实现的函数但其实以上的函数是存在非常明显的问题的你能观察出问题吗
问题就是以上的函数使用传size的值这就会让函数在递归过程中在各个函数栈帧中size的改变不会影响到其兄弟结点的size值因此就需要对以上函数做出改变
int BinaryTreeLeafSize(BTNode* root,int* psize)
{if (root 0){return 0;}(*psize);BinaryTreeLeafSize(root-left,psize) ;BinaryTreeLeafSize(root-right,psize);return *psize;
}
以上就是改变后的函数将计数的变量size传值改为传址这样就可以让每个函数栈帧内*psize的改变影响到其兄弟结点的函数栈帧。
但以上这种算法需要在调用函数前创建一个用于计数的变量而且在每次调用完函数BinaryTreeLeafSize后还需要将用于计数的变量重新赋值为0否则就会使得下一次调用函数得到的结点个数还会包含上一次调用函数得到的结点个数因此这种算法是不太好的我们需要在思考其他的算法
以下就是就是不使用计数的方法来实现的函数是将二叉树的结点直接返回函数递归的结束条件就是当结点为NULL时 // 二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right);
}
以上函数在以下示例中就会如下形式递归 4.2 二叉树叶子结点个数
要实现求二叉树中的叶子结点个数函数首先来复习一下什么是叶子结点
我们知道度为0的结点称为叶结点叶子结点的特征就是无孩子结点也就是其链式结构当中结点内两个指针都指向NULL例如在以下示例的叶子节点就是结点3、结点5、结点6
复习了叶子结点的概念接下来就可以来实现函数代码了
先是在Tree.h文件内完成二叉树叶子结点个数函数的声明
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root); 将该函数命名为BinaryTreeLeafSize,函数的参数是指向二叉树结点的结构体指针
之后就是在Tree.c内完成函数的定义
以下函数也是通过函数递归的方式来实现的递归的结束条件是当结点为NULL时此时就返回0 当结点的左孩子和右孩子都为NULL就返回1
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-left NULL root-rightNULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);} 4.3二叉树第k层结点个数
首先先来通过一个示例来复习第k层节点数的概念例如以下示例二叉树中第三层节点数就为3 要实现函数先是在Tree.h文件内完成二叉树第k层结点个数函数的声明
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k); 将该函数命名为BinaryTreeLeafSize,函数的参数有两个第一个是指向二叉树结点的结构体指针第二个是想要得到的二叉树节点数的层序号
之后就是在Tree.c内完成函数的定义 以下函数也是通过函数递归的方式来实现的递归的结束条件是当结点为NULL时此时就返回0 在函数中当调用该函数时k值都减1当k值为1是就表明该1结点是在第k层就返回1
// 二叉树第k层结点个数
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);
} 4.4二叉树的深度/高度
在实现二叉树的高度/深度函数前先来复习一下高度/深度的概念树的高度或深度就表示树中结点的最大层次
例如以下示例二叉树中深度就为3 要实现函数先是在Tree.h文件内完成二叉树的深度函数的声明
//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
将该函数命名为BinaryTreeDepth,函数的参数是指向二叉树结点的结构体指针
之后就是在Tree.c内完成函数的定义 在二叉树中的深度就为左子树的深度或者右子树的深度再加上1在这当中取左右子树中深度大的一边以下代码中使用三目操作符 来实现
//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int L BinaryTreeDepth(root-left);int R BinaryTreeDepth(root-right);return L R ? 1 L : 1 R;
} 4.5二叉树查找值为x的结点
先是在Tree.h文件内完成查找值为x的结点函数的声明
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
将该函数命名为BinaryTreeFind函数的参数有两个第一个是指向二叉树结点的结构体指针第二个是要查找的数据
之后就是在Tree.c内完成函数的定义 在以下函数中如果找到了值为x的结点也就是当root-val等于x时就返回这个结点的指针并且在函数在左子树中找到就不会再去右结点中查找
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-val x){return root;}BTNode* tmp1BinaryTreeFind(root-left,x);if (tmp1 ! NULL){return tmp1;}BTNode*tmp2BinaryTreeFind(root-right, x);if (tmp2 ! NULL){return tmp2;}return NULL;
} 4.6二叉树的销毁
先是在Tree.h文件内完成二叉树的销毁函数的声明
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);
将该函数命名为BinaryDestory函数的的参数为指向结点的结构体指针的地址 由于要在释放结点空间后将指针置为NULL因此函数的参数为二级指针这样就可以使得形参的改变影响实参不用再手动置指针为NULL
之后就是在Tree.c内完成函数的定义 在此函数中是使用后序遍历的方式使得能找到结点的孩子结点在此之后再释放结点
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);*root NULL;
} 5.层序遍历
在本篇开始我们实现了前中后序遍历接下来我们接着来实现层序遍历先来了解层序遍历的概念
设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第⼀层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历
在层序遍历中由于要将二叉树中的结点按照层序来遍历这就使得我们不能再像之前的遍历一样使用函数递归的方法来实现这时就要再思考其他的方法
在此我们实现层序遍历需要额外借助数据结构队列
在此使用队列是来完成以下操作先将二叉树中的根结点入队列之后读取对头元素后出队列若结点的左、右孩子结点存在就将孩子结点入队列之后重复以上操作直到队列为空 注在实现层序遍历的代码前先要将之前实现的队列文件Queue.c和Queue.h添加到程序当中 并且要将之前的队列当中定义队列的结构的结构体中的数据类型改为指针类型BinaryTreeNode*
//队列结构的定义
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{QDataType data;//节点内的数据struct QueueNode* next;//指向下一个节点的指针}QueueNode;
完成以上操作就可以来实现层序遍历的代码了
//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);//将二叉树根节点入队QueuePush(q, root);while (!QueueEmpty(q)){//取队头BTNode* tmpQueueFront(q);printf(%d , tmp-val);//出队QueuePop(q);if (tmp-left){QueuePush(q, tmp-left);}if (tmp-right){QueuePush(q, tmp-right);}}QueueDestory(q);//销毁队列} 6.判断是否为完全二叉树
之前我们了解了完全二叉树相关的概念和性质那么如果要写一个函数来判断是否为完全二叉树该如何来实现呢 接下来就来看看完全二叉树和非完全二叉树层序遍历的有什么不同来看以下示例 以上为非完全二叉树层序遍历结果为A B C D NULL E F NULL NULL NULL NULL NULL NULL 而在以上完全二叉树中层序遍历结果就为A B C D F E NULL NULL NULL NULL NULL NULL NULL 通过以上两个二叉树的示例就可以得出如果一个二叉树是完全二叉树则在层序遍历时当遍历到NULL时二叉树二叉树所有有效结点都已经遍历完而如果是非完全二叉树就会在层序遍历中遍历到NULL后二叉树可能还有有效结点没有遍 接下来就来实现判断是否是完全二叉树的代码以下函数和层序遍历一样也是用到队列但和层序遍历中有所不同无论结点的孩子结点为不为空都入队列。当取出的队头元素为NULL时就跳出第一个while循环之后的while循环用来判断队列剩下的是否还有有效元素有则说明该二叉树不是完全二叉树
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);QueuePush(q, root);while (!QueueEmpty(q)){BTNode* tmp QueueFront(q);QueuePop(q);if (tmp NULL){break;}QueuePush(q,tmp-left);QueuePush(q, tmp-right);}while (!QueueEmpty(q)){BTNode* tmp QueueFront(q);QueuePop(q);if (tmp ! NULL){QueueDestory(q);//销毁队列return false;}}QueueDestory(q);//销毁队列return true;} 7.完整代码
Tree.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.htypedef int BTDataType;
// 二叉树链式结构
typedef struct BinaryTreeNode
{struct BinaryTreeNode* left;struct BinaryTreeNode* right;BTDataType val;}BTNode;//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//层序遍历
void LevelOrder(BTNode* root);// 二叉树结点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);
Tree.c
#includeTree.h
#includeQueue.h//前序遍历
void PreOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}//中序遍历
void InOrder(BTNode* root)
{if (root NULL){return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}//后序遍历
void PostOrder(BTNode* root)
{if (root NULL){return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(q);//将二叉树根节点入队QueuePush(q, root);while (!QueueEmpty(q)){//取队头BTNode* tmpQueueFront(q);printf(%d , tmp-val);//出队QueuePop(q);if (tmp-left){QueuePush(q, tmp-left);}if (tmp-right){QueuePush(q, tmp-right);}}QueueDestory(q);}// 二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right);
}// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-left NULL root-rightNULL){return 1;}return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);}// 二叉树第k层结点个数
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);
}//⼆叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int L BinaryTreeDepth(root-left);int R BinaryTreeDepth(root-right);return L R ? 1 L : 1 R;
}// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-val x){return root;}BTNode* tmp1BinaryTreeFind(root-left,x);if (tmp1 ! NULL){return tmp1;}BTNode*tmp2BinaryTreeFind(root-right, x);if (tmp2 ! NULL){return tmp2;}return NULL;
}// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);*root NULL;} test.c
#includeTree.hBTNode* NewNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);exit(1);}newnode-left newnode-right NULL;newnode-val x;return newnode;
}BTNode* CreateTree()
{BTNode* node1 NewNode(1);BTNode* node2 NewNode(2);BTNode* node3 NewNode(3);BTNode* node4 NewNode(4);BTNode* node5 NewNode(5);node1-left node2;node1-right node3;node2-left node4;node2-right node5;return node1;
}void testTree()
{BTNode* node1CreateTree();PreOrder(node1);printf(\n);InOrder(node1);printf(\n);PostOrder(node1);printf(结点个数%d\n,BinaryTreeSize(node1));printf(叶子结点个数%d\n, BinaryTreeLeafSize(node1));printf(第k层结点个数%d\n, BinaryTreeLevelKSize(node1,3));printf(深度%d\n, BinaryTreeDepth(node1));BTNode* findBinaryTreeFind(node1,13);printf(%s, find NULL ? 找不到! : 找到了);LevelOrder(node1);bool dBinaryTreeComplete(node1);printf(%s, d true ? 是完全二叉树 : 不是完全二叉树);BinaryTreeDestory(node1);
}Queue.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h//队列结构的定义
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{QDataType data;//节点内的数据struct QueueNode* next;//指向下一个节点的指针}QueueNode;typedef struct Queue
{struct QueueNode* phead;//指向第一个节点的指针struct QueueNode* ptail;//指向尾节点的指针int size;//节点的个数}Queue;
//初始化队列
void QueueInit(Queue* pq);
//销毁队列
void QueueDestory(Queue* pq);
//入队列
void QueuePush(Queue* pq, QDataType x);
//出队列
void QueuePop(Queue* pq);
//队列判空
bool QueueEmpty(Queue* pq);
//取队列头数据
QDataType QueueFront(Queue* pq);
//取队列尾数据
QDataType QueueBack(Queue* pq);
//队列有效数据个数
int QueueSize(Queue* pq);
Queue.c
#includeQueue.h//初始化队列
void QueueInit(Queue* pq)
{assert(pq);pq-phead pq-ptail NULL;pq-size 0;
}//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));QueueNode* pcur pq-phead;while (pcur){QueueNode* Next pcur-next;free(pcur);pcur Next;}pq-phead pq-ptail NULL;pq-size 0;
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-phead NULL pq-ptail NULL;
}//入队列
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode (QueueNode*)malloc(sizeof(QueueNode));if (newnode NULL){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;if (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));if (pq-phead pq-ptail){free(pq-phead);pq-phead pq-ptail NULL;}else{QueueNode* Next pq-phead-next;free(pq-phead);pq-phead Next;}pq-size--;}//取队列头数据
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-phead-data;
}//取队列尾数据
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-ptail-data;}//队列有效数据个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
} 以上就是二叉树(下)的全部内容了本篇之后我们就学习完了二叉树的所有基本知识接下来将会在之后的篇章中写一些二叉树相关的算法题未完待续……
