今天给各位分享bst树的常见操作c语言的知识，其中也会对bst树中序遍历进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！
本文目录一览：
1、二叉排序树的C语言实现2、二叉树的基本操作 C语言版的3、求数据结构 B-树与B+树及其操作的代码（C语言版）4、用C语言实现二叉排序树排序，并按递减顺序打印各个数据5、关于c语言树的建立及操作
二叉排序树的C语言实现
两处编译错误 已修改
见代码中注释([flczzhang]-XXX)
#include stdio.h
#include stdlib.h
typedef int KeyType;
typedef struct node
{
KeyType key;
struct node *lchild,*rchild;
} BSTNode;
typedef BSTNode *BSTree;
//二叉排序树插入
//若二叉排序树 *Tptr中没有关键字为key，则插入，否则直接返回
void InsertBST( BSTree *TPtr , KeyType key )
{
BSTNode *f , *p;
p = *TPtr; //p的初值指向根结点
while(p) //查找插入位置
{
if( p-key == key ) //树中已有key，无须插入
{
return;
}
f=p; //f保存当前查找的结点
//若keyp-key，则在左子树中查找，否则在右子树中查找
p=(keyp-key)? p-lchild:p-rchild;
}
p=(BSTNode *)malloc( sizeof(BSTNode) );
p-key=key;
p-lchild=p-rchild=NULL;//生成新结点
if(*TPtr==NULL) //原树为空
{
*TPtr=p; //新插入的结点为新的根
}
else //原树非空时将新结点p作为f的左孩子或右孩子插入
{
if(keyf-key)
{
f-lchild=p;
}
else
{
f-rchild=p;
}
}//[flczzhang]- miss a }
}
//创建二叉排序树
//输入一个结点序列，建立一棵二叉排序树，将根结点指针返回
BSTree CreateBST( void )
{
BSTree T=NULL;
KeyType key;
scanf( “%d” , key );
while(key) //假设key=0是输人结束标志
{
InsertBST( T , key );//将key插入二叉排序树T
scanf( “%d” , key );//读人下一关键字
}
return T;
}
//查找二叉排序树 T 中是否存在指定的 key
//指针 f 指向 T 的双亲, f 初始值为 NULL
//若查找成功返回1，指针p指向该数据元素结点，否则返回0，p指向查找过程中的最后一个结点
int SearchBST( BSTree T , int key , BSTree f , BSTree *p)
{
if( !T )
{
*p = f;
return 0;
}
else if( T-key == key )
{
*p = T;
return 1;
}
else if( T-key key )
{
return SearchBST( T-lchild , key , T , p );
}
else
{
return SearchBST( T-rchild , key , T , p );
}
}
//访问节点数据
void visit( KeyType c , int level )
{
printf( “%d 在第 %d 层\n” ,c , level );
}
//前序遍历树节点
void PreorderTraverse( BSTree T ,int level )
{
if(T)
{
visit(T-key , level );
PreorderTraverse(T-lchild , level+1 );
PreorderTraverse(T-rchild , level+1 );
}
}
int main()
{
int level=1;
BSTree T;
T = CreateBST();//[flczzhang]- type error for function name CreateBST(missing e)
PreorderTraverse( T , level );
return 0;
}
二叉树的基本操作 C语言版的
#include iostream.h
typedef struct BiTNode
{
char data;
int bit;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode;
void InitBT(BiTNode *t)//1、初始化，不带头结点
{
t=NULL;
}
/*void InitBT(BiTNode *t)//初始化，带头结点
{
t=new BiTNode;
t-lchild=t-rchild=t-parent=NULL;
}*/
int EmptyBT(BiTNode *t)//判断队空
{
if(t==0)
return 1;
else
return 0;
}
BiTNode *creatBT(BiTNode *t,int b)//2、创建二叉树
{
BiTNode *p;
char ch;
cinch;
if(ch==’#’)return 0;
else
{
p=new BiTNode;
p-data=ch;
p-parent=t;
p-bit=b;
t=p;
t-lchild=creatBT(t,0);
t-rchild=creatBT(t,1);
}
return t;
}
void preorder(BiTNode *t)//3、先序遍历
{
if(!EmptyBT(t))
{
coutt-data;
preorder(t-lchild);
preorder(t-rchild);
}
}
void inorder(BiTNode *t)//中序遍历
{
if(!EmptyBT(t))
{
inorder(t-lchild);
coutt-data;
inorder(t-rchild);
}
}
void postorder(BiTNode *t)//后序遍历
{
if(!EmptyBT(t))
{
postorder(t-lchild);
postorder(t-rchild);
coutt-data;
}
}
void coutBT(BiTNode *t,int m,int n,int i)//4、计算二叉树中叶子结点、度为2的结点和度为1的结点的个数
{
if(!EmptyBT(t))
{
if((t-lchild==0) (t-rchild==0))
m++;//叶子结点
else if((t-lchild!=0) (t-rchild!=0))
i++;//度为2的结点
else
n++;//度为1的结点
coutBT(t-lchild,m,n,i);
coutBT(t-rchild,m,n,i);
}
}
void coutNode(BiTNode *t,int k)//5、求二叉树中结点个数
{
if(!EmptyBT(t))
{
k++;
coutNode(t-lchild,k);
coutNode(t-rchild,k);
}
}
int BTdepth(BiTNode *t)//6、求二叉树的深度
{
int i,j;
if(EmptyBT(t))
return 0;
else
{
i=BTdepth(t-lchild);
j=BTdepth(t-rchild);
return (ij?i:j)+1;
}
}
int Xdepth(BiTNode *t,char x)//7、查找x的层数
{
int num1,num2,n;
if(t==NULL)
return 0;
else{
if(t-data==x)
return 1;
num1=Xdepth(t-lchild,x);
num2=Xdepth(t-rchild,x);
n=num1+num2;
if(num1!=0||num2!=0)
n++;
return n;
}
}
static int flag;
void SearchChild(BiTNode *t,int k)//8、查找第k个结点的左右孩子
{
if(!EmptyBT(t))
{
if(k==0)
{
cout”位置不能为0!”endl;
return;
}
else
{
flag++;
if(flag==k)
{
if(t-lchild==0)
cout”无左孩子! “;
else
cout”左孩子为：”(t-lchild-data)” “;
if(t-rchild==0)
cout”无右孩子!”endl;
else
cout”右孩子为：”(t-rchild-data)endl;
}
else
{
SearchChild(t-lchild,k);
SearchChild(t-rchild,k);
}
}
}
}
int Xancestor(BiTNode *t,char x)//9、查找x结点祖先
{
int n,num1,num2;
if(t==NULL)
return 0;
else
{
if(t-data==x)
return 1;
num1=Xancestor(t-lchild,x);
num2=Xancestor(t-rchild,x);
n=num1+num2;
if(n!=0)
{
n++;
coutt-data” “endl;
}
}
}
void BTNodePath(BiTNode *t)//10、输出所有叶子结点路径
{
if(!EmptyBT(t))
{
if((t-lchild==0) (t-rchild==0))
{
coutt-data”的路径为：”;
for(BiTNode *p=t;p!=0;p=p-parent)
coutp-data;
coutendl;
}
else
{
BTNodePath(t-lchild);
BTNodePath(t-rchild);
}
}
}
void BTNodebit(BiTNode *t)//11、输出所有叶子结点编码
{
if(!EmptyBT(t))
{
if((t-lchild==0) (t-rchild==0))
{
coutt-data”的编码为：”;
for(BiTNode *p=t;p-parent!=0;p=p-parent)
coutp-bit;
coutendl;
}
else
{
BTNodebit(t-lchild);
BTNodebit(t-rchild);
}
}
}
void main()
{
BiTNode *t;
int m,n,i,d,q,k;
char x;
cout”1、初始化…”endl;
InitBT(t);
cout”2、创建二叉树…”endl;
t=creatBT(t,0);
cout”3.1、先序遍历…”endl;
preorder(t);
coutendl;
cout”3.2、中序遍历…”endl;
inorder(t);
coutendl;
cout”3.3、后序遍历…”endl;
postorder(t);
coutendl;
m=n=i=0;
cout”4、计算叶子结点，度为1的结点和度为2的结点的个数…”endl;
coutBT(t,m,n,i);
cout”叶子结点个数为：”mendl;
cout”度为1的结点个数为：”nendl;
cout”度为2的结点个数为：”iendl;
q=0;
cout”5、计算结点个数…”endl;
coutNode(t,q);
cout”结点个数为：”qendl;
d=0;
cout”6、计算深度…”endl;
d=BTdepth(t);
cout”深度为：”dendl;
cout”7、求x的层数…”endl;
cout”输入x：”;
cinx;
if(Xdepth(t,x)==0)
cout”x不存在！”endl;
else
coutXdepth(t,x)endl;
cout”8、输入要查找孩子的结点在先序遍历中的位置k（不等于0）：”;
cink;
SearchChild(t,k);
if(kflag)
cout”位置超出长度!”endl;
cout”9、查询结点的所有祖先，请输入结点x：”;
cinx;
int num;
num=Xancestor(t,x);
if(num==0)
cout”结点不存在！”endl;
if(num==1)
cout”根结点无祖先！”endl;
cout”10、输出所有叶子结点路径（叶→根）：”endl;
BTNodePath(t);
cout”11、输出所有叶子结点编码（叶→根）：”endl;
BTNodebit(t);
}
求数据结构 B-树与B+树及其操作的代码（C语言版）
那个叫二叉树啊
树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
一、树的概述
树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。以下具体地给出树的定义及树的数据结构表示。
（一）树的定义
树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(ROOT)的结点；
⒉剩下的结点被分成n=0个互不相交的集合T1、T2、……Tn，而且，
这些集合的每一个又都是树。树T1、T2、……Tn被称作根的子树(Subtree)。
树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树
1.树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。
2.树的深度——组成该树各结点的最大层次，如上图，其深度为4；
3.森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合就为森林；
4.有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。
5.树的表示
树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如上图可写成如下形式：
(A(B(E(K,L),F),C(G),D(H(M),I,J)))
5.
2
二叉树
1.二叉树的基本形态：
二叉树也是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：
(1)空二叉树——(a)；
(2)只有一个根结点的二叉树——(b)；
(3)右子树为空的二叉树——(c)；
(4)左子树为空的二叉树——(d)；
(5)完全二叉树——(e)
注意：尽管二叉树与树有许多相似之处，但二叉树不是树的特殊情形。
用C语言实现二叉排序树排序，并按递减顺序打印各个数据
#include stdio.h
#include malloc.h
typedef int KeyType;
typedef char InfoType[10];
typedef struct node //记录类型
{
KeyType key; //关键字项
InfoType data; //其他数据域
struct node *lchild,*rchild; //左右孩子指针
} BSTNode;
int InsertBST(BSTNode *p,KeyType k)
{
if (p==NULL) //原树为空, 新插入的记录为根结点
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p-key=k;
p-lchild=p-rchild=NULL;
return 1;
}
else if (k==p-key) //树中存在相同关键字的结点,返回0
return 0;
else if (kp-key)
return InsertBST(p-lchild,k); //插入到*p的左子树中
else
return InsertBST(p-rchild,k); //插入到*p的右子树中
}
BSTNode *CreateBST(KeyType A[],int n) //返回BST树根结点指针
{
BSTNode *bt=NULL; //初始时bt为空树
int i=0;
while (in)
{
InsertBST(bt,A[i]); //将关键字A[i]插入二叉排序树T中
i++;
}
return bt; //返回建立的二叉排序树的根指针
}
void DispInDescrease(BSTNode *bt){ //按从小到大输出查找树中的内容，对该树中序遍历即可
if(bt){
DispInDescrease(bt-lchild);
printf(“%d\t”,bt-key);
DispInDescrease(bt-rchild);
}
}
void main()
{
BSTNode *bt,*p,*f;
int n=9;
KeyType a[]={1,12,5,8,3,10,7,13,9};
bt=CreateBST(a,n);
DispInDescrease(bt);
}
//已上机验证成功
关于c语言树的建立及操作
//—————————————————————————
#include stdio.h
#include stdlib.h
typedef struct np{
int dat;
struct np *left,*right;
} node;
node *create(void)
{
return (malloc(sizeof(node)));
}
node *t(node *a,int d)/*建立二叉树*/
{
if (a==NULL) {
a=create();
a-left =a-right =NULL;
a-dat=d;
}
else if (d=a-dat) {
a-right =t(a-right,d);
}
else if (da-dat) {
a-left =t(a-left ,d);
}
return a;
}
void prt(node *r)
{
if (r!=NULL) {
printf(“%d “,r-dat );
prt(r-left );
prt(r-right );
}
}
int main(void)
{
node *bst=NULL;
int i;
while (scanf(“%d”,i),i!=-1111){ /*从键盘输入整数，以-1111结束输入*/
bst=t(bst,i); /*生成二叉排序数*/
}
prt(bst); /*前序遍历*/
putchar(‘\n’);
return 0;
}
//—————————————————————————
关于bst树的常见操作c语言和bst树中序遍历的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
微信扫一扫 
支付宝扫一扫 
