苏州网站建设培训学校,flashfxp连接wordpress,西安旅游服务网站建设,音乐影视网站建设方案文章目录 1. 节点定义2. 前中后序遍历2. 1 遍历规则2. 2 遍历实现2. 3 结点个数2. 3. 1 二叉树节点个数2. 3. 2 二叉树叶子节点个数2. 3. 3 二叉树第k层节点个数 2. 4 二叉树查找值为x的节点2. 5 二叉树层序遍历2. 6 判断二叉树是否是完全二叉树 3. 二叉树性质 1. 节点定义
用… 文章目录 1. 节点定义2. 前中后序遍历2. 1 遍历规则2. 2 遍历实现2. 3 结点个数2. 3. 1 二叉树节点个数2. 3. 2 二叉树叶子节点个数2. 3. 3 二叉树第k层节点个数 2. 4 二叉树查找值为x的节点2. 5 二叉树层序遍历2. 6 判断二叉树是否是完全二叉树 3. 二叉树性质 1. 节点定义
用链表来表示一棵二叉树即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址其基本结构如下
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data; //数据struct BinaryTreeNode* left; //左孩子struct BinaryTreeNode* right; //右孩子
}BTNode;链式二叉树的创建方式比较复杂为了更好地对接口进行调试我们先手动创建一棵链式二叉树进行测试
//创建节点
BTNode* BuyBTNode(int val)
{BTNode * newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail);return NULL;}newnode-data val;newnode-left NULL;newnode-right NULL;return newnode;
}
BTNode * CreateTree()
{BTNode * n1 BuyBTNode(1);BTNode * n2 BuyBTNode(2);BTNode * n3 BuyBTNode(3);BTNode * n4 BuyBTNode(4);BTNode * n5 BuyBTNode(5);BTNode * n6 BuyBTNode(6);BTNode * n7 BuyBTNode(7);//手动将他们连接起来成为一棵二叉树n1-left n2;n1-right n4;n2-left n3;n4-left n5;n4-right n6;n5-left n7;return n1;
}接下来就可以用这棵二叉树对接口进行测试。
2. 前中后序遍历
二叉树不同于之前的顺序结构不能直接进行依次遍历必须按照一定的规则进行遍历。 注堆也是一种二叉树但是堆不能进行遍历所以没有这方面的考虑。 另外二叉树的链式结构是一个递归的结构几乎所有的接口实现都需要用到递归的思想。
2. 1 遍历规则
按照规则二叉树的遍历有前序/中序/后序的递归结构遍历:
前序遍历(Preorder Traversal亦称先序遍历)访问根结点的操作发生在遍历其左右子树之前 访问顺序为根结点、左子树、右子树中序遍历(lnorder Traversal)访问根结点的操作发生在遍历其左右子树中间 访问顺序为左子树、根结点、右子树后序遍历(Postorder Traversal)访问根结点的操作发生在遍历其左右子树之后 访问顺序为左子树、右子树、根结点
我们以前序遍历解释一下怎么遍历 从根节点1开始遍历先输出根节点数据1然后来到左孩子2输出2来到2的左孩子3输出3来到3的左孩子NULL回退至3来到3的右孩子NULL再回退3节点遍历完毕回退至2来到2的右节点NULL回退至2,2节点遍历完毕回退至1来到1的右孩子4先输出4再来到4的左孩子4输出4遍历左右俩孩子都为空回退至上面的4来到4的右孩子5输出5后俩孩子都为空再最终回退至1根节点遍历完成该二叉树遍历完成。 前序遍历结果123456 中序遍历结果321546 后序遍历结果315641
2. 2 遍历实现
在实现时我们可以把每一个孩子都看成一个二叉树的根节点以方便递归遍历。
//前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (!root)return;printf(%d , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);
}
//后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (!root)return;BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);printf(%d , root-data);
}
//中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (!root)return;BinaryTreePrevOrder(root-left);printf(%d , root-data);BinaryTreePrevOrder(root-right);
}2. 3 结点个数
2. 3. 1 二叉树节点个数
int BinaryTreeSize(BTNode* root);二叉树中只有结点没有把数据个数存储起来那么我们要怎么获取二叉树中元素的个数呢 有两种思路一个是创建全局变量然后通过任意一种遍历方式遍历二叉树每遍历一次都让这个变量那么就能得到节点的个数了但是这样会带来两个问题
全局变量每次都要归0但是由于是递归进行遍历的所以需要写一个子函数用于递归。在函数内部调用全部变量可能会存在危险因为这个变量是任何函数都能访问并修改的。
基于这样的原因我们不采用这个方式。 而是通过计算这个节点本身左子树节点的个数右子树节点的个数的方式进行递归。
int BinaryTreeSize(BTNode* root)
{if (!root)return 0;return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right); //1就是该节点本身再加上左右两棵子树
}2. 3. 2 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);叶子节点的特点就是root-left NULL root-right NULL所以只要加上一个判断是否要1其他的就和计算节点个数的思路是一样的。
int BinaryTreeLeafSize(BTNode* root)
{//如果是叶子节点就没必要继续向下传递了直接回归就可以了if (!root)return 0;if (root-left NULL root-right NULL)return 1;return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right);
}2. 3. 3 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);在传递时增加一个参数k来判断递归到哪一层了如果是目标层数就1回归其他与计算二叉树叶子节点个数思路一致。
int BinaryTreeLevelKSize(BTNode* root, int k)
{//同理到目标层数之后就不需要继续向下传递了if (!root)return 0;if (k 1)return 1;return BinaryTreeLevelKSize(root-left, k - 1) BinaryTreeLevelKSize(root-right, k - 1);
}2. 4 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);在二叉树中遍历并对比数据如果找到了就返回这个节点的指针没找到就返回NULL。
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (!root)return NULL;if (root-data x)return root;//需要分别判断左右子树中有没有这个数据//左BTNode* leftfind BinaryTreeFind(root-left,x);if (leftfind)return leftfind;//右BTNode* rightfind BinaryTreeFind(root-right,x);if (rightfind)return rightfind;//没找到返回空return NULL;
}2. 5 二叉树层序遍历
除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。 设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 实现层序遍历需要额外借助队列这一数据结构。 层序遍历就是一层一层地从左到右地进行遍历比如上面这棵二叉树的层序遍历就是1 2 3 4 5 6 7
大致思路为创建一个数据类型为BTNode*的队列先将根节点入队列然后分别将它的左右孩子入队列接着出队列一次。然后把队头的左右孩子如果不为NULL入队列再出队列一次每次出队列前都要把它的值打印出来循环以上过程直到队列为空。
注这里的队列不再实现可以看这篇博客。
void BinaryTreeLevelOrder(BTNode* root)
{//二叉树判空if (!root)printf(null\n);//创建队列并初始化Queue qu;QueueInit(qu);//把根节点入队列QueuePush(qu, root);while (!QueueEmpty(qu)){//将队头的左右子树入队列并将队头数据打印再出队列一次BTNode* tmp QueueFront(qu);QueuePop(qu);printf(%d , tmp-data);if (tmp-left)QueuePush(qu, tmp-left);if (tmp-right)QueuePush(qu, tmp-right);}//销毁队列QueueDestroy(qu);printf(\n);
}2. 6 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);完全二叉树的特点是第X层没有完全放满时X1层不能有节点且没有满的层的节点必须是从左往右排布的。
我们可以借助层序遍历来判断二叉树是不是完全二叉树。 步骤为就算节点为空也要入队列直到出队列时遇到了空节点时开始连续出队列如果队列中剩下的元素中有非空的节点就说明不是完全二叉树。
我们以这棵二叉树为例 当轮到4的左孩子尽管不存在但先这么理解一下出队列时开始不再入队列只出队列并判断是否为空这时队列中还有4的右节点7那就判断出来了二叉树不是完全二叉树。
如果在第一次出队列的为空节点的之后的节点都是空节点比如上面这个二叉树没有节点7那就是完全二叉树。
bool BinaryTreeComplete(BTNode* root)
{assert(root);Queue qu;QueueInit(qu);QueuePush(qu, root);while (!QueueEmpty(qu)){BTNode* tmp QueueFront(qu);//如果出队列的是空节点就停止这个循环if (!tmp)break;QueuePop(qu);QueuePush(qu, tmp-left);QueuePush(qu, tmp-right);}//这个循环只出不入while (!QueueEmpty(qu)){//如果队列中还有空节点就说明不是完全二叉树if (QueueFront(qu)){QueueDestroy(qu);return false;}QueuePop(qu);}QueueDestroy(qu);return true;
}3. 二叉树性质
对任何一棵二叉树,如果度为 0 的叶结点个数为n0度为 2 的分支结点个数为n2 则有 n0 n21 证明 假设一个二叉树有 a 个度为 2 的节点b 个度为 1 的节点c 个叶节点则这个二叉树的边数是 2ab 另一方面由于共有 abc 个节点所以边数等于 abc-1 结合上面两个公式: 即 2ab abc-1即 ac-1
题目练习 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A 不存在这样的二叉树 B 200 C 198 D 199 有199个度为2的节点那么在二叉树中度为0的节点有1991也就是200个选B。 在具有 2n 个结点的完全二叉树中叶子结点个数为() A n B n1 C n-1 D n/2 设叶子节点有x个那么度为2的节点为x-1个。有2n个节点所以度为1的节点有2n-2x1条而完全二叉树中度为1的节点只有0或1个但是这个二叉树的结点个数为偶数由于根节点有1个而其他的除了最后一层的结点个数都是偶数所以度为1的结点个数为1。解方程2n-2x11就可以得出xn。选A。 一棵完全二叉树的结点数位为531个那么这棵树的高度为() A 11 B 10 C 8 D 12 完全二叉树每一层的节点个数为2n-1个那么根据等比数列的求和公式完全二叉树前n层的节点个数为2n-1解方程2n-1531可得n为10选B。 一个具有767个结点的完全二叉树其叶子结点个数为() A 383 B 384 C 385 D 386 设叶子节点有x个那么度为2的节点为x-1个度为1的节点为768-2x个通过第2题的分析我们可知度为1的节点为0个就可以算出x384选B。
数据结构初阶的二叉树就到这里想必你会发现这个二叉树我们没有实现插入删除的接口因为二叉树的插入删除使用C语言实现过于复杂会在高阶数据结构中讲解。
谢谢你的阅读喜欢的话来个点赞收藏评论关注吧 我会持续更新更多优质文章
我的博客即将同步至腾讯云开发者社区邀请大家一同入驻https://cloud.tencent.com/developer/support-plan?invite_code10p1y5y691zy4 文章转载自： http://www.morning.gfnsh.cn.gov.cn.gfnsh.cn http://www.morning.lxthr.cn.gov.cn.lxthr.cn http://www.morning.hdpcn.cn.gov.cn.hdpcn.cn http://www.morning.fjgwg.cn.gov.cn.fjgwg.cn http://www.morning.bybhj.cn.gov.cn.bybhj.cn http://www.morning.dzfwb.cn.gov.cn.dzfwb.cn http://www.morning.lpcct.cn.gov.cn.lpcct.cn http://www.morning.hsflq.cn.gov.cn.hsflq.cn http://www.morning.bhgnj.cn.gov.cn.bhgnj.cn http://www.morning.mzjbz.cn.gov.cn.mzjbz.cn http://www.morning.rbnnq.cn.gov.cn.rbnnq.cn http://www.morning.kzyr.cn.gov.cn.kzyr.cn http://www.morning.xyjlh.cn.gov.cn.xyjlh.cn http://www.morning.wtsr.cn.gov.cn.wtsr.cn http://www.morning.spnky.cn.gov.cn.spnky.cn http://www.morning.ylkkh.cn.gov.cn.ylkkh.cn http://www.morning.tlnkz.cn.gov.cn.tlnkz.cn http://www.morning.lkhgq.cn.gov.cn.lkhgq.cn http://www.morning.lhgqc.cn.gov.cn.lhgqc.cn http://www.morning.nqmhf.cn.gov.cn.nqmhf.cn http://www.morning.yqtry.cn.gov.cn.yqtry.cn http://www.morning.yuminfo.com.gov.cn.yuminfo.com http://www.morning.lbjdx.cn.gov.cn.lbjdx.cn http://www.morning.gmswp.cn.gov.cn.gmswp.cn http://www.morning.ptqds.cn.gov.cn.ptqds.cn http://www.morning.kcxtz.cn.gov.cn.kcxtz.cn http://www.morning.dmthy.cn.gov.cn.dmthy.cn http://www.morning.fhddr.cn.gov.cn.fhddr.cn http://www.morning.cfocyfa.cn.gov.cn.cfocyfa.cn http://www.morning.smcfk.cn.gov.cn.smcfk.cn http://www.morning.jtfsd.cn.gov.cn.jtfsd.cn http://www.morning.cszbj.cn.gov.cn.cszbj.cn http://www.morning.hrrmb.cn.gov.cn.hrrmb.cn http://www.morning.ppbqz.cn.gov.cn.ppbqz.cn http://www.morning.tmcmj.cn.gov.cn.tmcmj.cn http://www.morning.mygbt.cn.gov.cn.mygbt.cn http://www.morning.jggr.cn.gov.cn.jggr.cn http://www.morning.klltg.cn.gov.cn.klltg.cn http://www.morning.lnnc.cn.gov.cn.lnnc.cn http://www.morning.lwqst.cn.gov.cn.lwqst.cn http://www.morning.fdjwl.cn.gov.cn.fdjwl.cn http://www.morning.kpxnz.cn.gov.cn.kpxnz.cn http://www.morning.cdygl.com.gov.cn.cdygl.com http://www.morning.llfwg.cn.gov.cn.llfwg.cn http://www.morning.clwhf.cn.gov.cn.clwhf.cn http://www.morning.plkrl.cn.gov.cn.plkrl.cn http://www.morning.qkskm.cn.gov.cn.qkskm.cn http://www.morning.vvdifactory.com.gov.cn.vvdifactory.com http://www.morning.ggmls.cn.gov.cn.ggmls.cn http://www.morning.ndtmz.cn.gov.cn.ndtmz.cn http://www.morning.dhdzz.cn.gov.cn.dhdzz.cn http://www.morning.plfy.cn.gov.cn.plfy.cn http://www.morning.zwxfj.cn.gov.cn.zwxfj.cn http://www.morning.gsjw.cn.gov.cn.gsjw.cn http://www.morning.wlqll.cn.gov.cn.wlqll.cn http://www.morning.yydzk.cn.gov.cn.yydzk.cn http://www.morning.qglqb.cn.gov.cn.qglqb.cn http://www.morning.ffbl.cn.gov.cn.ffbl.cn http://www.morning.zpqlf.cn.gov.cn.zpqlf.cn http://www.morning.jjnql.cn.gov.cn.jjnql.cn http://www.morning.cnxpm.cn.gov.cn.cnxpm.cn http://www.morning.gcrlb.cn.gov.cn.gcrlb.cn http://www.morning.mmtjk.cn.gov.cn.mmtjk.cn http://www.morning.bkslb.cn.gov.cn.bkslb.cn http://www.morning.tklqs.cn.gov.cn.tklqs.cn http://www.morning.ykyfq.cn.gov.cn.ykyfq.cn http://www.morning.rbnnq.cn.gov.cn.rbnnq.cn http://www.morning.zknxh.cn.gov.cn.zknxh.cn http://www.morning.mfsjn.cn.gov.cn.mfsjn.cn http://www.morning.dyhlm.cn.gov.cn.dyhlm.cn http://www.morning.xjnw.cn.gov.cn.xjnw.cn http://www.morning.nqbcj.cn.gov.cn.nqbcj.cn http://www.morning.c7493.cn.gov.cn.c7493.cn http://www.morning.zknxh.cn.gov.cn.zknxh.cn http://www.morning.okiner.com.gov.cn.okiner.com http://www.morning.wzjhl.cn.gov.cn.wzjhl.cn http://www.morning.zmyhn.cn.gov.cn.zmyhn.cn http://www.morning.rdnjc.cn.gov.cn.rdnjc.cn http://www.morning.mwqbp.cn.gov.cn.mwqbp.cn http://www.morning.elmtw.cn.gov.cn.elmtw.cn
