网站的项目建设周期,建设网站需要备案么,电商网站建设公司怎么样,购买了域名之后怎么做网站详解C语言实现二叉树~#x1f60e;前言#x1f64c;什么是二叉树#xff1f;二叉树的性质总结#xff1a;整体实现内容分析#x1f49e;1.头文件的编写#xff1a;#x1f64c;2.功能文件的编写#xff1a;#x1f64c;1#xff09;前序遍历的数值来创建树——递归函…
详解C语言实现二叉树~前言什么是二叉树二叉树的性质总结整体实现内容分析1.头文件的编写2.功能文件的编写1前序遍历的数值来创建树——递归函数实现 2求树的高度函数实现 3求叶子数函数实现 4求树的总结点个数函数实现 5前序遍历二叉树实现 6中序遍历二叉树实现 7后序遍历二叉树实现 8删除二叉树函数实现 3.测试文件编写总结撒花博客昵称博客小梦 最喜欢的座右铭全神贯注的上吧 作者简介一名热爱C/C算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主 博主小留言哈喽各位CSDN的uu们我是你的博客好友小梦希望我的文章可以给您带来一定的帮助话不多说文章推上欢迎大家在评论区唠嗑指正觉得好的话别忘了一键三连哦 前言 哈喽各位友友们我今天又学到了很多有趣的知识现在迫不及待的想和大家分享一下我仅已此文手把手带领大家详解C语言实现二叉树~ 利用二叉链式存储结构来完成二叉树的实现并完成叶子高度前序遍历生成树叶节点的个数结点总数前序遍历中序遍历后序遍历销毁树。都是精华内容可不要错过哟 什么是二叉树
满足以下两个条件的树就是二叉树 本身是有序树树中包含的各个节点的度不能超过 2即只能是 0、1 或者 2 二叉树的性质总结 二叉树中第 i 层最多有 2^( i-1)个结点。如果二叉树的深度为 K那么此二叉树最多有 2^K-1 个结点。二叉树中终端结点数叶子结点数为 n0度为 2 的结点数为 n2则 n0n21。 二叉树又可以分类为许多不同的二叉树
整体实现内容分析 利用二叉链式存储结构来完成二叉树的实现并完成叶子高度前序遍历生成树叶节点的个数结点总数前序遍历中序遍历后序遍历销毁树。采用递归的思想先是malloc开辟结点空间然后给结点赋值然后递归左子树然后递归右子树。这里用*表示空。最后返回生成的root指针的地址求高度采用后序遍历的思想。相当于求左右子树结点高度的最大值。每次递归加1就是计算结点数。求叶子总数时先求出左子树的叶子数再加上右子树的叶子数。求总结点数时这里直接递归计算出左子树和右子树的总结点数每次加1表示遍历的节点数计算。然后就是前中后序的实现这里也是用到递归的思想最后便是将数销毁掉malloc生成的空间要用free手动销毁。 1.头文件的编写
头文件的编写的整体思路分析 这里用的是二叉链式存储的实现。首先是定义结构体然后是对求叶子高度前序遍历生成树叶节点的个数结点总数前序遍历中序遍历后序遍历销毁树。 #pragma once
#includestdio.h
#includestdlib.h
typedef int datatype;
typedef struct node
{datatype data;struct node* lchild, * rchild;
}tree;
tree* Creatbitree();
int Depthbitree(tree* T);
int Leaf_count(tree* T);
int Countbitree(tree* T);
int Preorder(tree* T);
int Inorder(tree* T);
int Postorder(tree* T);
tree* Delete(tree* T);
2.功能文件的编写
1前序遍历的数值来创建树——递归函数实现
编写的整体思路分析 采用递归的思想先是malloc开辟结点空间然后给结点赋值然后递归左子树然后递归右子树。这里用*表示空。最后返回生成的root指针的地址 #includeBinaryTree.h
tree* Creatbitree()//前序遍历的数值来创建树——递归
{char ch;tree* root;scanf(%c, ch);//用于接收输入的数值 if (ch *) return NULL;//用*来判断是否为空 else {root (tree*)malloc(sizeof(tree));root-data ch;//赋值 root-lchild Creatbitree();//左子树 root-rchild Creatbitree();//右子树 }return root;
}2求树的高度函数实现
编写的整体思路分析 这里求高度采用后序遍历的思想。相当于求左右子树结点高度的最大值。每次递归加1 就是计算结点数。 int Depthbitree(tree* T)//测量树的深度
{if (T NULL) return 0;else {int leftheighter Depthbitree(T-lchild);int rightheighter Depthbitree(T-rchild);return (leftheighter rightheighter ? leftheighter 1 : rightheighter 1);}
}
3求叶子数函数实现
编写的整体思路分析 代码上已表明算法思想先求出左子树的叶子数再加上右子树的叶子数。 int Leaf_count(tree* T)//测量叶子的数量
{if (T NULL) return 0;else if (!T-lchild !T-rchild)//如果左右结点都为空则他就是叶子结点 return 1;else return Leaf_count(T-lchild) Leaf_count(T-rchild);
}
4求树的总结点个数函数实现
编写的整体思路分析 这里直接递归计算出左子树和右子树的总结点数每次加1表示遍历的节点数计算。 int Countbitree(tree* T) //测量总的结点个数
{if (T NULL)return 0;else {return Countbitree(T-lchild) Countbitree(T-rchild)1;}
}
5前序遍历二叉树实现
int Preorder(tree* T)//前序遍历序列 根左右
{if (T NULL)return 0;else {printf(%c , T-data);//先输出根节点 Preorder(T-lchild);Preorder(T-rchild);}
}
6中序遍历二叉树实现
int Inorder(tree* T)//中序遍历序列 左根右
{if (T NULL)return 0;else {Inorder(T-lchild);//先输出左孩子 printf(%c , T-data);Inorder(T-rchild);}
}
7后序遍历二叉树实现
int Postorder(tree* T)//后序遍历序列 左右根
{if (T NULL)return 0;else {Postorder(T-lchild);//先输出左孩子 Postorder(T-rchild);printf(%c , T-data);}
}
8删除二叉树函数实现
tree* Delete(tree* T)//删除树
{if (T-lchild)Delete(T-lchild);else if (T-rchild)Delete(T-rchild);elsefree(T);
}
3.测试文件编写 #define _CRT_SECURE_NO_WARNINGS 1
#includeBinaryTree.hmain()
{tree* T;T (tree*)malloc(sizeof(tree));T-lchild NULL;T-rchild NULL;printf(请输入树的前序遍历序列\n);T Creatbitree();int n Depthbitree(T);int m Leaf_count(T);int l Countbitree(T);printf(树创建完成\n);printf(前序输出为\n);printf(\t\t);Preorder(T);printf(\n中序输出为\n);printf(\t\t);Inorder(T);printf(\n后序输出为\n);printf(\t\t);Postorder(T);printf(\n高度%d\n叶子%d\n总结点%d\n, n, m, l);Delete(T);printf(删除成功);
}
功能测试结果展示图 总结撒花 本篇文章旨在分享详解C语言实现二叉树。希望大家通过阅读此文有所收获本次主要是对二叉树的实现这里只要用到的思想是递归这也是难点所在。这就要需要画图帮忙辅助理解递归的具体每一步是如何执行的需要分析清楚。在创建树的时候可以采用前序遍历思想创建这种思想创建是比较好理解的也可以用其他思想创建相对比较难理解一点。以及区分好前中后序遍历的思想然后再编写代码。 如果我写的有什么不好之处请在文章下方给出你宝贵的意见。如果觉得我写的好的话请点个赞赞和关注哦~
