旗舰店的网站怎么做,jquery上传wordpress,v9双语版网站怎么做,免费个人网页制作成品个人主页#xff1a;日刷百题
系列专栏#xff1a;〖C语言小游戏〗〖Linux〗〖数据结构〗 〖C语言〗
#x1f30e;欢迎各位→点赞#x1f44d;收藏⭐️留言#x1f4dd; 一、二叉树的创建 这里我们使用先序遍历的思想来创建二叉树#xff0c;这里的内容对于刚接触二… 个人主页日刷百题
系列专栏〖C语言小游戏〗〖Linux〗〖数据结构〗 〖C语言〗
欢迎各位→点赞收藏⭐️留言 一、二叉树的创建
这里我们使用先序遍历的思想来创建二叉树这里的内容对于刚接触二叉树的朋友可能有些难理解不妨先看完下面的二叉树各种遍历再来看创建就会简单很多为了保持文章的整体性先讲二叉树的创建。 当然为了后续内容能够衔接我们先手动创建一个固定的树就是上面这棵树后续内容全部围绕这棵树 typedef int DataType;
typedef struct TreeNode
{DataType data;struct TreeNode* left;struct TreeNode* right;
}TreeNode;
TreeNode* BuyNode(int x)
{TreeNode* node (TreeNode*)malloc(sizeof(TreeNode));if (node NULL){perror(malloc fail:);return NULL;}node-data x;node-left node-right NULL;
}TreeNode* CreatTree()
{TreeNode* node1 BuyNode(1);TreeNode* node2 BuyNode(2);TreeNode* node3 BuyNode(3);TreeNode* node4 BuyNode(4);TreeNode* node5 BuyNode(5);TreeNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
} 现在开始讲如何用前序遍历方式来进行创建二叉树这里给俩种创建方法。 1.1 返回根节点指针创建 注我们用前序遍历方式输入数字-1代表空上面的二叉树可写为1 2 3 -1 -1 -1 4 5 -1 -1 6 -1 -1 TreeNode* CreatTree()
{int i;scanf(%d, i);if (i -1){return NULL;}TreeNode* root (TreeNode*)malloc(sizeof(TreeNode));if (root NULL){perror(malloc fail:);exit(-1);}root-data i;root-left CreatTree();root-right CreatTree();return root;
}注return root 是不能省略的递归返回时遇到空返回或者构建完子数返回根节点作为上一级左子树构建完子树返回根节点作为上一级右子树依次递归回去直到返回整个数的根节点 1.2 二级指针传参创建 同样的依然构建上面的而二叉树用前序遍历方式输入数字-1代表空上面的二叉树可写为1 2 3 -1 -1 -1 4 5 -1 -1 6 -1 -1 void CreatTree(TreeNode** root)
{int i;scanf(%d, i);if (i -1){*root NULL;}else{*root (TreeNode*)malloc(sizeof(TreeNode));if (*root NULL){perror(malloc fail:);exit(-1);}(*root)-data i;CreatTree(((*root)-left));CreatTree(((*root)-right));}} 注二级指针传参可以改变一级指针的指向同样的这里创建好根节点后创造左子树在创造右子树依次递归下去。 二、二叉树的遍历
我们先从最简单的操作----遍历学起。所谓二叉树遍历(Traversal)就是按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个节点有且只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。二叉树的遍历分为四种前序遍历、中序遍历、后序遍历和层序遍历。 2.1 前序遍历 前序遍历Preorder Traversal又称先根遍历即先遍历根结点再遍历左子树最后遍历右子树。而对于子树的遍历也服从上述规则。利用递归我们可以很快地写出代码 // 二叉树前序遍历
void PreOrder(TreeNode* root)
{if (root NULL){printf(NULL );return ;}printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);} 便于我们更好的理解我们画出递归展开图 2.2 中序遍历 中序遍历Inorder Traversal又称中根遍历即先遍历左子树再遍历根结点最后遍历右子树。同样子树的遍历规则也是如此。递归代码如下 // 二叉树中序遍历
void InOrder(TreeNode* root)
{if (root NULL){printf(NULL );return ;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
} 2.3 后序遍历 后序遍历Inorder Traversal又称后根遍历即先遍历左子树再遍历右子树最后遍历根结点。递归代码如下 // 二叉树后序遍历
void PostOrder(TreeNode* root)
{if (root NULL){printf(NULL );return ;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
} 2.4 层序遍历 除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推 自上而下自左至右逐层访问树的结点 的过程就是层序遍历。 层序遍历借助队列实现思路解析图如下 //层序遍历
void LevelOrder(TreeNode* root)
{Queue pq;QueueInit(pq);if (root NULL){QueueDestroy(pq);return;}QueuePush(pq,root);while (!QueueEmpty(pq)){TreeNode* front QueueFront(pq);printf(%d , front-data);QueuePop(pq);if (front-left! NULL){QueuePush(pq, front-left);}if (front-right ! NULL){QueuePush(pq, front-right);}}QueueDestroy(pq);
} 思考当然层序遍历这里有一个变形我们能不能将二叉树每一层打印单独放一行该怎么做呢 思路 1设二叉树的根节点所在层数为1第一层根节点进队列队列元素个数为1size1 2每出队列一次size--,根节点出完队列俩个子节点进队列,此时队列元素个数为第二层节点个数size2 3当我们出队列size次把第二层元素出完队列剩下的元素是第三层节点sizeQueueSize 以此类推以size为循环条件则可实现每层单独打印一行 void LevelOrder(TreeNode* root)
{Queue pq;QueueInit(pq);if (root NULL){QueueDestroy(pq);return;}QueuePush(pq,root);int size 1;while (!QueueEmpty(pq)){while (size--){TreeNode* front QueueFront(pq);printf(%d , front-data);QueuePop(pq);if (front-left ! NULL){QueuePush(pq, front-left);}if (front-right ! NULL){QueuePush(pq, front-right);}}size QueueSize(pq);printf(\n);}QueueDestroy(pq);
} 三、二叉树的结点 3.1 二叉树的总结点数 一颗二叉树的结点数我们可以看作是根结点左子树结点数右子树结点数那左右子树的结点数又是多少呢按照相同的方法继续拆分层层递归直到左右子树为空树返回空树的结点数0即可。递归代码如下 // 二叉树节点个数
int TreeSize(TreeNode* root)
{return root NULL? 0 : TreeSize(root-left) TreeSize(root-right) 1;
} 3.2 二叉树的叶子结点数 左右子树都为空的结点即是叶子结点。这里分为两种情况左右子树都为空和左右子树不都为空。 1当左右子树都为空时则这颗树的叶子结点数为1(根节点)。 2当左右子树不都为空即根结点不是叶子结点时这棵树的叶子结点数就为左子树叶子结点数右子树叶子结点数空树没有叶子结点。 // 二叉树叶子节点个数
int TreeLeafSize(TreeNode* 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层结点。注当前节点为第一层 1若为空树无论哪层节点数都是0 2若不是空树且k1,则只有一个节点根节点 // 二叉树第k层节点个数
int TreeLevelKSize(TreeNode* root, int k)
{assert(k 0);if (root!NULLk 1){return 1;}if (root NULL){return 0;}if (k 1){return TreeLevelKSize(root-left, k - 1) TreeLevelKSize(root-right, k - 1);}
}// 判断二叉树是否是完全二叉树
bool TreeComplete(TreeNode* root)
{Queue pq;QueueInit(pq);if (root NULL){QueueDestroy(pq);return;}QueuePush(pq, root);while (!QueueEmpty(pq)){TreeNode* front QueueFront(pq);QueuePop(pq);if (front NULL){break;}QueuePush(pq, front-left);QueuePush(pq, front-right);}while (!QueueEmpty(pq)){TreeNode* front QueueFront(pq);QueuePop(pq);if (front ! NULL){return false;}}QueueDestroy(pq);return true;
} 四、二叉树的查找 二叉树的查找本质上就是一种遍历只不过是将之前的打印操作换为查找操作而已。我们可以使用前序遍历来进行查找 1先比较根结点是否为我们要查找的结点如果是返回根节点地址 2如果不是遍历左子树如果左子树是直接返回节点地址不是则遍历右子树如果右子树是直接返回节点地址不是返回空说明左右子树都没找到。 // 二叉树查找值为x的节点
TreeNode* TreeFind(TreeNode* root, DataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}TreeNode* node1 TreeFind(root-left, x);if (node1){return node1;}TreeNode* node2 TreeFind(root-right, x);if (node2){return node2;}return NULL;
} 五、二叉树的高度/深度 树中结点的最大层次称为二叉树的高度。因此一颗二叉树的高度我们可以看作是 1(根结点)左右子树高度的较大值。层层递归下去直到遇到空树返回0即可 这里值得注意的是不要写成 return TreeHeight(root-left)TreeHeight(root-right) ? TreeHeight(root-left)1:TreeHeight(root-right)1;
} 这里比较好左右子树较大的一颗后又会从新递归较大那颗子树高度会造成重复计算时间复杂度增高。 我们要保存好左右子树层数避免重复计算代码如下 //二叉树的高度
int TreeHeight(TreeNode* root)
{if (root NULL){return 0;}int left TreeHeight(root-left);int right TreeHeight(root-right);return leftright ? left1:right1;
} 六、完全二叉树的判断 这里的思路利用了层序遍历不同的是将空节点指针也入队列当我们遇到第一个空节点指针则退出循环然后对队列进行检测若第一个空节点指针以后全都是空则为完全二叉树反之不为完全二叉树。 注当在队列遇到第一个空节点指针时二叉树中空节点指针之后所有非空节点指针全部进队列 思路解析图如下 代码如下
// 判断二叉树是否是完全二叉树
bool TreeComplete(TreeNode* root)
{Queue pq;QueueInit(pq);if (root NULL){QueueDestroy(pq);return;}QueuePush(pq, root);while (!QueueEmpty(pq)){TreeNode* front QueueFront(pq);QueuePop(pq);if (front NULL){break;}QueuePush(pq, front-left);QueuePush(pq, front-right);}while (!QueueEmpty(pq)){TreeNode* front QueueFront(pq);QueuePop(pq);if (front ! NULL){return false;}}QueueDestroy(pq);return true;
} 七、二叉树的销毁
7.1 一级指针传参销毁
同样的和创建节点一样我们给出俩个销毁方式
(1)一种是传一级指针方式这种方式不是改变根节点的指向需要在销毁函数结束后将root置为NULL
void TreeDestroy(TreeNode* root)//出来将rootNULL
{if (root NULL){return;}TreeDestroy(root-left);TreeDestroy(root-right);free(root);}
7.2 二级指针传参销毁
(2)另一种是传二级指针直接在函数内部将每一个销毁的节点指针置为NULL.
void TreeDestroy(TreeNode** root)
{if (*root NULL){return;}TreeDestroy((*root)-left);TreeDestroy((*root)-right);free(*root);*root NULL;
} 总结本篇文章将二叉树的基础知识差不多囊括了后续的话还需要大量练习做巩固加强递归比较抽象难以理解需要动手画递归展开图进行帮助理解。
希望大家阅读完可以有所收获同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言百题一定会认真阅读
