// 创建二叉树的原数组数据: 40 20 60 10 30 50 70
创新互联是一家专注于成都做网站、成都网站制作、成都外贸网站建设与策划设计,固镇网站建设哪家好?创新互联做网站,专注于网站建设十年,网设计领域的专业建站公司;建站业务涵盖:固镇等地区。固镇做网站价格咨询:028-86922220
// 前序遍历序列: 40 20 10 30 60 50 70
// 中序遍历序列: 10 20 30 40 50 60 70
// 后序遍历序列: 10 30 20 50 70 60 40
// 输入关键字k1,k2的数值: 30 50
// 打印的结果:
// 40 30 50
//
// 二叉树示意图:
//
// 40
// / \
// 20 60
// / \ / \
// 10 30 50 70
#include "stdio.h"
#include "stdlib.h"
struct Tree
{
int data;
struct Tree *left;
struct Tree *right;
};
typedef struct Tree TreeNode;
typedef TreeNode *Bitree;
Bitree insertNode(Bitree root,int data) //插入结点
{
Bitree newnode;
Bitree current;
Bitree back;
newnode=(Bitree)malloc(sizeof(TreeNode));
if(newnode==NULL)
{
printf("\n动态分配内存出错.\n");
exit(1);
}
newnode-data=data;
newnode-left=NULL;
newnode-right=NULL;
if(root==NULL)
{
return newnode;
}
else
{
current=root;
while(current!=NULL)
{
back=current;
if(current-data data)
current=current-left;
else
current=current-right;
}
if(back-data data)
back-left=newnode;
else
back-right=newnode;
}
return root;
}
Bitree createTree(int *data,int len) //创建二叉树(非递归)
{
Bitree root=NULL;
int i;
for(i=0;ilen;i++)
{
root=insertNode(root,data[i]);
}
return root;
}
void preOrder(Bitree ptr) //先序遍历(递归法)
{
if(ptr!=NULL)
{
printf("%d ",ptr-data);
preOrder(ptr-left);
preOrder(ptr-right);
}
}
void inOrder(Bitree ptr) //中序遍历(递归法)
{
if(ptr!=NULL)
{
inOrder(ptr-left);
printf("%d ",ptr-data);
inOrder(ptr-right);
}
}
void postOrder(Bitree ptr) //后序遍历(递归法)
{
if(ptr!=NULL)
{
postOrder(ptr-left);
postOrder(ptr-right);
printf("%d ",ptr-data);
}
}
//根据关键字k1和k2,进行区间查找(递归法)
void btreeSearch(Bitree ptr,int k1,int k2)
{
if(ptr!=NULL)
{
if(ptr-data k1 ptr-data k2)
{
btreeSearch(ptr-right,k1,k2);
}
else if(ptr-data == k1 ptr-data k2)
{
printf("%d ",ptr-data);
btreeSearch(ptr-right,k1,k2);
}
else if(ptr-data k1 ptr-data k2)
{
printf("%d ",ptr-data);
btreeSearch(ptr-left,k1,ptr-data);
btreeSearch(ptr-right,ptr-data,k2);
}
else if(ptr-data k1 ptr-data == k2)
{
printf("%d ",ptr-data);
btreeSearch(ptr-left,k1,k2);
}
else if(ptr-data k1 ptr-data k2)
{
btreeSearch(ptr-left,k1,k2);
}
else if(ptr-data == k1 ptr-data == k2)
{
printf("%d ",ptr-data);
}
else
{
printf("其它情况,当前节点的数值是%d",ptr-data);
}
}
}
int main()
{
Bitree T=NULL; //T是二叉查找树
int data[]={40,20,60,10,30,50,70};
int len;
int i;
int k1,k2; //关键字k1,k2
int tmp;
len=sizeof(data)/sizeof(int);
printf("创建二叉树的原数组数据: ");
for(i=0;ilen;i++)
{
printf("%d ",data[i]);
}
T=createTree(data,len); //创建二叉树
printf("\n前序遍历序列: ");
preOrder(T);
printf("\n中序遍历序列: ");
inOrder(T);
printf("\n后序遍历序列: ");
postOrder(T);
printf("\n输入关键字k1,k2的数值: ");
scanf("%d%d",k1,k2);
if(k1k2)
{
tmp=k1;
k1=k2;
k2=tmp;
}
//根据关键字k1和k2,进行区间查找(递归法)
btreeSearch(T,k1,k2);
printf("\n");
return 0;
}
二叉树的遍历分为以下三种：
先序遍历：遍历顺序规则为【根左右】
中序遍历：遍历顺序规则为【左根右】
后序遍历：遍历顺序规则为【左右根】
什么是【根左右】？就是先遍历根，再遍历左孩子，最后遍历右孩子；
举个例子，看下图：
先序遍历：ABCDEFGHK
中序遍历：BDCAEHGKF
后序遍历：DCBHKGFEA
以中序遍历为例：
中序遍历的规则是【左根右】，我们从root节点A看起；
此时A是根节点，遍历A的左子树；
A的左子树存在，找到B，此时B看做根节点，遍历B的左子树；
B的左子树不存在，返回B，根据【左根右】的遍历规则，记录B，遍历B的右子树；
B的右子树存在，找到C，此时C看做根节点，遍历C的左子树；
C的左子树存在，找到D，由于D是叶子节点，无左子树，记录D，无右子树，返回C，根据【左根右】的遍历规则，记录C，遍历C的右子树；
C的右子树不存在，返回B，B的右子树遍历完，返回A；
至此，A的左子树遍历完毕，根据【左根右】的遍历规则，记录A，遍历A的右子树；
A的右子树存在，找到E，此时E看做根节点，遍历E的左子树；
E的左子树不存在，返回E，根据【左根右】的遍历规则，记录E，遍历E的右子树；
E的右子树存在，找到F，此时F看做根节点，遍历F的左子树；
F的左子树存在，找到G，此时G看做根节点，遍历G的左子树；
G的左子树存在，找到H，由于H是叶子节点，无左子树，记录H，无右子树，返回G，根据【左根右】的遍历规则，记录G，遍历G的右子树；
G的右子树存在，找到K，由于K是叶子节点，无左子树，记录K，无右子树，返回G，根据【左根右】的遍历规则，记录F，遍历F的右子树；
F的右子树不存在，返回F，E的右子树遍历完毕，返回A；
至此，A的右子树也遍历完毕；
最终我们得到上图的中序遍历为BDCAEHGKF，无非是按照遍历规则来的；
根据“中序遍历”的分析，相信先序遍历和后序遍历也可以轻松写出~
分类: 电脑/网络 程序设计 其他编程语言
问题描述:
+20
c语言-
(求)
树,二叉树,二叉查找树区别
和用他们做的C语言简单编成
最好有详细解释。
谢谢
解析:
二叉树是指结点的度最大为2，也就是一个结点最多只有两个分支。二叉树与度为2的树的区别是二叉树是顺序树，即有严格的左右之分，而度为2的树却没有这种要求。
二叉排序树是在二叉树的基础上面将小于结点的分支都放在该结点的左边，而大于该结点的分支都放在右边的树，这样很便于查找。
我只给你写了一些主要的函数：
struct point {
int data;
struct point *lchild;
struct point *rchild;
};
/*建立二叉排序树*/
struct point *creattree(int data[],int n)
{
int i;
struct point *T;
T=NULL;
for(i=0;in;i++)
T=insert(T,data[i]);
return T;
}
/*插入一个结点*/
struct point *insert(struct point *T,int item)
{
struct point *p1,*p2;
p1=(struct point *)malloc(sizeof(struct point ));
p1-data=item;
p1-lchild=NULL;
p1-rchild=NULL;
if(T==NULL)
T=p1;
else if(T!=NULL){
p2=T;
while(1)
{
if(itemp2-data)
{
if(p2-lchild!=NULL)
p2=p2-lchild;
else{
p2-lchild=p1;
break;
}
}
else
{
if(p2-rchild!=NULL)
p2=p2-rchild;
else{
p2-rchild=p1;
break;
}
}
}
}
return T;
}
/*对二叉树进行中序遍历，如果一个结点左孩子的值大于它，或者是右孩子的值小于它，则不为顺序树*/
int INorder(struct point *T,int n)
{
struct point *stack[30];
int top=-1,i=0;
struct point *p;
p=T;
do{
while(p!=NULL)
{
stack[++top]=p;
p=p-lchild;
}
p=stack[top--];
if(((p-lchild)-data)p-data||(p-rchild)-data)p-data)
return 0;
p=p-rchild;
}while(p!=NULL||top!=-1);
p=p-rchild;
printf("%d",p-data);
}
