先序打印二叉树/ void InOrderPrint(BiTree T) { if (T == NULL) { return; } else { printf("%c ", T->data); InOrderPrint(T->lchild); InOrderPrint(T->rchild);
时间: 2024-04-22 16:22:05 浏览: 12
这段代码是先序遍历打印二叉树的代码,它的功能是从二叉树的根节点开始,先打印根节点,再递归打印左子树,最后递归打印右子树。这里的 BiTree 是指二叉树的结构体类型,T 表示二叉树的根节点。在每次递归时,如果当前节点为空,则返回;否则打印当前节点的值,然后递归打印它的左子树和右子树。这个算法的时间复杂度是 O(n),其中 n 是二叉树的节点数。
相关问题
完善代码:#include <stdio.h> #include <malloc.h> #include <conio.h> typedef int ElemType; typedef struct BiTreeNode { ElemType data; struct BiTreeNode *lchild, *rchild; } BiTreeNode,*BiTree; void Visit(BiTree bt) { printf("%d ",bt->data); } int max(int x,int y) { if (x>y) return x; else return y; } //二叉树的先序遍历算法 void PreOrder(BiTree bt) /* bt为指向根结点的指针*/ { if (bt) /*如果bt为空,结束*/ { Visit (bt ); /*访问根结点*/ PreOrder (bt -> lchild); /*先序遍历左子树*/ PreOrder (bt -> rchild); /*先序遍历右子树*/ } } //二叉树的中序遍历递归算法 void InOrder(BiTree bt)/* bt为指向二叉树根结点的指针*/ { } //二叉树的后序遍历递归算法 void PostOrder(BiTree bt) /* bt为指向二叉树根结点的指针*/ { } //结合“扩展先序遍历序列”创建二叉树,递归 BiTree CreateBiTree(ElemType s[]) { BiTree bt; static int i=0; ElemType c = s[i++]; if( c== -1) bt = NULL; /* 创建空树 */ else { bt = (BiTree)malloc(sizeof(BiTreeNode)); bt->data = c; /* 创建根结点 */ bt->lchild = CreateBiTree(s); /* 创建左子树 */ bt->rchild = CreateBiTree(s); /* 创建右子树 */ } return bt; } //根据先序序列、中序序列建立二叉树,递归 BiTree PreInOrder(ElemType preord[],ElemType inord[],int i,int j,int k,int h) { BiTree t; //添加代码 return t; } BiTree CreateBiTree_PreIn(ElemType preord[],ElemType inord[],int n) { BiTree root; if (n<=0) root=NULL; else root=PreInOrder(preord,inord,0,n-1,0,n-1); return root; } //统计叶结点个数 int BitreeLeaf ( BiTree bt ) { if ( bt == NULL ) return 0 ; /* 空树,叶子数为0 */ if ( bt->lchild ==NULL&& bt->rchild == NULL) return 1 ; /*只有一个根结点,叶子数为1*/ return ( BitreeLeaf( bt -> lchild ) + BitreeLeaf ( bt -> rchild )) ; } //统计二叉树的深度 int BitreeDepth ( BiTree bt ) { int d = 0,depthL, depthR; /*depthL和depthR分别为左、右子树的深度*/ if ( bt == NULL ) return 0 ; /*空树,深度为0 */ if ( bt -> lchild ==NULL && bt -> rchild == NULL) return 1; /*叶子结点,深度为1 */ depthL = BitreeDepth ( bt -> lchild ) ; /*左子树深度 */ depthR = BitreeDepth ( bt -> rchild ) ; /*右子树深度 */ d = max (dept
hL, depthR) + 1; /*当前结点深度*/ return d ; } int main() { ElemType s1[] = {1,2,-1,-1,3,-1,-1}; BiTree bt1; bt1 = CreateBiTree(s1); printf("二叉树的先序遍历:"); PreOrder(bt1); printf("\n"); printf("二叉树的中序遍历:"); InOrder(bt1); printf("\n"); printf("二叉树的后序遍历:"); PostOrder(bt1); printf("\n"); ElemType pre[] = {1,2,3}; ElemType in[] = {2,1,3}; BiTree bt2; bt2 = CreateBiTree_PreIn(pre,in,3); printf("根据先序序列、中序序列建立的二叉树的先序遍历:"); PreOrder(bt2); printf("\n"); printf("根据先序序列、中序序列建立的二叉树的中序遍历:"); InOrder(bt2); printf("\n"); printf("根据先序序列、中序序列建立的二叉树的后序遍历:"); PostOrder(bt2); printf("\n"); printf("二叉树的叶子结点个数:%d\n",BitreeLeaf(bt2)); printf("二叉树的深度:%d\n",BitreeDepth(bt2)); return 0; }
注释已经比较详细了,只需要实现InOrder和PostOrder函数即可。InOrder函数中需要先中序遍历左子树,然后访问根结点,最后中序遍历右子树。PostOrder函数中需要先后序遍历左子树,然后后序遍历右子树,最后访问根结点。完整代码如下:
#include<stdio.h> #include<stdlib.h> define char TElemType typedef struct BiTNode{ TElemType data; struct BiTNode *lchild; struct BiTNode *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); } } void printTree(TreeNode* root) { if (root == NULL) { printf("# "); return; } printf("%c ", root->val); printTree(root->left); printTree(root->right); } int main() { BiTree T = NULL; printf("请输入先序遍历序列:\n"); CreateBiTree(&T); return 0; }这个C语言代码怎么改
这段代码存在一些问题:
1. `define char TElemType` 应该改为 `typedef char TElemType`,使得`TElemType` 成为一个类型别名,代表了二叉树节点的数据类型。
2. 函数 `printTree(TreeNode* root)` 没有声明,应该修改为 `void printTree(BiTree root)`。
修改后的代码如下:
```
#include<stdio.h>
#include<stdlib.h>
typedef char TElemType; // 定义二叉树节点的数据类型
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild;
struct BiTNode *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);
}
}
void printTree(BiTree root) {
if (root == NULL) {
printf("# ");
return;
}
printf("%c ", root->data);
printTree(root->lchild);
printTree(root->rchild);
}
int main() {
BiTree T = NULL;
printf("请输入先序遍历序列:\n");
CreateBiTree(&T);
printTree(T);
return 0;
}
```
这样就可以正确地根据输入的先序遍历序列建立一棵以二叉链表表示的二叉树,并输出这棵树的先序遍历序列了。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![text/x-c](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)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)