二叉树的遍历问题和相关算法（思路梳理和代码实现）

在主包的上一篇博客中我们介绍了堆的相关知识这篇博客我们便充分补充下二叉树的相关算法问题普及下常见的遍历方法。正片开始啦发车遍历前序中序后序补充层序遍历 )1. 遍历规则按照规则⼆叉树的遍历有前序/中序/后序的递归结构遍历1.前序遍历(Preorder Traversal 亦称先序遍历)访问根结点的操作发⽣在遍历其左右⼦树之前访问顺序为根结点、左⼦树、右⼦树2.中序遍历(Inorder Traversal)访问根结点的操作发⽣在遍历其左右⼦树之中间访问顺序为左⼦树、根结点、右⼦树3.后序遍历(Postorder Traversal)访问根结点的操作发⽣在遍历其左右⼦树之后访问顺序为左⼦树、右⼦树、根结点那么我们先挑战下分别用三种遍历方法来遍历这棵二叉树。答案在这里我们要熟悉掌握递归在有正确的逻辑思路后便能信手拈来。2.代码实现//前序遍历--根左右 void preOrder(BTNode* root) { if (root NULL) { return NULL; } printf(%d, root-data); preOrder(root-left); preOrder(root-right); }//中序遍历--左跟右 void inOrder(BTNode* root) { if (root NULL) { return NULL; } preOrder(root-left); printf(%d, root-data); preOrder(root-right); }//后序遍历--左右根 void postOrder(BTNode* root) { if (root NULL) { return NULL; } preOrder(root-left); preOrder(root-right); printf(%d, root-data); }3.层序遍历除了先序遍历、中序遍历、后序遍历外还可以对⼆叉树进⾏层序遍历。设⼆叉树的根结点所在层数为1层序遍历就是从所在⼆叉树的根结点出发⾸先访问第⼀层的树根结点然后从左到右访问第2层上的结点接着是第三层的结点以此类推⾃上⽽下⾃左⾄右逐层访问树的结点的过程就是层序遍历。实现层序遍历需要额外借助数据结构队列//层序遍历 void leverOrder(BTNode* root) { Queue q; QueueInit(q); QueuePush(q,root); while (!QueueEmpty(q)) { BTNode* top QueueFront(q); QueuePop(q); printf(%c ,top-data); if (top-left) QueuePush(q, top-left); QueuePush(q, top-right); } QueueDestroy(q); }二叉树的相关算法1.先前介绍// ⼆叉树结点个数 int BinaryTreeSize(BTNode* root); //int BinaryTreeSize(BTNode* root,int* psize); // ⼆叉树叶⼦结点个数 int BinaryTreeLeafSize(BTNode* root); // ⼆叉树第k层结点个数 int BinaryTreeLevelKSize(BTNode* root, int k); //⼆叉树的深度/⾼度 int BinaryTreeDepth(BTNode* root); // ⼆叉树查找值为x的结点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // ⼆叉树销毁 void BinaryTreeDestory(BTNode** root);2.代码实现1.二叉树结点个数int BinaryTreeSize(BTNode* root) { if (root NULL) { return 0; } return 1BinaryTreeSize(root-left) BinaryTreeSize(root-right); }2.⼆叉树叶⼦结点个数int BinaryTreeLeafSize(BTNode* root) { if (root NULL) { return 0; } if (root-right NULL root-left NULL) { return 1; } return BinaryTreeLeafSize(root-left) BinaryTreeLeafSize(root-right); }3.⼆叉树第k层结点个数int BinaryTreeLevelKSize(BTNode* root, int k) { if (root NULL) { return 0; } if (k1) { return 1; } return BinaryTreeLevelKSize(root-left,k-1) BinaryTreeLevelKSize(root-right,k-1); }4.⼆叉树的深度/⾼度int BinaryTreeDepth(BTNode* root) { if (root NULL) { return 0; } int leftDep BinaryTreeDepth(root-left); int rightDep BinaryTreeDepth(root-right); return 1 (leftDep rightDep ? leftDep:rightDep); }5.⼆叉树查找值为x的结点BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root NULL) { 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; } }6.⼆叉树销毁void BinaryTreeDestory(BTNode** root) { if (*root NULL) { return ; } BinaryTreeDestory(((*(root))-right)); BinaryTreeDestory(((*(root))-left)); free(*root); *root NULL; }做有意义的事过意义的人生欢迎大家一起讨论创作不易小博主求求赞啦