网站服务器问题,常州行业网站,深圳沙井公司网站建设,湛江模板建站哪家好个人主页#xff1a; NiKo
数据结构专栏#xff1a; 数据结构与算法 源码获取#xff1a;Gitee——数据结构 一、二叉树的链式结构 typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;struct BinaryTreeNode* left; // 左子树根节点struct BinaryT…
个人主页 NiKo
数据结构专栏 数据结构与算法 源码获取Gitee——数据结构 一、二叉树的链式结构 typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;struct BinaryTreeNode* left; // 左子树根节点struct BinaryTreeNode* right; // 右子树根节点
}BTNode; 每一颗二叉树都是由左子树、根、右子树构成的在实现二叉树的链式结构时我们也要将二叉树看作这三部分。 二、二叉树的遍历
学习二叉树结构最简单的方式就是遍历。所谓 二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 遍历是通过递归实现的。 按照规则二叉树的遍历有 前序/中序/后序的递归结构遍历 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 图1-1 已经创建的二叉树如图1-1。 1.前序遍历 前序遍历访问根结点的操作发生在遍历其左右子树之前访问顺序为根、左子树、右子树。根据概念在访问二叉树时需要将二叉树看作根、左子树、右子树左右子树又可以分为根、左子树、右子树直到访问的节点为空NULL即证明访问到了二叉树的最底层。 如图1-1所示首先访问的根是1这是第一层递归然后递归访问此根的左子树根节点为2这是第二层递归而以2为根的子树又可以分为以3为根的左子树、NULL访问完根节点2后应继续递归访问左子树根节点3这是第三层递归此时根节点3的左子树为空右子树为空无法再递归下去以3为根节点的子树访问完毕结束第三层递归返回到第二层递归并访问根节点2的右子树右子树为空无法递归以2为根节点的子树访问完毕结束第二层递归返回到第一层递归并访问根节点1的右子树同理根据遍历左子树的方式遍历右子树。 void PrevOrder(BTNode* root) {// 不符合递归条件结束此层递归if (root NULL) {printf(N );return;}printf(%d , root-data); // 访问根节点PrevOrder(root-left); // 访问根节点的左子树PrevOrder(root-right); // 访问根节点的右子树
}根据代码前序遍历的结果示意图 2.中序遍历 中序遍历访问根结点的操作发生在遍历其左右子树之中间。访问顺序为左子树、根、右子树。同前序遍历的分析方式一样访问一棵树应从他的左子树开始访问然后再访问根和右子树。 如图1-1首先访问以1为根的左子树根节点2进入第一层递归以根节点为2的左子树又可以分为左子树根节点3、右子树NULL进入第二层递归此时正在访问的是根节点为3的子树根据中序遍历的规则应按照左子树、根、右子树的顺序访问进入第三层递归。3的左右子树都为空不符合递归条件结束第三层递归返回到第二层递归并访问根节点2然后访问根节点2的右子树右子树为空结束第二层递归返回到第一层递归并访问根节点1随后访问根节点1的右子树同理根据遍历左子树的方式遍历右子树。 void InOrder(BTNode* root) {if (root NULL) {printf(N );return;}InOrder(root-left); // 访问根的左子树printf(%d , root-data); // 访问根InOrder(root-right); // 访问根的右子树
} 根据代码中序遍历的结果示意图 3.后序遍历 后序遍历访问根结点的操作发生在遍历其左右子树之后。访问顺序为左子树、右子树、根后序遍历访问一棵树时根节点是最后访问的。 如图1-1首先访问根节点1的左子树根节点2进入第一层递归这颗子树还可以分为左右子树则进入第二层递归访问根节点2的左右子树。随后进入第三层递归先访问根节点3的左子树然后是右子树最后是根节点3结束第三层递归返回第二层递归并访问根节点2的右子树之后在访问根节点2结束第二层递归返回第一层递归访问根节点1的右子树最后访问根节点1。 void PostOrder(BTNode* root) {if (root NULL) {printf(N );return;}PostOrder(root-left); // 访问左子树PostOrder(root-right); // 访问右子树printf(%d , root-data); // 访问根
} 根据代码后序遍历的结果示意图 三、节点个数 对于一棵树而言他的节点分为两种情况 根节点为空返回0。根节点不为空这颗树的节点数左子树节点个数右子树节点个数根节点1。 根据这两种情况写出的代码如下 int TreeSize(BTNode* root) {return root NULL ? 0 :TreeSize(root-left) TreeSize(root-right) 1;
} 分析第一个访问的根节点1不为空根据表达式先计算左子树的节点个数通过TreeSize(root-left)进入第一层递归访问到根节点2在第二层递归中通过TreeSize(root-left)进入第二层递归访问根节点3根节点3不为空通过TreeSize(root-left)访问左子树进入第三层递归左子树为空返回0右子树为空返回0第三层递归的返回值为0011结束第三层递归返回到第二层递归的TreeSize(root-left)的值就是1然后在第二层递归中通过TreeSize(root-right)访问根节点2的右子树右子树为空返回0第二层递归的返回值1012结束第二层递归并将值返回到第一层递归的TreeSize(root-left)这样左子树的节点个数计算完毕为2紧接着再计算第一层递归的TreeSize(root-right)同理可得TreeSize(root-right)的值为3最后得出这棵树的节点个数是6。 四、叶子节点个数 叶子节点是指不含有任何子树的节点度为0即root-left和root-right均为NULL。判断叶子节点的个数需要我们找到度为0的节点。 对于一颗子树它的叶子节点有三种情况 根节点为空返回0根节点不为空左右子树均为空它本身就是叶子节点返回1根节点不为空左右子树至少有一个不为空这棵树的叶子节点树左子树叶子节点数右子树叶子节点数 根据这三种情况写出的代码如下 int TreeLeafSize(BTNode* root) {if (root NULL) {return 0;}else if (root-left NULL root-right NULL) {return 1;}else {return TreeLeafSize(root-left) TreeLeafSize(root-right);}
} 分析进入第一层递归访问根节点1根节点1不为空且左右子树不为空通过TreeLeafSize(root-left)进入第二层递归访问根节点2根节点2不为空且左子树不为空通过TreeLeafSize(root-left)进入第三层递归访问根节点3根节点3不为空但是此时左右子树为空说明节点3是叶子节点结束第三层递归返回1到第二层递归在第二层递归中通过TreeLeafSize(root-right)访问根节点2的右子树为空返回0则以2为根节点的子树叶子节点个数011结束第二层递归返回1到第一层递归同理可得右子树的叶子节点为112则这棵树的叶子节点数123。 五、高度 树的高度是指树中节点的最大层次在二叉树中左右两棵子树的高度较大者作为这棵树的高度。 求树的高度有两种情况 根节点为空返回0根节点不为空这棵树的高度max(左子树高度,右子树高度)1 根据这两种情况写出的代码如下 int TreeHeight(BTNode* root) {if (root NULL) {return 0;}else {return max(TreeHeight(root-left), TreeHeight(root-right)) 1;}
} 分析进入第一层递归访问根节点1不为空通过TreeHeight(root-left)进入第二层递归访问根节点2不为空通过TreeHeight(root-left)访问根节点3进入第三层递归此时TreeHeight(root-left)和TreeHeight(root-right)的返回值都为0第三层递归返回0011到第二层递归并结束第三层递归。第二层递归返回1012到第一层递归同理再访问右子树得TreeHeight(root-right)的返回值为2max(TreeHeight(root-left),TreeHeight(root-right))1的结果为3故此树的高度就是3。 六、第k层的节点个数 求二叉树的第k层节点可以向下转化为求这棵树的左右子树的第k-1层节点当k1时就到达了这棵树的第k层。 在二叉树中每次向下递归一层的情况有三种 根节点为空返回0根节点不为空且k不等于1继续向下递归直到k等于1根节点不为空且k等于1说明到达目标层返回1 根据这三种情况写出的代码如下 int TreeLevelKSize(BTNode* root, int k) {if (root NULL) {return 0;}if (k 1) {return 1;}else {return TreeLevelKSize(root-left, k - 1) TreeLevelKSize(root-right, k - 1);}
} 分析假设k3进入第一层递归访问根节点1不为空且k不等于1k3通过TreeLevelKSize(root-left, k - 1)进入第二层递归访问根节点2不为空且k不等于1k2通过TreeLevelKSize(root-left, k - 1)进入第三层递归访问根节点3不为空此时k1说明到达目标层返回1结束第三层递归。在第二层递归中通过TreeLevelKSize(root-right, k - 1)访问右子树为空返回0结束第二层递归返回1到第一层递归同理通过TreeLevelKSize(root-right, k - 1)可到达根节点1的右子树且第k层节点数是2所以这棵树的第三层有123个节点。 七、查找值为x的节点 遍历二叉树找到值为x的节点返回即可。 遍历的结果有四种情况 根节点为空返回NULL根节点不为空节点的值等于x返回这个节点地址如果在左子树中找到了目标节点不用再遍历右子树左右子树都没有找到这个节点返回NULL 根据这四种情况写出的代码如下 BTNode* TreeFind(BTNode* root, BTDataType x) {if (root NULL) {return NULL;}if (root-data x) {return root;}BTNode* ptr TreeFind(root-left, x);if (ptr ! NULL) {return ptr;}else {BTNode* ptr TreeFind(root-right, x);if (ptr NULL) {return NULL;}else {return ptr;}}
} 分析假设x6进入第一层递归访问根节点11不等于6且不为空通过TreeFind(root-left, x)进入第二层递归访问根节点22不等于6且不为空进入第三层递归访问根节点33不等于6此时结束第三层递归返回值NULL根节点2的左子树没有找到向右子树遍历右子树也没有找到结束第二层递归返回NULL说明在左子树中没有找到目标节点这时候查找右子树在右子树中找到了就返回这个节点。 八、创建二叉树 已知一个字符数组根据这个字符数组创建二叉树创建二叉树的顺序应该是根、左子树、右子树。 假设给出这样一个数组abc##de#g##f###其中#表示NULL字母代表树中节点存储的值还是用递归的思想根据这个数组建立一个二叉树。首先需要遍历这个数组遍历的结果有两种 指针指向的元素为#代表这个节点为NULL左子树或右子树建立完成指针指向非#元素将值赋给这个节点后继续建立这个节点的左子树和右子树 根据这两种情况写出的代码如下 // abc##de#g##f###
BTNode* CreateTree(BTDataType* arr, int* pi) {if (arr[*pi] #) {(*pi);return NULL;}BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL) {perror(malloc fail!);exit(-1);}node-data arr[(*pi)];node-left CreateTree(arr, pi);node-right CreateTree(arr, pi);return node;
} 分析定义一个指针代表数组的下标每当创建一个节点或遇到NULL就后移。创建好一个节点后给节点赋值然后进入递归当函数返回NULL时说明这颗子树创建完成以此类推。 九、销毁二叉树 销毁二叉树时采用后序遍历销毁节点原因是如果采用前序遍历或中序遍历会导致根节点销毁后无法销毁他的左子树或右子树。 销毁二叉树步骤 如果当前节点为NULL直接结束不为空先销毁左子树再销毁右子树最后销毁根 代码如下 void TreeDestory(BTNode* root) {if (root NULL) {return;}// 采用后序遍历销毁树TreeDestory(root-left);TreeDestory(root-right);free(root);
} 分析进入函数后先判断这个节点是不是空如果是代表已经销毁不是通过递归依次销毁左子树和右子树最后销毁根。 十、层序遍历 层序遍历广度优先遍历指的是在一棵二叉树中依次遍历访问每一层的节点直到最后一层。层序遍历需要使用到队列结构相关代码在gitte中。 层序遍历基本步骤 如果节点为空不进队列节点不为空进队列进入循环取队列的头节点头节点的左右节点非空入队列头节点出队列这时访问了一层节点当队列为空时结束循环 代码如下 void TreeLevelOrder(BTNode* root) {Queue q;QueueInit(q);// 不为空进队列if (root) {QueuePush(q, root);}// 如果队列是空的代表已经访问完所有元素while (!QueueEmpty(q)) {BTNode* front QueueFront(q);QueuePop(q);printf(%c , front-data);if (front-left) {QueuePush(q, front-left);}if (front-right) {QueuePush(q, front-right);}}QueueDestroy(q);
} 分析初始化队列如上图节点1入队列进入循环取队头节点并打印在控制台节点1的左右节点24入队列节点1出队列队列中剩24开始第二次循环取队头节点22的左节点3入队列2出队列队列中剩43以此类推开始第三次循环后节点4的左右节点进队列完成层序遍历。 十一、判断完全二叉树 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 完全二叉树就是这样一种特殊的非满二叉树除了最后一层外其他每一层都是填满的并且最后一层的节点都尽可能地靠左排列。如上图。 具体实现步骤判断完全二叉树不能利用递归实现需要利用队列的相关知识广度优先遍历实现。 创建队列无论树中的节点是否为空都进入队列根据层序遍历将队头节点的左右子节点带入队列在进入队列时如果遇到了第一个空节点就停止将节点带入队列开始判断队列中的节点是否都为空。如果是代表这棵树是完全二叉树如果不是代表这棵树是完全二叉树。 代码 bool TreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);// 遇到第一个空就可以开始判断如果队列中还有非空就不是完全二叉树if (front NULL){break;}QueuePush(q, front-left);QueuePush(q, front-right);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);// 如果有非空就不是完全二叉树if (front){QueueDestroy(q);return false;}}QueueDestroy(q);return true;
} 队列的源码可到博主的个人码云中获取Project_Queue 十二、补充二叉树的性质 若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2的i-1次方个结点. 若规定根结点的层数为1则深度为h的二叉树的最大结点数是2的h次方减1. 对任何一棵二叉树, 如果度为0其叶结点个数为 n0, 度为2的分支结点个数为n2 ,则有n0 n2 1若规定根结点的层数为1具有n个结点的满二叉树的深度hlog2(n1). (pslog2(n1)是log以2为底n1为对数) 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有结点从0开始编号则对于序号为i的结点有
若i0i位置结点的双亲序号(i-1)/2i0i为根结点编号无双亲结点 若2i1n左孩子序号2i12i1n否则无左孩子 若2i2n右孩子序号2i22i2n否则无右孩子 针对性质3 /*
* 假设二叉树有N个结点
* 从总结点数角度考虑N n0 n1 n2 ①
*
* 从边的角度考虑N个结点的任意二叉树总共有N-1条边
* 因为二叉树中每个结点都有双亲根结点没有双亲每个节点向上与其双亲之间存在一条边
* 因此N个结点的二叉树总共有N-1条边
*
* 因为度为0的结点没有孩子故度为0的结点不产生边; 度为1的结点只有一个孩子故每个度为1的结
点* * 产生一条边; 度为2的结点有2个孩子故每个度为2的结点产生两条边所以总边数为
n12*n2
* 故从边的角度考虑N-1 n1 2*n2 ②
* 结合① 和 ②得n0 n1 n2 n1 2*n2 - 1
* 即n0 n2 1
*/
