方维服务客户类型,seo查询站长工具,重庆营销型网站开发,网站开发微信支付功能✨✨所属专栏#xff1a;数据结构✨✨ ✨✨作者主页#xff1a;嶔某✨✨ 二叉树的遍历
前序、中序以及后序遍历
学习二叉树结构#xff0c;最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则#xff0c;依次对二叉树中的结点进行相应的操作#xff… ✨✨所属专栏数据结构✨✨ ✨✨作者主页嶔某✨✨ 二叉树的遍历
前序、中序以及后序遍历
学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的结点进行相应的操作并且每个结点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历 1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。 2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。 3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。 由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 // 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){ printf(# );return;}printf(%c ,root-_data);BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{if (root NULL){printf(# );return;}BinaryTreePrevOrder(root-_left);printf(%c , root-_data);BinaryTreePrevOrder(root-_right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{if (root NULL){printf(# );return;}BinaryTreePrevOrder(root-_left);BinaryTreePrevOrder(root-_right);printf(%c , root-_data);
}
层序遍历
层序遍历除了前序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1层序遍历就是从所在二叉树的根结点出发首先访问第一层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。
这里与前、中、后序遍历不同的是层序遍历用的迭代而非递归。创建一个队列将整个树的根节点入队之后再将根节点的左右节点入队。让上一层节点带动下一层父节点将子女节点带入队之后将父节点拿出队列这样就实现了层序遍历。
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{assert(root);Queue q;QueueInit(q);QueuePush(q,root);while (QueueSize(q)){BTNode* front QueueFront(q);QueuePop(q);printf(%c , front-_data);if (front-_left)QueuePush(q,front-_left);if(front-_right)QueuePush(q,front-_right);}
} 其他函数
通过前序遍历数组创建二叉树 判断下标为i的字符是否为#如果不为#那就新malloc一个节点将数据放进去新节点的左右节点分别再递归赋值。
BTNode* BinaryTreeCreate(BTDataType* a,int* pi)
{if (a[*pi] #){(*pi);return NULL;}BTNode* new (BTNode*)malloc(sizeof(BTNode));if (new NULL){perror(malloc is fail);return NULL;}new-_data a[(*pi)];new-_left BinaryTreeCreate(a, pi);new-_right BinaryTreeCreate(a, pi);return new;
}
销毁二叉树
如果当前节点为空那么就释放如果当前节点不为空那么就先递归释放左右子树,左右子树释放后再将根节点释放并置空。
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root NULL){free(*root);return;}BinaryTreeDestory((*root)-_left);BinaryTreeDestory((*root)-_right);free(*root);*root NULL;
}
二叉树节点个数
如果当前节点为空返回0如果当前节点不为空返回其左右子树的节点个数1。
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL)return 0;return BinaryTreeSize(root-_left) BinaryTreeSize(root-_right) 1;
}
二叉树叶子节点个数
如果节点的左右节点都为空返回1否则返回左右子树的叶子节点个数。
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL)return 0;if (root-_left NULL root-_right NULL)return 1;return BinaryTreeLeafSize(root-_left) BinaryTreeLeafSize(root-_right);
}
二叉树第k层节点个数
第k层节点的个数可以看作第一层的左右节点的第k-1层节点个数因此当k 1时此层就是要计算再内的节点。
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL)return 0;if (k 1)return 1;return BinaryTreeLevelKSize(root-_left, k - 1) BinaryTreeLevelKSize(root-_right, k - 1);
}
二叉树查找值为x的节点
采取前序遍历如果根节点的值等于x返回root否则先判断左子树有无符合节点若有返回对应的节点反之返回另一个子树的对应节点若左右字数都没有对应节点最终将返回空
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL)return NULL;if (root-_data x)return root;BTNode* ret1 BinaryTreeFind(root-_left, x);if (ret1 ! NULL)return ret1;return BinaryTreeFind(root-_right, x);
}
判断二叉树是否为完全二叉树
建立一个队列和层序遍历一样当遇到空节点时跳出循环开始判断。如果再空节点的后面还有非空节点那么这棵树就不是完全二叉树。反之此树空节点之后的所有的节点都为空那么此树为完全二叉树。 // 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{assert(root);Queue q;QueueInit(q);QueuePush(q, root);while (QueueSize(q)){BTNode* front QueueFront(q);QueuePop(q);if (front NULL)break;QueuePush(q, front-_left);QueuePush(q, front-_right);}while (QueueSize(q)){BTNode* front QueueFront(q);QueuePop(q);if (front){Destory(q);return false;}}return true;
}
本期博客到这里就结束了如果有什么错误欢迎指出如果对你有帮助请点个赞谢谢
