最基础的二叉树:
#include <stdio.h> #include <stdlib.h> typedef int elemtype; //整形为树的数据类型 typedef struct node { elemtype data; struct node *lchild,*rchild; }btree,*ptree; void (*visit)(elemtype e); //树的创建 ptree CreatTree() { ptree root; elemtype data; scanf("%d",&data); if(data == 0)root = NULL; //0 代表空子树 else { root = (ptree)malloc(sizeof(btree)); if(!root)exit(1); root->data = data; root->lchild = CreatTree(); root->rchild = CreatTree(); } return root; } void PrintResult(elemtype e) { printf("%d ",e); } //前序遍历二叉树 void PreOrderTree(ptree root,void (*visit)(elemtype )) { if(root) { (visit)(root->data); PreOrderTree(root->lchild,visit); PreOrderTree(root->rchild,visit); } } //中序遍历二叉树 void InOrderTree(ptree root,void (*visit)(elemtype )) { if(root) { PreOrderTree(root->lchild,visit); (visit)(root->data); PreOrderTree(root->rchild,visit); } } //后序遍历二叉树 void PostOrderTree(ptree root,void (*visit)(elemtype )) { if(root) { PreOrderTree(root->lchild,visit); PreOrderTree(root->rchild,visit); (visit)(root->data); } } int main() { ptree root = NULL; root = CreatTree(); PreOrderTree(root,PrintResult); printf("\n"); InOrderTree(root,PrintResult); printf("\n"); PostOrderTree(root,PrintResult); printf("\n"); return 0; }
不过二叉树的建立方式各异,下面是第二种二叉树的建立方式
#include<stdio.h> #include<stdlib.h> #include<string.h> #define maxitem 1024 #define ok 1 typedef char elemtype; typedef struct BiTNode { elemtype data; struct BiTNode *lchild,*rchild; }bitnode,*bitree; //初始化树根节点 int init(bitree *t) { *t = NULL; return ok; } //前序创建二叉树 int creat(bitree *t) { char ch; scanf("%c",&ch); if (ch == '#') *t = NULL; else { *t = (bitree)malloc(sizeof(bitnode)); if (!*t) exit(1); (*t)->data = ch; creat(&(*t)->lchild);creat(&(*t)->rchild); } return 1; } //前序遍历二叉树 void InOrderTraverse(bitree T) { if(T) { InOrderTraverse(T->lchild); InOrderTraverse(T->rchild); printf("%c",T->data); } } int main() { bitree t; init(&t); creat(&t); InOrderTraverse(t); printf("\n"); return 0; }