正文
二叉树的实现c语言主函数 二叉树用c语言实现
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
数据结构二叉树的程序，用c语言怎么实现？
您好，想要实现一个二叉树，需要用到结构体来存储每个节点的信息，并使用指针来存储每个节点的左右子节点的地址。具体的实现方法可以参考下面的代码示例：
#include stdio.h
#include stdlib.h
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* createNode(int val) {
struct TreeNode* node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
node-val = val;
node-left = NULL;
node-right = NULL;
return node;
}
void insertNode(struct TreeNode* root, int val) {
if (root == NULL) {
return;
}
if (val root-val) {
if (root-left == NULL) {
root-left = createNode(val);
} else {
insertNode(root-left, val);
}
} else {
if (root-right == NULL) {
root-right = createNode(val);
} else {
insertNode(root-right, val);
}
}
}
void printTree(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d\n", root-val);
printTree(root-left);
printTree(root-right);
}
int main() {
struct TreeNode* root = createNode(5);
insertNode(root, 3);
insertNode(root, 2);
insertNode(root, 4);
insertNode(root, 7);
insertNode(root, 6);
insertNode(root, 8);
printTree(root);
return 0;
}
在这段代码中，我们定义了一个结构体 TreeNode 来表示二叉树的每个节点，结构体中包含了一个节点的数值 val，以及指向左子节点和右子节点的指针 left 和 right。
二叉树的基本操作 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);
}
C语言二叉树递归算法怎么做？
#include stdio.h
#include string.h
struct treenode{
int value;
treenode* left;
treenode* right;
};
typedef treenode* BiTree;
void visit(treenode* node)
{
printf("%2d ", node-value);
}
// 结点总数
int node(BiTree T)
{
if( !T ){
return 0;
}
return node(T-left) + node(T-right) + 1;
}
// 前序
void preOrder(BiTree T)
{
if( T ){
visit(T);
preOrder(T-left);
preOrder(T-right);
}
}
// 中序
void inOrder(BiTree T)
{
if( T ){
inOrder(T-left);
visit(T);
inOrder(T-right);
}
}
// 后序
void postOrder(BiTree T)
{
if( T ){
postOrder(T-left);
postOrder(T-right);
visit(T);
}
}
// 叶子节点数
int leafnode(BiTree T)
{
if( T ){
if( !T-left !T-right )
return 1;
else
leafnode(T-left) + leafnode(T-right);
}else{
return 0;
}
}
int height(BiTree T)
{
if( T ){
int lh = height(T-left);
int rh = height(T-right);
return (lhrh ? lh:rh) + 1;
}else{
return 0;
}
}
int main()
{
return 0;
}
二叉树c语言实现
#includeiostream.h
#include stdio.h
#include stdlib.h
typedef struct node {
char data;
struct node *lchild,*rchild;//
}BiTNode,*BiTree;
void CreatBiTree(BiTree T)
{
char ch;
ch=getchar();
if (ch == ' ')
T = 0;
else {
T=(BiTNode*)malloc(sizeof(BiTNode));
T-data=ch;//生成根节点
CreatBiTree(T-lchild);//构造左子树
CreatBiTree(T-rchild);//构造右子树
}
}
void preorder(BiTree T)//前序遍历
{
if (T!=NULL){
printf ("%c",T-data);
preorder(T-lchild);
preorder(T-rchild);
}
}
void inorder(BiTree T)//中序遍历
{
if (T!=NULL){
inorder(T-lchild);
printf ("%c",T-data);
inorder(T-rchild);
}
}
void postorder(BiTree T)//后序遍历
{
if (T!=NULL){
postorder(T-lchild);
postorder(T-rchild);
printf ("%c",T-data);
}
}
void main ()
{
cout"请输入要创建二叉树的实现c语言主函数的二叉树包括空格:"endl ;
BiTree T;
CreatBiTree(T);//创建二叉树
cout"前序遍历二叉树的实现c语言主函数的结果为:"endl;
preorder(T);
coutendl;
cout"中序遍历的结果为:"endl;
inorder(T);
coutendl;
cout"后序遍历的结果为:"endl;
postorder(T);
}
关于二叉树的实现c语言主函数和二叉树用c语言实现的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。
