二叉树的一些基本操作，包括创建以及采用递归进行二叉树的先序、中序、后序及层次遍历
//BinaryTree.h #ifndef _BINARY_TREE_H #define _BINARY_TREE_H typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; }TreeNode; TreeNode* CreatBinaryTree(int* arr, int len,int idx); void PreOrder(TreeNode* root); void MidOrder(TreeNode* root); void PostOrder(TreeNode* root); void LevelOrder(TreeNode* root, int level); int MaxDepth(TreeNode *root); #endif //BinaryTree.cpp #include<iostream> #include<algorithm> #include<math.h> #include"BinaryTree.h" using namespace std; TreeNode* CreatBinaryTree(int* arr, int len,int idx) //生成二叉树，'-1'表示此处为NULL { TreeNode *pNode = NULL; if (idx < len && arr[idx] != -1) { pNode = new TreeNode; pNode->val = arr[idx]; pNode->left = CreatBinaryTree(arr, len, 2 * idx + 1); pNode->right = CreatBinaryTree(arr, len, 2 * idx + 2); } return pNode; } void PreOrder(TreeNode* root) //先序遍历二叉树 { if (root == NULL) { return; } TreeNode *p = root; cout << p->val; PreOrder(p->left); PreOrder(p->right); } void MidOrder(TreeNode* root) //中序遍历二叉树 { if (root == NULL) { return; } TreeNode *p = root; MidOrder(p->left); cout << p->val; MidOrder(p->right); } void PostOrder(TreeNode* root) //后序遍历二叉树 { if (root == NULL) { return; } TreeNode* p = root; PostOrder(p->left); PostOrder(p->right); cout << p->val; } void LevelOrder(TreeNode* root, int level) //层次遍历二叉树，输出第level层的值，若需输出每一层的，可以与函数MaxDepth结合使用 { if (root == NULL || level < 1) { return; } if (level == 1) { cout << root->val; } LevelOrder(root->left, level - 1); LevelOrder(root->right, level - 1); } int MaxDepth(TreeNode *root) //求取二叉树的深度 { if (root == NULL) { return 0; } return max(MaxDepth(root->left), MaxDepth(root->right)) + 1; } //test.cpp #include<iostream> #include"BinaryTree.h" using namespace std; int main() { int arr[] = {1,2,3,4,-1,6,7,8}; int len = sizeof(arr) / sizeof(arr[0]); TreeNode* T= CreatBinaryTree(arr,len,0); int depth = MaxDepth(T); for (int i = 1; i <= depth; i++) { LevelOrder(T, i); } return 0; }
