一、前，中，后序——三种遍历方式
1:前，中，后序遍历
访问方向图示：（后续解题思路）
2.原理图示：(递归）
ps：以中序遍历为例
3.代码实现
//Preorder，Inorder，postorder，代码区别在于打印位置 void Order(BTNode* root) { if (root == NULL) { printf("NULL "); return; } printf("%d ", root->data);//Preorder前序 Order(root->left); printf("%d ", root->data);//Inorder中序 Order(root->right); printf("%d ", root->data);//postorder后序 }
二、层序遍历（利用队列）
1.层序遍历原理图示：
2.代码实现
节点 typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode;
void LevelOrder(BTNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root);//入队列 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q);//保存队列头指针 QueuePop(&q);//出队列 printf("%d ", front->data); if(front->left) QueuePush(&q, front->left); if (front->right) QueuePush(&q, front->right); } QueueDestroy(&q); }
3.实际应用：【判断一颗二叉树是否为完全二叉树】
原理解析：利用层序遍历，将二叉树遍历完。此时栈中只剩下NULL。只要清空栈的过程中发现非空元素则能够判断其不是完全二叉树，反之成立。
代码实现：
三、递归思想在二叉树中的实际应用
1.求二叉树的结点个数：这里不对TreeSize返回值做保存的原因是，返回值不用于判断
int TreeSize(BTNode* root) { return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1; }
2.求二叉树的高度：注意要保存递归回来的返回值再做判断，避免进行下一步递归时返回找上一步递归的值，造成低效。
int TreeHeight(BTNode* root) { if (root == NULL) return 0; int leftHeight = TreeHeight(root->left);//保存递归的值 int rightHeight = TreeHeight(root->right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; }
3.求二叉树第k层的节点数：第1层的第k个节点等于第2层的k-1个节点，以此类推。这里不对TreeSize返回值做保存的原因是，返回值不用于判断
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); }
4.二叉树的销毁
void TreeDestory() { if(root==NULL) { return; } TreeDestory(root->left); TreeDestory(root->right); free(root); }
三、深度DPS/广度BFS优先遍历
1.深度优先遍历
2.广度优先遍历
