用递归的方法实现以下算法: 1.以二叉链表表示二叉树,建立一棵二叉树(算法5.3); 2.输出二叉树的中序遍历结果(算法5.1); 3.输出二叉树的前序遍历结果; 4.输出二叉树的后序遍历结果; 5.计算二叉树的深度
时间: 2023-06-03 14:05:18 浏览: 283
好的,我能回答你的第一个问题。以下是用递归的方法实现二叉树的建立和遍历的算法过程:
1. 建立二叉树的方法:
```
// 定义二叉树节点
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
// 创建二叉树函数
void CreateBiTree(BiTree *T) {
char ch;
scanf("%c", &ch);
if (ch == '#') // 如果输入的是 #,表示当前节点为空
*T = NULL;
else {
// 创建根节点
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->data = ch;
// 递归创建左子树
CreateBiTree(&(*T)->lchild);
// 递归创建右子树
CreateBiTree(&(*T)->rchild);
}
}
```
2. 中序遍历二叉树的方法:
```
// 中序遍历函数
void InOrderTraverse(BiTree T) {
if (T) {
InOrderTraverse(T->lchild);
printf("%c ", T->data);
InOrderTraverse(T->rchild);
}
}
```
3. 前序遍历二叉树的方法:
```
// 前序遍历函数
void PreOrderTraverse(BiTree T) {
if (T) {
printf("%c ", T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
```
4. 后序遍历二叉树的方法:
```
// 后序遍历函数
void PostOrderTraverse(BiTree T) {
if (T) {
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ", T->data);
}
}
```
5. 计算二叉树深度的方法:
```
// 计算二叉树深度函数
int TreeDepth(BiTree T) {
if (T == NULL)
return 0;
else {
int leftDepth = TreeDepth(T->lchild); // 求左子树深度
int rightDepth = TreeDepth(T->rchild); // 求右子树深度
return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}
}
```
以上就是用递归的方法实现二叉树的建立和遍历的算法过程。