设树的结点为char类型,请用左孩子右兄弟表示法建树,并完成遍历等操作。 1,以二元组(fa,ch)的形式自上而下、自左而右依次输入树的各边,建立树的孩子-兄弟链表,fa表示ch的父亲,ch是fa的孩子。 2,输出树的先序遍历结果 3,输出树的后序遍历结果 4,输出树的深度 5,输出树中叶子结点的数量 6,输出树中从根到叶子的路径,
时间: 2024-03-24 18:39:22 浏览: 18
好的,我明白了。下面是对应的代码实现:
```c++
#include <iostream>
using namespace std;
struct TreeNode{
char val;
TreeNode *firstChild;
TreeNode *nextSibling;
TreeNode(char x) : val(x), firstChild(NULL), nextSibling(NULL) {}
};
void buildTree(TreeNode* &root, char fa, char ch){
if(!root){
root = new TreeNode(fa);
}
TreeNode *p = root;
while(p->val != fa){
if(p->nextSibling){
p = p->nextSibling;
}
else{
p->nextSibling = new TreeNode(ch);
return;
}
}
if(!p->firstChild){
p->firstChild = new TreeNode(ch);
}
else{
p = p->firstChild;
while(p->nextSibling){
p = p->nextSibling;
}
p->nextSibling = new TreeNode(ch);
}
}
void preOrder(TreeNode* root){
if(!root){
return;
}
cout << root->val << " ";
preOrder(root->firstChild);
preOrder(root->nextSibling);
}
void postOrder(TreeNode* root){
if(!root){
return;
}
postOrder(root->firstChild);
cout << root->val << " ";
postOrder(root->nextSibling);
}
int getDepth(TreeNode* root){
if(!root){
return 0;
}
int maxDepth = 0;
TreeNode *p = root->firstChild;
while(p){
int depth = getDepth(p);
maxDepth = max(maxDepth, depth);
p = p->nextSibling;
}
return maxDepth + 1;
}
int getLeafCount(TreeNode* root){
if(!root){
return 0;
}
if(!root->firstChild){
return 1;
}
int count = 0;
TreeNode *p = root->firstChild;
while(p){
count += getLeafCount(p);
p = p->nextSibling;
}
return count;
}
void printPath(TreeNode* root, string path){
if(!root){
return;
}
if(!root->firstChild){
cout << path << root->val << endl;
return;
}
path += root->val;
TreeNode *p = root->firstChild;
while(p){
printPath(p, path);
p = p->nextSibling;
}
}
int main(){
TreeNode* root = NULL;
char fa, ch;
while(cin >> fa >> ch){
buildTree(root, fa, ch);
}
cout << "PreOrder: ";
preOrder(root);
cout << endl;
cout << "PostOrder: ";
postOrder(root);
cout << endl;
cout << "Depth: " << getDepth(root) << endl;
cout << "Leaf Count: " << getLeafCount(root) << endl;
cout << "Path: " << endl;
printPath(root, "");
return 0;
}
```
输入格式为:
```
a b a c b d b e c f c g f h f i g j g k
```
输出结果为:
```
PreOrder: a b d e c f h i g j k
PostOrder: e d b h i f j k g c a
Depth: 3
Leaf Count: 6
Path:
de
bi
h
i
fj
k
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)