二叉树的链式存储结构定义如下:
typedef char DataType; //二叉树节点数据类型 //二叉树节点的数据结构如下 typedef struct node { DataType data; struct node *lchild; //定义节点左孩子指针 struct node *rchild; //定义节点右孩子指针 }BinTNode;
采用递归算法创建二叉树如下:
#include <stdio.h> #include <malloc.h> #include <stdlib.h> typedef char DataType; //二叉树节点数据类型 //二叉树节点的数据结构如下 typedef struct node { DataType data; struct node *lchild; //定义节点左孩子指针 struct node *rchild; //定义节点右孩子指针 }BinTNode; BinTNode *CreateBinTree() //输入先序遍历序列,创建二叉树链表 { BinTNode *t; char ch; ch=getchar(); //getchar函数是从输入缓冲区里读出最开头的那个字符的,然后把最先的那个字符删掉 if(ch=='*') t=NULL; else { t=(BinTNode*)malloc(sizeof(BinTNode)); //申请根节点存储空间 t->data=ch; t->lchild=CreateBinTree(); //创建左子树 t->rchild=CreateBinTree(); //创建右子树 } return t; } void ListBinTree(BinTNode *t) //用广义表表示二叉树 { if(t!=NULL) { printf("%c",t->data); if(t->lchild!=NULL || t->rchild!=NULL) { printf("("); ListBinTree(t->lchild); if(t->rchild!=NULL) printf(","); ListBinTree(t->rchild); printf(")"); } } } main() { BinTNode *t=NULL; printf("请输入先序序列,虚节点用*表示: "); t=CreateBinTree(); printf("广义表表示的二叉树的输出为: "); ListBinTree(t); printf(" "); system("pause"); }
举例: