公司网站设计用什么,淘宝客导购网站 丢单,网站建设一对一培训,物业管理系统app#x1f493;博主个人主页:不是笨小孩#x1f440; ⏩专栏分类:数据结构与算法#x1f440; 刷题专栏#x1f440; C语言#x1f440; #x1f69a;代码仓库:笨小孩的代码库#x1f440; ⏩社区#xff1a;不是笨小孩#x1f440; #x1f339;欢迎大家三连关注… 博主个人主页:不是笨小孩 ⏩专栏分类:数据结构与算法 刷题专栏 C语言 代码仓库:笨小孩的代码库 ⏩社区不是笨小孩 欢迎大家三连关注一起学习一起进步 二叉树 二叉树的性质二叉树的链式结构二叉树的遍历前序遍历中序遍历后序遍历层序遍历 二叉树的销毁二叉树的查找 二叉树的性质 1.若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1) 个结点. 2. 若规定根节点的层数为1则深度为h的二叉树的最大结点数是 2^h-1. 3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为02 ,则有n0 n2 1 4. 若规定根节点的层数为1具有n个结点的满二叉树的深度h . (ps 是log以2为底n1为对数) 5. 对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 若i0i位置节点的双亲序号(i-1)/2i0i为根节点编号无双亲节点若2i1n左孩子序号2i12i1n否则无左孩子若2i2n右孩子序号2i22i2n否则无右孩子 二叉树的链式结构
一般来说二叉树分为二叉链和三叉链二叉链就是结构里面一个左孩子节点一个右孩子节点三叉链多了一个父亲节点我们比较经常见的都是二叉链的所以我们主要讲的也是二叉链。
结构
typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode; 我们在看任意一颗二叉树时都可以将它分为三部分根左子树右子树左子树也可看成根左子树右子树右子树也可看成根左子树右子树因此二叉树定义是递归式的我们后面的代码也是主要靠递归来实现的。 二叉树的遍历 二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。 二叉树的遍历分为前序遍历、中序遍历、后序遍历、层序遍历其中前中后序遍历是递归定义的而层序遍历是非递归遍历的。
前序遍历 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。前序先访问根节点再访问左子树再访问右子树。 代码如下
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){return;}printf(%d , root-data);BinaryTreePrevOrder(root-left);BinaryTreePrevOrder(root-right);
}递归图 大家可以根据这个递归展开图好好理解一下后面的二叉树基本操作都是需要用递归来实现的。
中序遍历 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。 代码如下
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){return;}BinaryTreeInOrder(root-left);printf(%d , root-data);BinaryTreeInOrder(root-right);}后序遍历 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 代码如下
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){return;}BinaryTreePostOrder(root-left);BinaryTreePostOrder(root-right);printf(%d , root-data);
}这三种遍历本质上都是一样的理解清楚一个另外两个就很简单了。 层序遍历 层序遍历和其他三种都不一样设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 那这个要怎么实现呢 我们需要借助我们的队列我们可以先把根节点入到队列里然后开始出队列只不过每次出的时候如果它的左孩子不为空就将左孩子入队列右孩子不为空就将右孩子入队列以此类推。我们就是利用了队列的先进先出我们就可以轻松地完成层序遍历。 代码如下
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root){QueuePush(q,root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);if (front-left){QueuePush(q, front-left);}if (front-right){QueuePush(q, front-right);}printf(%d , front-data);}printf(\n);
}二叉树的销毁 二叉树的销毁很简单我们需要遍历一遍二叉树但是我们用那种遍历呢如果用前序那么就会销毁根节点就找不到它的左孩子和右孩子明显是不合适的最好的情况就是我们先去销毁它的左孩子再去销毁他的右孩子然后再销毁根节点所以这里我们使用后序遍历是比较合适的。 代码如下
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{if (root NULL){return;}BinaryTreeDestory(root-left);BinaryTreeDestory(root-right);free(root);
}二叉树的查找 二叉树的查找的基本思路也是遍历一遍二叉树但是我们需要返回这个节点这就给我们的难度增加了很多我们这里想的是先看根节点是不是如果不是就去他的左子树找如果找到了就返回否则就去它的右子树找找到就返回该节点最后都找不到我们就返回NULL. 代码如下
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* left BinaryTreeFind(root-left, x);if (left ! NULL){return left;}BTNode* right BinaryTreeFind(root-right, x);if (right ! NULL){return right;}return NULL;
}最后带大家看一下会给我们带来好运的树
今天的分享就到这里感谢大家的关注和支持
