方法一:
//用先序,中序,后序的方法递归遍历二叉树
#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef int ElemType;
typedef struct node
{ ElemType data; struct node *lchild,*rchild;}BiNode,*Bitree;//创建一个二叉树 void Inittree(Bitree e){ char x; scanf("%d",&x); if(x==0) e=NULL; else { e=(BiNode *)malloc(sizeof(BiNode)); e->data=x; Inittree(e->lchild); Inittree(e->rchild); }}//用先序遍历二叉树 void preorder(Bitree t){ if(t==NULL) return ; printf("%d\n",t->data); preorder(t->lchild); preorder(t->rchild);}//中序遍历二叉树 void Inorder(Bitree t){ if(t==NULL) return ; Inorder(t->lchild); printf("%d\n",t->data); Inorder(t->rchild);}//后序遍历二叉树 void posorder(Bitree t){ if(t==NULL) return ; posorder(t->lchild); posorder(t->rchild); printf("%d\n",t->data);}//用递归的方法计算二叉树的结点的个数 int countnode(Bitree t){ if(t==NULL) return 0; else { return countnode(t->lchild)+countnode(t->rchild)+1; }}int main()
{ Bitree t; int change=-1; int num; Inittree(t); printf("1:先序遍历\n"); printf("2:中序遍历\n"); printf("3:后序遍历\n"); printf("4:计算树的结点个数\n"); printf("请输出选择:\n"); scanf("%d",&change); switch(change) { case 1: preorder(t); printf("\n\n"); break; case 2: Inorder(t); printf("\n\n"); break; case 3: posorder(t); printf("\n\n"); break; case 4: countnode(t); num=countnode(t); printf("%d\n\n",num); break; default : printf("ERROR!\n"); } return 0;}
方法二:
#include<stdio.h>
#include<stdlib.h>#include<malloc.h>//定义二叉树
typedef struct node{ int data;//数据元素 struct node *left;//指向左子树 struct node *right;//指向右子树}BTree;//构造二叉树:递归方式
int BTreeCreate(BTree **tp){ //构造方法,或者说构造顺序:从左子树开始构造 int x; scanf("%d",&x); if(x<=0) { *tp=NULL;//指针为空,树节点中的某个指针为空 return 0; } *tp=(BTree*)malloc(sizeof(BTree));//将树节点中指针指向该地址空间 if(tp==NULL) return 0; (*tp)->data=x; BTreeCreate(&((*tp)->left)); BTreeCreate(&((*tp)->right)); return 1;}//遍历:前序遍历,递归的方式,先根节点,再左子树后右子树
void PreOrder(BTree *tree){ if(tree==NULL) { return; } printf("%d ",tree->data); PreOrder(tree->left); PreOrder(tree->right);}//遍历:中序遍历,递归方式,先左子树再根节点最后右子树
void MidOrder(BTree *tree){ if(tree==NULL) { return; } MidOrder(tree->left); printf("%d ",tree->data); MidOrder(tree->right);}//遍历:后序遍历,递归方式,先左子树再右子树最后根节点
void PostOrder(BTree *tree)
{ if(tree==NULL) { return; } PostOrder(tree->left); PostOrder(tree->right); printf("%d ",tree->data);}int countnode(BTree *tree)
{ if(tree==NULL) return 0; else return countnode(tree->left)+countnode(tree->right)+1;}int main()
{ //二叉树构建 BTree *tree; printf("Create binary tree:\n"); BTreeCreate(&tree); //前序遍历 printf("Pre order:\n"); PreOrder(tree); printf("\n"); //中序遍历 printf("Mid order:\n"); MidOrder(tree); printf("\n"); //后序遍历 printf("Post order:\n"); PostOrder(tree); printf("\n"); //计算二叉树节点数目 printf("输出点的数目:\n"); int num=countnode(tree); printf("%d\n",num); return 0;}