数据结构 如何创建一棵树,请给出c语言详细代码,谢谢
作者&投稿:童废 (若有异议请与网页底部的电邮联系)
其实构造一棵树和构造链表没多大区别,你要理解链表后就会了,真的!!
有前序遍历,中序遍历,后序遍历等方法产生二叉树,题目描述不太明确!
刚刚回答了一个类似的问题,以下代码供参考:#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef char TElemType;
typedef int Status;
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild;
// 左右孩子指针
} BiTNode, *BiTree;
//以下是建立二叉树存储结构,空节点输入作为#结束标识
Status CreateBiTree(BiTree &T) {
//请将该算法补充完整,参见第6章课件算法或课本
char ch;
scanf("%c",&ch);
if(ch=='#') T=NULL;
else{
if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))
exit(OVERFLOW);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
} // CreateBiTree
void Preorder(BiTree T)
{
if(T)
{
printf("%c",T->data);
Preorder(T->lchild);
Preorder(T->rchild);
}
}
void Inorder(BiTree T)
{ // 中序遍历二叉树
//请将该算法补充完整,参见第6章课件算法
if(T)
{
Inorder(T->lchild);
printf("%c",T->data);
Inorder(T->rchild);
}
}
void Postorder(BiTree T)
{ // 后序遍历二叉树
//请将该算法补充完整,参见第6章课件算法
if(T)
{
Postorder(T->lchild);
Postorder(T->rchild);
printf("%c",T->data);
}
}
//以下是求叶子结点数
void CountLeaf(BiTree T,int& count){
//请将该算法补充完整,参见第6章课件算法
if(T){
if((!T->lchild)&&(!T->rchild))
count++;
CountLeaf(T->lchild,count);
CountLeaf(T->rchild,count);
}
}
//以下是求二叉树的深度
int Depth(BiTree T ){
//请将该算法补充完整,参见第6章课件算法
int depthval,depthLeft,depthRight;
if(!T) depthval=0;
else{
depthLeft = Depth(T->lchild);
depthRight = Depth(T->rchild);
if(depthLeft>depthRight)depthval = 1+depthLeft;
else depthval = 1+depthRight;
}
return depthval;
}
void main(){
BiTree T;
int s=0,d;
printf("\n creat of the bitree:\n");
CreateBiTree(T);
printf("\n output result of Preorder:\n");
Preorder(T);
CountLeaf(T,s);
d=Depth(T);
printf("\n leaves=%d\n",s);
printf("\n depth=%d\n",d);
}
以下是一个简单的C语言程序,可以创建一棵二叉树:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int data;
struct node *left;
struct node *right;
} Node;
Node* create(int data) {
Node *node = (Node*)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void insert(Node **root, int data) {
if (*root == NULL) {
*root = create(data);
} else if (data < (*root)->data) {
insert(&(*root)->left, data);
} else if (data > (*root)->data) {
insert(&(*root)->right, data);
}
}
void inorder(Node *root) {
if (root != NULL) {
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
}
int main() {
Node *root = NULL;
// 创建二叉树
insert(&root, 5);
insert(&root, 3);
insert(&root, 7);
insert(&root, 1);
insert(&root, 9);
// 中序遍历二叉树并输出结果
inorder(root);
return 0;
}
```
在上述代码中,我们首先定义了二叉树节点的数据结构 `Node`,其中包含了节点的值以及左右子节点的指针。然后,我们提供了两个函数:`create()` 和 `insert()`。`create()` 函数用于创建新的节点,并返回其指针;`insert()` 函数用于向二叉树中插入新的节点。
在 `insert()` 函数中,我们首先判断当前根节点是否为 `NULL`,如果是,则将新节点插入到该位置;否则,递归地向下查找合适的插入位置。需要注意的是,这里假设二叉树中不会存储重复的值。
最后,我们在 `main()` 函数中创建了一棵二叉树,并调用 `inorder()` 函数进行中序遍历,将其结果输出到控制台。在实际应用中,可以根据需要实现其他遍历方式,如前序遍历和后序遍历等。
例如,对于以上示例代码,程序将输出以下结果:
```
1 3 5 7 9
```
需要注意的是,在实际应用中还需要考虑更多的边界情况和错误处理。例如,可能出现内存分配失败、节点重复插入或删除失败等问题。
# include <stdio.h>
# include <stdlib.h
typedef struct BiTNode
{
char data;
struct BiTNode * lchild,* rchild;
}BiTNode, *BiTree;
//先序建立二叉树中的节点
BiTree CreatBiTree()
{
BiTree T;
char ch;
fflush(stdin);
scanf("%c",&ch);
if(ch == '0')
{
return NULL;
}
else
{
T=(BiTNode *)malloc(sizeof(BiTNode));
if(!T)
exit(1);
T->data=ch;
T->lchild = CreatBiTree();
T->rchild = CreatBiTree();
return T;
}
}
void PreTravel(BiTree T)
{
if(T)
{
printf("%c ",T->data);
PreTravel(T->lchild);
PreTravel(T->rchild);
}
}
int main()
{
BiTree T;
printf("先序建立二叉树结点(‘0’表示空):\n");
T = CreatBiTree();
printf("先序遍历创建的二叉树:\n");
PreTravel(T);
printf("\n");
return 0;
}
/*
结果:
------------------------
先序建立二叉树结点(‘0’表示空):
a
b
0
0
c
0
0
先序遍历创建的二叉树:
a b c
Press any key to continue
------------------------------
*/
线魏赛明: 刚刚回答了一个类似的问题,以下代码供参考: #include "stdio.h" #include "stdlib.h" #define OK 1 #define ERROR 0 #define OVERFLOW -2typedef char TElemType; typedef int Status; typedef struct BiTNode { // 结点结构TElemType data; ...
长泰县19361343975: 数据结构C语言:怎样构造一棵树 - ?
线魏赛明: 首先确定存储结构,比如是双亲表示还是孩子兄弟链表表示或者孩子链表表示 再按此存储结构规则将树中的所有边(结点的关系)输入,就可以将树构造好了
长泰县19361343975: 数据结构建树程序,C语言C++皆可 - ?
线魏赛明: #include <stdio.h> #include <stdlib.h> #include<iostream.h> #define maxnode 100 #define NULL 0 typedef char DataType; /*设数据域类型为字符型*/ typedef struct node{ DataType data; struct node *lchild,*rchild; /*左右链域为指向结点结构的指...
长泰县19361343975: 数据结构二叉树的创建(c语言版) - ?
线魏赛明: //输入的格式为:abd##e##c###include "stdlib.h"typedef int Element;struct Tree {Element data;struct Tree *left;struct Tree *right; };void CreateBinSortTree(struct Tree **t); void InsertNode2Tree(struct Tree **root, Element num);void ...
长泰县19361343975: c语言数据结构:怎么建立一个二叉树? - ?
线魏赛明: 只要将一个二叉树用“括号表示法”表示出来,然后,用链式存储结构将其各个结点存储就可以了,也就是输入一个二叉树.最后,用中序遍历输出! typedef struct node{ ElemType data;struct node *lchild,*rchild;} BTNode; //创建一个二叉树...
长泰县19361343975: 数据结构用c语言写:创建树,并进行先序,中序,后序遍历! - ?
线魏赛明: #include <iostream> using namespace std; class Node { public:Node(){ this->pLchild = this->pRchild = NULL; } char data; Node * pLchild; Node * pRchild; }; Node * CreateTree() { Node * root = new Node; root->data = 'A'; Node * pB = new Node; pB-...
长泰县19361343975: 数据结构试验(用C语言)建立一棵二叉树,并用递归或者非递归的算法分别用先序.中序和后序遍历、谢谢 - ?
线魏赛明: #define LEN sizeof(struct tree)#define NULL 0#include#include struct tree { char data; struct tree *lchild,*rchild; };//创建二叉树 struct tree *creat() { char c; struct tree *t; c=getchar(); if(c==' ') t=NULL; else { t=(struct tree*)malloc(LEN); t->data=c; t->...
长泰县19361343975: 求c语言数据结构二叉树的建树,前序遍历,输出树的代码,能用采纳. - ?
线魏赛明: #include#include#define MAXSIZE 100 //二叉树中最多的结点数 typedef char TElemType; typedef struct BiTNode { TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree;//定义函数指针 typedef void(* Visit)(BiTree);//二叉树的初始化 ...
长泰县19361343975: 二叉树的创建和遍历演示(数据结构c语言版)?
线魏赛明: 等一下,我好好研究一下数据结构,努力编写一下,看看可不可以做出来. 把函数写好了. typedef struct bnode { char data; struct bnode *lchild,*rchild; }Btree; void preorder(Btree *p)//先序遍历 { if(p!=NULL) {printf("%c",p->data); preorder(p->...
长泰县19361343975: 求数据结构(C语言版)建立二叉树的代码~~急~~谢谢了 - ?
线魏赛明: 二叉树具有以下重要性质: 性质1 二叉树第i层上的结点数目最多为2i-1(i≥1). 证明:用数学归纳法证明: 归纳基础:i=1时,有2i-1=20=1.因为第1层上只有一个根结点,所以命题成立. 归纳假设:假设对所有的j(1≤j<i)命题成立,即第j层上至多...