二叉树的建立、各种遍历操作以及树形输出
时间: 2023-05-18 14:03:11 浏览: 79
二叉树的建立可以通过递归或非递归的方式实现,其中递归方式比较简单,可以通过以下代码实现:
```
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || postorder.empty()) {
return NULL;
}
int rootVal = postorder.back();
TreeNode* root = new TreeNode(rootVal);
int rootIndex = find(inorder.begin(), inorder.end(), rootVal) - inorder.begin();
vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);
vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());
vector<int> leftPostorder(postorder.begin(), postorder.begin() + rootIndex);
vector<int> rightPostorder(postorder.begin() + rootIndex, postorder.end() - 1);
root->left = buildTree(leftInorder, leftPostorder);
root->right = buildTree(rightInorder, rightPostorder);
return root;
}
```
各种遍历操作包括前序遍历、中序遍历、后序遍历和层序遍历,可以通过递归或非递归的方式实现,以下是递归方式的代码:
```
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
cout << root->val << " ";
inorderTraversal(root->right);
}
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left != NULL) {
q.push(node->left);
}
if (node->right != NULL) {
q.push(node->right);
}
}
cout << endl;
}
}
```
树形输出可以通过递归方式实现,以下是代码:
```
void printTree(TreeNode* root, int depth) {
if (root == NULL) {
return;
}
printTree(root->right, depth + 1);
for (int i = 0; i < depth; i++) {
cout << " ";
}
cout << root->val << endl;
printTree(root->left, depth + 1);
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)