编写一个程序,用链式存储方式构造二叉树,实现二叉树的基本操作(假设树的元素类型为char),并在此基础上设计一个主程序完成如下功能: (1)编写CreatBiTree函数,创建二叉树T; (2)编写PreOrder函数,先序遍历二叉树 (3)编写InOrder函数,中序遍历二叉树; (4)编写PostOrder函数,后序遍历二叉树; (5)编写PostTreeDepth函数,求二叉树的深度
时间: 2024-01-23 12:05:14 浏览: 27
以下是一个用链式存储方式构造二叉树的程序,实现二叉树的基本操作,以及一个主程序完成如下功能:
```c++
#include<iostream>
using namespace std;
struct TreeNode{
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x): val(x), left(NULL), right(NULL){}
};
void CreatBiTree(TreeNode* &T){
char ch;
cin>>ch;
if(ch == '#'){
T = NULL;
}
else{
T = new TreeNode(ch);
CreatBiTree(T->left);
CreatBiTree(T->right);
}
}
void PreOrder(TreeNode* T){
if(T != NULL){
cout<<T->val<<" ";
PreOrder(T->left);
PreOrder(T->right);
}
}
void InOrder(TreeNode* T){
if(T != NULL){
InOrder(T->left);
cout<<T->val<<" ";
InOrder(T->right);
}
}
void PostOrder(TreeNode* T){
if(T != NULL){
PostOrder(T->left);
PostOrder(T->right);
cout<<T->val<<" ";
}
}
int PostTreeDepth(TreeNode* T){
if(T==NULL){
return 0;
}
int left_depth = PostTreeDepth(T->left);
int right_depth = PostTreeDepth(T->right);
return max(left_depth, right_depth)+1;
}
int main(){
TreeNode* T;
CreatBiTree(T);
cout<<"PreOrder: ";
PreOrder(T);
cout<<endl;
cout<<"InOrder: ";
InOrder(T);
cout<<endl;
cout<<"PostOrder: ";
PostOrder(T);
cout<<endl;
cout<<"PostTreeDepth: "<<PostTreeDepth(T)<<endl;
return 0;
}
```
在主程序中,我们先通过CreatBiTree函数来创建一个二叉树T,然后分别调用PreOrder、InOrder和PostOrder函数来实现先序遍历、中序遍历和后序遍历,最后调用PostTreeDepth函数来求二叉树的深度。
相关推荐
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)