佛山自动机设备骏域网站建设专家,推荐网站空间购买,淘宝客采集网站建设,自适应网站开发教程二叉树的实现 前言一、二叉树链式结构的实现1.1前置说明1.2二叉树的手动创建 二、二叉树的遍历2.1 前序、中序以及后序遍历二叉树前序遍历二叉树中序遍历二叉树后序遍历2.2 层序遍历练习 三、二叉树的具体代码实现二叉树的节点个数二叉树叶子节点个数二叉树第k层节点个数二叉树… 二叉树的实现 前言一、二叉树链式结构的实现1.1前置说明1.2二叉树的手动创建 二、二叉树的遍历2.1 前序、中序以及后序遍历二叉树前序遍历二叉树中序遍历二叉树后序遍历2.2 层序遍历练习 三、二叉树的具体代码实现二叉树的节点个数二叉树叶子节点个数二叉树第k层节点个数二叉树查找值为x的节点二叉树的销毁二叉树的创建判断二叉树是否是完全二叉树 四、二叉树的选择练习题答案 五、二叉树基础oj练习六、二叉树的完整代码Tree.hTree.cTest.c 前言
二叉树是一种常见的数据结构每个节点最多有两个子节点通常称为左子节点和右子节点。实现二叉树通常涉及定义节点类包含数据和指向子节点的指针以及相应的插入、删除和查找操作。遍历二叉树则是访问其所有节点的过程常见的遍历方式有前序遍历根-左-右、中序遍历左-根-右和后序遍历左-右-根。这些遍历方法可以递归或迭代实现对于理解二叉树结构和操作非常重要。 一、二叉树链式结构的实现
1.1前置说明
在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。由于现在各位读者对二叉树结构掌握还不够深入为了降低大家学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。
1.2二叉树的手动创建
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;BTNode* CreatBinaryTree()
{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;return node1;
}注意上述代码并不是创建二叉树的方式真正创建二叉树方式见下文
再看二叉树基本操作前再回顾下二叉树的概念二叉树是
空树非空根节点根节点的左子树、根节点的右子树组成的。 从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。
二、二叉树的遍历
2.1 前序、中序以及后序遍历
学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);二叉树前序遍历
// 二叉树前序遍历
void PreOrder(BTNode* root);void PreOrder(BTNode* root)
{if (root NULL){printf(NULL-);return;}printf(%d-, root-val);PreOrder(root-left);PreOrder(root-right);
}二叉树中序遍历
// 二叉树中序遍历
void InOrder(BTNode* root);void InOrder(BTNode* root)
{if (root NULL){printf(NULL-);return;}InOrder(root-left);printf(%d-, root-val);InOrder(root-right);
}二叉树后序遍历
// 二叉树后序遍历
void PostOrder(BTNode* root);void PostOrder(BTNode* root)
{if (root NULL){printf(NULL-);return;}PostOrder(root-left);PostOrder(root-right);printf(%d-, root-val);
}下面主要分析前序递归遍历中序与后序图解类似。
前序遍历递归图解 前序遍历结果1 2 3 4 5 6
中序遍历结果3 2 1 5 4 6
后序遍历结果3 2 5 6 4 12.2 层序遍历
层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。
// 层序遍历
void LevelOrder(BTNode* root);使用队列的形式来实现层序遍历——队列
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if(root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){printf(%c , front-val);QueuePush(q, front-left);QueuePush(q, front-right);}else{printf( N );}}printf(\n);QueueDestroy(q);
}层序遍历也称为广度优先遍历是一种树的遍历方法它按照树的层次顺序访问节点。具体来说从根节点开始先访问所有相邻的子节点然后逐层向下遍历每访问一层的节点就转向下一层直到遍历完所有节点。这种遍历方法常用于二叉树、多叉树和图等数据结构。在二叉树中通常使用队列来实现层序遍历首先将根节点入队然后不断从队列中出队节点并访问同时将该节点的子节点入队直到队列为空。层序遍历的时间复杂度通常为O(n)其中n为节点数空间复杂度取决于队列的大小最坏情况下为O(n)。
练习
请写出下面的前序/中序/后序/层序遍历
三、二叉树的具体代码实现
二叉树的节点个数
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);int BinaryTreeSize(BTNode* root)
{if (root NULL)return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 1;
}该段代码定义了一个名为BinaryTreeSize的函数用于计算二叉树中节点的总数。函数接受一个指向二叉树根节点的指针root作为参数。如果root为空则返回0否则递归计算左子树和右子树的节点数并将它们相加再加上根节点本身最终返回整个二叉树的节点总数。
二叉树是每个节点最多有两个子节点的树结构通常子节点被称为“左子节点”和“右子节点”。二叉树的节点个数是指树中所有节点的总数包括根节点、内部节点非叶子节点和叶子节点。计算二叉树的节点个数可以通过遍历树的所有节点来实现例如使用前序遍历、中序遍历或后序遍历等方法。在遍历过程中每访问一个节点就将计数器加1最终计数器的值就是二叉树的节点个数。此外对于完全二叉树和满二叉树等特殊类型的二叉树其节点个数可以通过特定的公式直接计算得出。
二叉树叶子节点个数
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);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);
}该函数BinaryTreeLeafSize计算二叉树的叶子节点数量。如果根节点为空返回0如果根节点是叶子节点即没有左右子节点返回1否则递归计算左子树和右子树的叶子节点数量并返回它们的和。
二叉树的叶子节点是指没有子节点的节点。要计算二叉树的叶子节点个数可以采用递归或迭代的方法。递归方法的基本思路是对于每个节点如果它是叶子节点则计数加1否则递归计算其左右子树的叶子节点个数并相加。迭代方法则可以利用队列或栈等数据结构层次遍历或深度优先遍历二叉树统计叶子节点的个数。无论采用哪种方法最终得到的叶子节点个数即为二叉树的叶子节点总数。
二叉树第k层节点个数
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);int BinaryTreeLevelKSize(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}该函数BinaryTreeLevelKSize计算了二叉树中第k层的节点数量。首先它检查k是否大于0并确认根节点root是否存在。如果root为空则返回0。如果k等于1表示要求的是第一层的节点数直接返回1。否则它递归地对左子树和右子树调用自身计算第k-1层的节点数然后将这两个结果相加得到第k层的节点数。
二叉树第k层的节点个数可以通过递归或迭代方法计算。在递归方法中对于给定的二叉树我们首先检查根节点是否为空。如果为空则树为空返回0。否则我们递归地计算左子树和右子树的第k-1层节点数并将它们相加得到第k层的节点数。在迭代方法中我们使用队列进行层序遍历记录每一层的节点数直到找到第k层或遍历完整个树。最终返回第k层的节点数。这两种方法的时间复杂度均为O(n)其中n为二叉树中节点的总数。
二叉树查找值为x的节点
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-val x)return root;BTNode* left BinaryTreeFind(root-left, x);if (left)return left;BTNode* right BinaryTreeFind(root-right, x);if (right)return right;return NULL;
}该函数是一个在二叉树中查找指定值的函数。它接受一个二叉树的根节点和一个要查找的值x作为参数。如果根节点为空则返回NULL。如果根节点的值与x相等则返回根节点。否则它递归地在左子树和右子树中查找x。如果在左子树或右子树中找到x则返回对应的节点。如果在整棵树中都没有找到x则返回NULL。
二叉树的销毁
二叉树的构建及遍历
//二叉树销毁 void Binary Tree Destory (BTNode** root) ; void BinaryTreeDestroy(BTNode** root)
{if ((*root) NULL)return;BinaryTreeDestroy((*root)-left);BinaryTreeDestroy((*root)-right);free(*root);*root NULL;
}该函数BinaryTreeDestroy是一个用于销毁二叉树的递归函数。它接受一个指向二叉树根节点指针的指针root。首先它检查根节点是否为空如果为空则直接返回。否则它递归地销毁左子树和右子树然后释放根节点的内存并将根节点指针设置为NULL从而完成整个二叉树的销毁。
二叉树的创建
// 通过前序遍历的数组 A B D # # E # H # # C F # # G # # 构建二叉树BTNode* Binary TreeCreate(BTDataType* a,int n,int* pi) ; BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (a NULL || n 0)return NULL;if (a[*pi] ){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root-val a[(*pi)];root-left BinaryTreeCreate(a, n, pi);root-right BinaryTreeCreate(a, n, pi);return root;
}该段代码实现了一个二叉树的创建函数。它接收三个参数一个数据类型数组a一个整数n表示数组长度以及一个整数指针pi指向数组中当前要处理的元素索引。函数首先检查输入是否有效若数组为空或n小于等于0则返回NULL。若当前元素为空格则递增索引并返回NULL。否则创建一个新的二叉树节点将当前元素赋值给节点的值并递归地创建左右子树。最后返回新创建的根节点。
判断二叉树是否是完全二叉树
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){printf(%c , front-val);QueuePush(q, front-left);QueuePush(q, front-right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);if (front){QueueDestroy(q);return false;}}}QueueDestroy(q);return true;
}此函数BinaryTreeComplete检查给定的二叉树root是否是完全二叉树。它使用一个队列q进行层序遍历。首先如果根节点存在则将其入队。然后在队列不为空的情况下反复取出队首节点并打印其值然后将它的左右子节点入队。如果在遍历过程中发现队列中出现了空节点则立即销毁队列并返回false因为完全二叉树在层序遍历中不应出现空节点。如果遍历结束即队列为空且没有发现空节点则销毁队列并返回true说明是完全二叉树。
四、二叉树的选择练习题
某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为 A、 ABDHECFG B、 ABCDEFGH C、 HDBEAFCG D、 HDEBFGCA二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为 A 、E B、 F C、 G D、 H设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列____。 A、 adbce B 、decab C、 debac D、 abcde某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出同一层从左到右的序列为( ) A 、FEDCBA B、 CBAFED C、 DEFCBA D、 ABCDEF
答案
1.A 2.A 3.D 4.A
五、二叉树基础oj练习
单值二叉树检查两颗树是否相同对称二叉树二叉树的前序遍历二叉树中序遍历二叉树的后序遍历另一颗树的子树
六、二叉树的完整代码
Tree.h
#pragma once
#include stdio.h
#include stdlib.h
#include stdbool.h
#include assert.htypedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType val;struct BinaryTreeNode* left;struct BinaryTreeNode* right;}BTNode;
typedef BTNode* QDatatype;
typedef struct QueueNode
{QDatatype val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;
//队列的初始化
void QueueInit(Queue* pq);
//队列的销毁
void QueueDestroy(Queue* pq);//入队列
void QueuePush(Queue* pq, QDatatype x);
//出队列
void QueuePop(Queue* pq);//队头元素
QDatatype QueueFront(Queue* pq);
//队尾元素
QDatatype QueueBack(Queue* pq);//检测是否为空
bool QueueEmpty(Queue* pq);//检测元素个数
int QueueSize(Queue* pq);//创建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);//二叉树的销毁
void BinaryTreeDestroy(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);
// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);Tree.c
#include Tree.h
void QueueInit(Queue* pq)
{assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-phead;while (cur){QNode* next cur-next;free(cur);cur next;}pq-phead NULL;pq-ptail NULL;pq-size 0;
}
void QueuePush(Queue* pq, QDatatype x)
{assert(pq);QNode* newnode (QNode*)malloc(sizeof(QNode));if (newnode NULL){perror(newnode malloc :);return;}newnode-val x;newnode-next NULL;if (pq-ptail){pq-ptail-next newnode;pq-ptail newnode;}else{pq-phead pq-ptail newnode;}pq-size;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;
}
void QueuePop(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));assert(pq-phead ! NULL);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(pq-phead ! NULL);return pq-phead-val;
}
QDatatype QueueBack(Queue* pq)
{assert(pq);assert(pq-ptail ! NULL);return pq-ptail-val;
}
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{if (a NULL || n 0)return NULL;if (a[*pi] ){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root-val a[(*pi)];root-left BinaryTreeCreate(a, n, pi);root-right BinaryTreeCreate(a, n, pi);return root;
}
void BinaryTreeDestroy(BTNode** root)
{if ((*root) NULL)return;BinaryTreeDestroy((*root)-left);BinaryTreeDestroy((*root)-right);free(*root);*root NULL;
}
int BinaryTreeSize(BTNode* root)
{if (root NULL)return 0;return BinaryTreeSize(root-left) BinaryTreeSize(root-right) 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)
{assert(k 0);if (root NULL)return 0;if (k 1)return 1;return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-val x)return root;BTNode* left BinaryTreeFind(root-left, x);if (left)return left;BTNode* right BinaryTreeFind(root-right, x);if (right)return right;return NULL;
}
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);
}bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){printf(%c , front-val);QueuePush(q, front-left);QueuePush(q, front-right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);if (front){QueueDestroy(q);return false;}}}QueueDestroy(q);return true;
}Test.c
#include Tree.h
int main()
{char a[] { a,b,c, , ,d,e, ,g, , ,f, , , };int pi 0;BTNode* root BinaryTreeCreate(a, sizeof(a) / sizeof(a[0]), pi);BinaryTreePrevOrder(root);printf(\n);BinaryTreeInOrder(root);printf(\n);BinaryTreePostOrder(root);printf(\n);printf(TreeSize : %d\n, BinaryTreeSize(root));printf(TreeKLevel : %d\n, BinaryTreeLevelKSize(root, 3));BTNode* ret BinaryTreeFind(root, 3);printf(TreeFind : %p\n, ret);BinaryTreeLevelOrder(root);printf(\n);printf(BinaryTreeComplete %d\n , BinaryTreeComplete(root));BinaryTreeDestroy(root);root NULL;return 0;
}我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code1bgxnv3eldfha
