左右孩子表示法来存储二叉树的程序C++
时间: 2024-02-04 13:10:06 浏览: 21
以下是使用左右孩子表示法来存储二叉树的C++程序:
```c++
#include<iostream>
#include<queue>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
void createTree(TreeNode* &root){ //创建二叉树
int val;
cin>>val;
if(val==-1){
root=NULL;
return;
}
root=new TreeNode(val);
createTree(root->left);
createTree(root->right);
}
void preOrder(TreeNode* root){ //先序遍历
if(root==NULL) return;
cout<<root->val<<" ";
preOrder(root->left);
preOrder(root->right);
}
void inOrder(TreeNode* root){ //中序遍历
if(root==NULL) return;
inOrder(root->left);
cout<<root->val<<" ";
inOrder(root->right);
}
void postOrder(TreeNode* root){ //后序遍历
if(root==NULL) return;
postOrder(root->left);
postOrder(root->right);
cout<<root->val<<" ";
}
void levelOrder(TreeNode* root){ //层次遍历
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* node=q.front();
q.pop();
if(node!=NULL){
cout<<node->val<<" ";
q.push(node->left);
q.push(node->right);
}
}
}
int main(){
TreeNode* root;
createTree(root);
cout<<"先序遍历:";
preOrder(root);
cout<<endl;
cout<<"中序遍历:";
inOrder(root);
cout<<endl;
cout<<"后序遍历:";
postOrder(root);
cout<<endl;
cout<<"层次遍历:";
levelOrder(root);
cout<<endl;
return 0;
}
```
在上述程序中,使用了一个结构体`TreeNode`来表示二叉树的节点,包含了节点的值以及左右孩子指针。`createTree`函数用于创建二叉树,输入-1表示该节点为空。`preOrder`、`inOrder`、`postOrder`和`levelOrder`函数分别实现了先序、中序、后序和层次遍历。其中,层次遍历使用了队列来实现。