189 8069 5689
先定义二叉树的存储结构，不同的定义方法相应有不同的存储结构的建立算法。
创新新互联，凭借十余年的网站设计制作、网站设计经验，本着真心·诚心服务的企业理念服务于成都中小企业设计网站有1000+案例。做网站建设，选创新互联。
如二叉树采用二叉链表存储结构，如下：
#define OK 1
#define OVERFLOW -1
typedef int TElemType;
typedef int Status;
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild ; //左孩子指针
struct BiTNode *rchild; // 右孩子指针
} BiTNode;//二叉树结点
typedef BiTNode *BiTree; //二叉树
int ch;
按给定的带 0 标记的先序序列定义一棵二叉树，如下：
Status CreateBiTree(BiTree T)
{//按先序序列建儿叉树
scanf("%d",ch);
if (ch= =0 ) T = NULL;
else {
if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T-data = ch; // 生成根结点
CreateBiTree(T-lchild); // 构造左子树
CreateBiTree(T-rchild); // 构造右子树
}
return OK;
} // CreateBiTree
例如，输入先序序列如下：1 2 0 3 0 0 4 0 0
建立的二叉树如下：
1
/ \
2 4
\
3
如果文字表达的话就是下面的，若看不懂，可以在百度的图片搜索里输入二叉树找张图对照着比划下，应该能看懂。概念并不是很难。
说简单点就是一个点分两个叉，这两个叉又分别分两个叉（搜张图就明白这句了）。~~~~~
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
一、树的概述
树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。
（一）树的定义
树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(ROOT)的结点；
⒉剩下的结点被分成n=0个互不相交的集合T1、T2、......Tn，而且， 这些集合的每一个又都是树。树T1、T2、......Tn被称作根的子树(Subtree)。
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
5. 2 二叉树
1.二叉树的基本形态：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——(a)；
(2)只有一个根结点的二叉树——(b)；
(3)右子树为空的二叉树——(c)；
(4)左子树为空的二叉树——(d)；
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
2.两个重要的概念：
(1)完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
(2)满二叉树——除了叶结点外每一个结点都有左右子女且叶结点都处在最底层的二叉树,。
5.普通树转换成二叉树：凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。
二叉树很象一株倒悬着的树，从树根到大分枝、小分枝、直到叶子把数据联系起来，这种数据结构就叫做树结构，简称树。树中每个分叉点称为结点，起始结点称为树根，任意两个结点间的连接关系称为树枝，结点下面不再有分枝称为树叶。结点的前趋结点称为该结点的"双亲"，结点的后趋结点称为该结点的"子女"或"孩子"，同一结点的"子女"之间互称"兄弟"。
二叉树：二叉树是一种十分重要的树型结构。它的特点是，树中的每个结点最多只有两棵子树，即树中任何结点的度数不得大于2。二叉树的子树有左右之分，而且，子树的左右次序是重要的，即使在只有一棵子树的情况下，也应分清是左子树还是右子树。定义：二叉树是结点的有限集合，这个集合或是空的，或是由一个根结点和两棵互不相交的称之为左子树和右子树的二叉树组成。
（三）完全二叉树
对满二叉树，从第一层的结点(即根)开始，由下而上，由左及右，按顺序结点编号，便得到满二叉树的一个顺序表示。据此编号，完全二叉树定义如下：一棵具有n个结点，深度为K的二叉树，当且仅当所有结点对应于深度为K的满二叉树中编号由1至n的那些结点时，该二叉树便是完全二叉树。图4是一棵完全二叉树。
说明：输入时按前序遍历方式依次输入各节点值，默认的结束符为0。即当一个节点为叶子节点时，把它的左子节点和右子节点都输为0，当然你可以自己修改为加别的值。例如某棵树的形状如下：
A
/ \
B C
/ \ \
D E F
则按如下输入：ABD00E00C0F00。
程序运行后结果如下：
前序遍历结果：
ABDECF
中序遍历结果：
DBEACF
程序源文件：
#include stdio.h
#include stdlib.h
struct treeNode
{
char data;
struct treeNode *lchild;
struct treeNode *rchild;
}; //定义一个节点
class binaryTree
{
private:
struct treeNode *T;
public:
binaryTree() {T = NULL;}; //构造函数
int createTree(); //创建树
int preTravel(); //先序遍历树
int inTravel(); //中序遍历树
};
struct treeNode * createBT(struct treeNode *bt, int k)
{
char b;
struct treeNode *p, *t;
b = getchar();
if (b != '0')
{
p = (struct treeNode *)malloc(sizeof(struct treeNode));
p-data = b;
p-lchild = NULL;
p-rchild = NULL;
if (k == 0) t = p;
if (k == 1) bt-lchild = p;
if (k == 2) bt-rchild = p;
createBT(p, 1);
createBT(p, 2);
}
return t;
}
void preTravelBT(struct treeNode *bt)
{
if (bt != NULL)
{
putchar(bt-data);
preTravelBT(bt-lchild);
preTravelBT(bt-rchild);
}
}
void inTravelBT(struct treeNode *bt)
{
if (bt != NULL)
{
inTravelBT(bt-lchild);
putchar(bt-data);
inTravelBT(bt-rchild);
}
}
int binaryTree::createTree()
{
printf("请输入各节点数据：\n");
T = createBT(T, 0);
return 0;
}
int binaryTree::preTravel()
{
printf("前序遍历结果：\n");
preTravelBT(T);
printf("\n");
return 0;
}
int binaryTree::inTravel()
{
printf("中序遍历结果：\n");
inTravelBT(T);
printf("\n");
return 0;
}
void main()
{
binaryTree MyTree;
MyTree.createTree();
MyTree.preTravel();
MyTree.inTravel();
}
#includeiostream.h
#includestdlib.h
typedef struct BiTNode
{ //定义树的结构
char date;
struct BiTNode *lchild ,*rchild;
}BiTNode,*BiTree;
void sumlr(BiTree T,int left,int right)//统计左右孩子数目
{
if(T==NULL)
return;
else
{
if(T-lchild!=NULL)
{
left++;
sumlr(T-lchild,left,right);
}
if(T-rchild!=NULL)
{
right++;
sumlr(T-rchild,left,right);
}
}
}
void sumnode(BiTree T,int count)//统计结点数目
{
if(T==NULL)
return;
else
{
count++;
sumnode(T-lchild,count);
sumnode(T-rchild,count);
}
}
void parent_search(BiTree T, char ch2)//查找父亲节点
{
if(!T)
return;
else
{
if(!T-lchild!T-rchild)
{
//cout"输入数据错误"endl;
return;
}
if(!(!T-lchild!T-rchild))
{
if(T-lchild!T-rchild)
{
if(T-lchild-date==ch2)
cout" 父亲节点为"T-dateendl;
else
{
parent_search(T-lchild, ch2);
parent_search(T-rchild, ch2);
}
}
if(!T-lchildT-rchild)
{
if(T-rchild-date==ch2)
cout" 父亲节点为"T-dateendl;
else
{
parent_search(T-lchild, ch2);
parent_search(T-rchild, ch2);
}
}
if(T-lchildT-rchild)
{
if(T-lchild-date==ch2)
cout" 父亲节点为"T-dateendl;
else
{
parent_search(T-lchild, ch2);
parent_search(T-rchild, ch2);
}
if(T-rchild-date==ch2)
cout" 父亲节点为"T-dateendl;
else
{
parent_search(T-lchild, ch2);
parent_search(T-rchild, ch2);
}
}
}
}
}
BiTree children_search(BiTree T,char findnode)
{ //找子节点
BiTree T1,T2;
if(T!=NULL)
{
if(T-date==findnode)
return T;
else
T1=children_search(T-lchild,findnode);
T2=children_search(T-rchild,findnode);
if(T1!=NULL)
return T1;
else
if(T2!=NULL)
return T2;
else
return NULL;
}
else
return NULL;
}
void delData(BiTree T, char ch)//删除节点
{
if(!T)
return;
if((T-lchild==NULL)(T-rchild==NULL))
return;
if((T-lchild==NULL)(T-rchild!=NULL))
{
if(T-rchild-date == ch)
{
T-rchild=NULL;
}
delData(T-rchild, ch);
}
if((T-rchild==NULL)(T-lchild!=NULL))
{
if(T-lchild-date == ch)
{
T-lchild=NULL;
}
delData(T-lchild, ch);
}
if((T-lchild !=NULL)(T-rchild!=NULL))
{
if(T-lchild-date== ch)
{
T-lchild=NULL;
}
if(T-rchild-date == ch)
{
T-rchild=NULL;
}
delData(T-lchild, ch);
delData(T-rchild, ch);
}
}
void CreateBiTree(BiTree T)
{ //建立二叉数用的函数
char b;
cinb;
if(b=='#')
T=NULL;
else
{
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
return ;
else
T-date=b;
CreateBiTree(T-lchild);
CreateBiTree(T-rchild);
}
return ;
}
void insertData(BiTree T, char ch)//插入数据
{
if(!T)
return;
else
{
if(T-date==ch)
{
int check;cout" 请输入数字：\n 1为该数据插入左孩子，2为该数据插入右孩子"endl;
cincheck;
if((T-lchild!=NULL)check==1)
{
cout" 该节点左孩子非空，无法插入"endl;
return;
}
if((T-rchild!=NULL)check==2)
{
cout" 该节点右孩子非空，无法插入"endl;
return;
}
if((T-lchild==NULL)check==1)
{
BiTree h;
h = (BiTNode *)malloc(sizeof(BiTNode));
char mo;
cout" 输入要插入的数据"endl;
cinmo;
h-date=mo;
h-lchild=NULL;
h-rchild=NULL;
T-lchild=h;
cout" 插入成功!"endl;
}
if((T-rchild==NULL)check==2)
{
BiTree h1;
h1=(BiTNode*)malloc(sizeof(BiTNode));
char mo1;cout" 输入要插入的数据"endl;
cinmo1;
h1-date=mo1;
h1-lchild=NULL;
h1-rchild=NULL;
T-rchild=h1;
cout" 插入成功!"endl;
}
}
else
{
insertData(T-lchild, ch);
insertData(T-rchild, ch);
}
}
}
//下面三个函数分别是前序，中序和后序遍历二叉树用的函数
void PreOrderTraverse(BiTree T)
{ //前序
if(T==NULL)
return ;
cout" ";
coutT-date;
PreOrderTraverse(T-lchild);
PreOrderTraverse(T-rchild);
}
void InOrderTraverse(BiTree T)
{ //中序
if(T==NULL)
return ;
InOrderTraverse(T-lchild);
cout" "T-date;
InOrderTraverse(T-rchild);
}
void PostOrderTraverse(BiTree T)
{ //后序
if(T==NULL)
return ;
PostOrderTraverse(T-lchild);
PostOrderTraverse(T-rchild);
cout" "T-date;
}
//主函数
void main()
{
BiTree T;int a;
char b;
do{
cout"\n 进入本程序后首先要建立一个二叉树，否则不能进一步操作\n\n 请按y确认首先建立二叉树\n";
cinb;
}while(b!='y'b!='Y');
do{
cout"\n 本系统可以提供下列操作："endl;
cout" 1.建立一棵二叉树（先序）"endl;
cout" 2.前序遍历此二叉树"endl;
cout" 3.中序遍历此二叉树"endl;
cout" 4.后序遍历此二叉树"endl;
cout" 5.输出二叉树某个节点的左右孩子"endl;
cout" 6.输出二叉树某个节点的父节点"endl;
cout" 7.删除二叉树以某个节点为父节点的子树"endl;
cout" 8.为该树中的某个节点插入孩子节点"endl;
cout" 9.统计节点数目"endl;
cout" 10.分别统计左右孩子节点数目"endl;
cout" 0.结束程序"endlendl;
cina;
coutendlendl;
switch(a)
{
case 1:
cout" 请输入数据建立一棵二叉树,输入#表示数为空"endl;
CreateBiTree(T);
break;
case 2:
cout" 先序遍历顺序为:";
PreOrderTraverse(T);
break;
case 3:
cout" 中序遍历顺序为:";
InOrderTraverse(T);
break;
case 4:
cout" 后序遍历顺序为:";
PostOrderTraverse(T);
break;
case 5:
char posi;BiTree ch;
cout" 请输入要查询的孩子的父节点:\n\n";
cinposi;
ch=children_search(T,posi);
if(ch-lchild!=NULLch-rchild!=NULL)
{
cout" 此节点的左孩子:"ch-lchild-date"; ";
cout" 右孩子:"ch-rchild-dateendl;
}
else
{
if(ch-lchild!=NULLch-rchild==NULL)
{
cout" 此节点的左孩子:"ch-lchild-date"; ";
cout" 右孩子不存在"endl;
}
else
{
if(ch-lchild==NULLch-rchild!=NULL)
{
cout"\n 此节点的左孩子不存在"endl;
cout" 右孩子:"ch-rchild-date"\n ";
}
else
cout" 两个孩子都不存在"endl;
}
}
break;
case 6:
char child;
cout"输入子节点:";
cinchild;
parent_search(T,child);
break;
case 7:
char fu;
cout" 输入删除子树的根节点:";
cinfu;
delData(T,fu);
cout" 删除后先序遍历顺序为:";
PreOrderTraverse(T);
coutendlendl;
break;
case 8:
char parent;
cout"输入要插入孩子的父节点"endl;
cinparent;
insertData(T,parent);
break;
case 9:
{
int b=0;
sumnode(T,b);
cout" 该树的节点数目是："bendl;}
break;
case 10:
int lef;int righ;lef=0;righ=0;
sumlr(T,lef,righ);
cout" 此树左孩子数目为："lef" ""右孩子数目为："righendl;
break;
case 0:
break;
default :
cout" 输入数字错误,请重新输入数字 "endl;
break;
}
}while(a!=0);
coutendlendl;
}
已通过编译