档案网站建设图片,wordpress 输出标签,哪些企业需要网络推广,先做网站再付款#x1f525;博客主页#xff1a; 小羊失眠啦. #x1f3a5;系列专栏#xff1a;《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞#x1f44d;收藏⭐评论✍️ 文章目录 一、前置说明二、二叉树的遍历2.1 前序遍历2.2 中序遍历2.3 后序遍历2.4 层序遍历 三、… 博客主页 小羊失眠啦. 系列专栏《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞收藏⭐评论✍️ 文章目录 一、前置说明二、二叉树的遍历2.1 前序遍历2.2 中序遍历2.3 后序遍历2.4 层序遍历 三、二叉树的结点个数3.1 二叉树的总结点数3.2 二叉树的叶子结点数3.3 二叉树第k层结点数 四、二叉树的高度/深度五、二叉树的查找六、二叉树的创建和销毁 一、前置说明
在学习二叉树各种各样的操作前我们先来回顾一下二叉树的概念
二叉树是度不超过2的树由根结点和左右2个子树组成每个子树也可以看作一颗二叉树又可以拆分为根结点和左右两颗子树… 是不是很熟悉一个大问题可以拆分为两个子问题每个子问题又可以拆分为更小的子问题这样层层拆分到不可拆分遇到空树的过程不就是递归吗因此我们可以得出 树是递归定义的后续树的各种操作正是围绕着这一点进行的。 二、二叉树的遍历
我们先从最简单的操作----遍历学起。所谓二叉树遍历(Traversal)就是按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个节点有且只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。二叉树的遍历分为四种前序遍历、中序遍历、后序遍历和层序遍历。
2.1 前序遍历
前序遍历Preorder Traversal又称先根遍历即先遍历根结点再遍历左子树最后遍历右子树。而对于子树的遍历也服从上述规则。利用递归我们可以很快地写出代码
//前序遍历
void PrevOrder(BTNode* root) {//遇到空树递归终点if (root NULL) {printf(NULL );return;}//对根节点进行操作此处为打印printf(%d , root-val);//递归遍历左子树PrevOrder(root-left);//递归遍历右子树PrevOrder(root-right);
}为了更好地理解这个过程我们可以画出递归展开图如下 2.2 中序遍历
中序遍历Inorder Traversal又称中根遍历即先遍历左子树再遍历根结点最后遍历右子树。同样子树的遍历规则也是如此。递归代码如下
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%d , root-val);InOrder(root-right);
}2.3 后序遍历
后序遍历Inorder Traversal又称后根遍历即先遍历左子树再遍历右子树最后遍历根结点。照葫芦画瓢递归代码如下
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-val);
}2.4 层序遍历
除了上面的前中后序遍历还可以对二叉树进行层序遍历。所谓层序遍历就是从所在二叉树的根节点出发首先访问第1层的根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推。这样自上而下自左向右逐层访问树的结点的过程就是层序遍历。 与前面三种遍历不同层序遍历属于广度优先遍历因此我们可以利用队列先进先出的特性将每个结点一层一层依次入队然后依次出队进行操作即可。具体演示及代码如下 void LevelOrder(BTNode* root)
{Que q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);printf(%d , front-val);if (front-left)QueuePush(q, front-left);if (front-right)QueuePush(q, front-right);QueuePop(q);}printf(\n);QueueDestroy(q);
}三、二叉树的结点个数
3.1 二叉树的总结点数
一颗二叉树的结点数我们可以看作是根结点左子树结点数右子树结点数那左右子树的结点数又是多少呢按照相同的方法继续拆分层层递归直到左右子树为空树返回空树的结点数0即可。递归代码如下
int TreeSize(BTNode* root)
{return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}3.2 二叉树的叶子结点数
左右子树都为空的结点即是叶子结点。这里分为两种情况左右子树都为空和左右子树不都为空。 当左右子树都为空时则这颗树的叶子结点数为1(根节点)。 当左右子树不都为空即根结点不是叶子结点时这棵树的叶子结点数就为左子树叶子结点数右子树叶子结点数空树没有叶子结点。
int TreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-left NULL root-right NULL){return 1;}return TreeLeafSize(root-left) TreeLeafSize(root-right);
}3.3 二叉树第k层结点数
类似的一颗树第k层的结点数我们可以拆分为其左子树第k-1层结点右子树第k-1层结点。这样层层递归下去直到k1求树的第1层结点数时返回1(树的第1层只有根结点)而如果在递归过程中遇到空树就返回0(空树没有结点)。例如下面一颗树 int TreeKLevel(BTNode* root, int k)
{assert(k 0);if (root NULL)return 0;if (k 1){return 1;}return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}四、二叉树的高度/深度
树中结点的最大层次称为二叉树的高度。因此一颗二叉树的高度我们可以看作是
1(根结点)左右子树高度的较大值。层层递归下去直到遇到空树返回0即可递归代码如下
int TreeHeight(BTNode* root)
{if (root NULL)return 0;return fmax(TreeHeight(root-left), TreeHeight(root-right)) 1;
}五、二叉树的查找
二叉树的查找本质上就是一种遍历只不过是将之前的打印操作换为查找操作而已。我们可以使用前序遍历来进行查找先比较根结点是否为我们要查找的结点如果是之间返回如果不是遍历左子树和右子树返回其查找的结果如果都找不到返回空指针。代码如下
// 二叉树查找值为x的结点
BTNode* TreeFind(BTNode* root, int x)
{if (root NULL)return NULL;if (root-val x)return root;BTNode* ret NULL;ret TreeFind(root-left, x);if (ret)return ret;ret TreeFind(root-right, x);if (ret)return ret;return NULL;
}六、二叉树的创建和销毁
最后我们再来看看如何来创建和销毁一颗二叉树。我们前面说过二叉树是递归定义的。有了前面的基础二叉树的创建和销毁也就不是什么难事了。
BTNode* BuyNode(int x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));if (node NULL){perror(malloc fail);exit(-1);}node-val x;node-left NULL;node-right NULL;return node;
}// 二叉树销毁
void TreeDestroy(BTNode* root)
{if (root NULL){return;}TreeDestroy(root-left);TreeDestroy(root-right);free(root);//root NULL;
}本次的内容到这里就结束啦。希望大家阅读完可以有所收获同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言小羊一定认真修改写出更好的文章~~
