用C++编写程序给出注释,以二叉链表建立二叉树链式存储结构,实现前序遍历、求叶子结点的个数计算、中序遍历、后序遍历、求深度。
时间: 2024-01-29 17:04:40 浏览: 89
以下是C++代码实现二叉树的建立和各种遍历方式及深度计算,注释已在代码中标注:
```c++
#include<iostream>
using namespace std;
//定义二叉树结点
struct TreeNode{
char val;
TreeNode* left;
TreeNode* right;
//构造函数
TreeNode(char x): val(x), left(nullptr), right(nullptr){}
};
//建立二叉树
void buildTree(TreeNode* &root){
char ch;
cin>>ch;
if(ch=='#') return; //若输入为'#',则该结点为空结点
root=new TreeNode(ch); //新建结点
buildTree(root->left); //递归建立左子树
buildTree(root->right); //递归建立右子树
}
//前序遍历
void preOrder(TreeNode* root){
if(root==nullptr) return; //遍历到空结点,返回上一级
cout<<root->val<<" "; //先输出该结点的值
preOrder(root->left); //递归遍历左子树
preOrder(root->right); //递归遍历右子树
}
//中序遍历
void inOrder(TreeNode* root){
if(root==nullptr) return; //遍历到空结点,返回上一级
inOrder(root->left); //递归遍历左子树
cout<<root->val<<" "; //输出该结点的值
inOrder(root->right); //递归遍历右子树
}
//后序遍历
void postOrder(TreeNode* root){
if(root==nullptr) return; //遍历到空结点,返回上一级
postOrder(root->left); //递归遍历左子树
postOrder(root->right); //递归遍历右子树
cout<<root->val<<" "; //输出该结点的值
}
//计算叶子结点个数
int leafCount(TreeNode* root){
if(root==nullptr) return 0; //空结点返回0
if(root->left==nullptr && root->right==nullptr) return 1; //左右子树都为空,为叶子结点,返回1
return leafCount(root->left)+leafCount(root->right); //递归计算左右子树叶子结点个数之和
}
//求深度
int treeDepth(TreeNode* root){
if(root==nullptr) return 0; //空结点返回0
int leftDepth=treeDepth(root->left); //递归计算左子树深度
int rightDepth=treeDepth(root->right); //递归计算右子树深度
return max(leftDepth,rightDepth)+1; //返回左右子树深度较大值加1
}
int main(){
TreeNode* root=nullptr;
buildTree(root); //建立二叉树
cout<<"前序遍历结果:";
preOrder(root); //前序遍历
cout<<endl<<"中序遍历结果:";
inOrder(root); //中序遍历
cout<<endl<<"后序遍历结果:";
postOrder(root); //后序遍历
cout<<endl<<"叶子结点数为:"<<leafCount(root)<<endl; //计算叶子结点个数
cout<<"树的深度为:"<<treeDepth(root)<<endl; //计算树的深度
return 0;
}
```
希望能对你有所帮助!
阅读全文