int preorder(bnode *bt)//递归先序遍历 {if(bt==NULL) return; else { printf("%d",bt->data); if(bt->lc!=NULL) preorder(bt->lc); if(bt->rc!=NULL); preorder(bt->rc); } }

这是一段二叉树的递归先序遍历代码，其中bnode是二叉树结点的结构体定义，包含数据data和左右子树指针lc, rc。该函数的作用是先输出当前结点的数据，再递归遍历左子树和右子树。

具体来说，函数首先判断当前结点是否为空，如果为空就返回。否则，先输出当前结点的数据，然后递归遍历左子树和右子树。递归遍历左子树时，先判断左子树指针是否为空，如果不为空则继续递归遍历左子树；递归遍历右子树时也是类似的。

这段代码的时间复杂度是O(n)，其中n是二叉树的结点个数。因为遍历每个结点的时间都是常数级别的，而遍历所有结点需要的时间是线性的。

相关问题

#include<stdio.h> #include<stdlib.h> typedef struct btreenode { int data; struct bnode *lc; struct bnode *rc; }bnode; int creat(bnode **proot) { bnode *p,*q; int k,n,i; *proot=NULL;//初始化空树 printf("输入二叉树的节点元素个数n：");//输入数据元素个数 scanf("%d",&n); printf("输入二叉树："); for(i=0;i<n;i++) { p=(bnode *)malloc(sizeof(bnode)); /*if(p == NULL) {//检查分配内存是否成功 printf("树满\n"); exit(1);}*/ p->lc=NULL; p->rc=NULL; scanf("%d",&k); p->data=k; if(*proot=NULL) *proot=p; else {q=*proot; while(q!=NULL) {if(q->data>k) if(q->lc!=NULL) q=q->lc; else {q->lc=p; q=NULL; } else if(q->rc!=NULL) q=q->rc; else {q->rc=p; q=NULL; } } } } } void preorder(bnode *bt)//递归先序遍历 { if(bt==NULL) {return ; } printf("ggggg"); preorder(bt->lc); preorder(bt->rc); } void inorder(bnode *bt) { if(bt==NULL) { return;} else { if(bt->lc!=NULL) inorder(bt->lc); printf("%d",bt->data); if(bt->rc!=NULL) inorder(bt->rc); } printf("%d",bt->data); } int main() { bnode *bt; bt=NULL; creat(&bt); printf("先序遍历结果："); preorder(bt); printf("\n"); printf("中序遍历结果："); inorder(bt); printf("\n"); return 0; }

这段代码是一个二叉树的创建和遍历程序，包括先序遍历和中序遍历。

在程序中，结构体 `btreenode` 表示二叉树节点，包括节点值 `data` 和左右子节点指针 `lc` 和 `rc`。

函数 `creat` 的作用是创建二叉树，参数 `proot` 是一个二级指针，表示二叉树根节点的地址。函数首先将根节点指针设置为 `NULL`，然后输入二叉树节点元素个数 `n` 和节点元素值，依次将节点插入二叉树中。

函数 `preorder` 和 `inorder` 分别是二叉树的先序遍历和中序遍历函数。其中 `preorder` 是递归函数，先输出当前节点值，然后递归遍历左右子树；`inorder` 同样是递归函数，但先遍历左子树，再输出当前节点值，最后遍历右子树。

在 `main` 函数中，首先定义一个二叉树指针 `bt`，然后调用 `creat` 函数创建二叉树，最后分别调用 `preorder` 和 `inorder` 函数进行先序遍历和中序遍历。

完善代码：#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函数中需要先后序遍历左子树，然后后序遍历右子树，最后访问根结点。完整代码如下：