本文目录一览：
如何使用C或C++结构建立八叉树的模型
以下程序摘自互联网，是C++的
如果要用C语言编写，则
（1）使用C结构建立八叉树的模型
1.typedef struct OctreeNode 2.{ 3. int value; 4. struct OctreeNode *Up; 5. struct OctreeNode *Down; 6. struct OctreeNode *Left; 7. struct OctreeNode *Right; 8. struct OctreeNode *Front; 9. struct OctreeNode *Back; 10.}OctreeNode;
（2）递归添加上下左右前后邻居，我这里只给一面
1.void AddUp(OctreeNode *Me, int v) 2.{ 3. Me-Up = (OctreeNode *)malloc(sizeof (OctreeNode)); 4. Me-Up-vvalue = v; 5. Me-Up-Up = NULL; 6. Me-Up-Down = Me; 7. Me-Up-Front = NULL; 8. OctreeMe-Up-Back = NULL; 9. Me-Up-Right = NULL; 10. Me-Up-Left = NULL; 11.}
实现Octree的原理
(1). 设定最大递归深度
(2). 找出场景的最大尺寸，并以此尺寸建立第一个立方体
(3). 依序将单位元元素丢入能被包含且没有子节点的立方体
(4). 若没有达到最大递归深度，就进行细分八等份，再将该立方体所装的单位元元素全部分担给八
个子立方体
(5). 若发现子立方体所分配到的单位元元素数量不为零且跟父立方体是一样的，则该子立方体停止
细分，因为跟据空间分割理论，细分的空间所得到的分配必定较少，若是一样数目，则再怎么切数目
还是一样，会造成无穷切割的情形。
(6). 重复3，直到达到最大递归深度。
#include iostream.h
using namespace std;//定义八叉树节点类
templateclass T
struct OctreeNode
{
T data; //节点数据
T xmin,xmax; //节点坐标，即六面体个顶点的坐标
T ymin,ymax;
T zmin,zmax;
OctreeNode T *top_left_front,*top_left_back; //该节点的个子结点
OctreeNode T *top_right_front,*top_right_back;
OctreeNode T *bottom_left_front,*bottom_left_back;
OctreeNode T *bottom_right_front,*bottom_right_back;
OctreeNode //节点类
(T nodeValue = T(),
T xminValue = T(),T xmaxValue = T(),
T yminValue = T(),T ymaxValue = T(),
T zminValue = T(),T zmaxValue = T(),
OctreeNodeT* top_left_front_Node = NULL,
OctreeNodeT* top_left_back_Node = NULL,
OctreeNodeT* top_right_front_Node = NULL,
OctreeNodeT* top_right_back_Node = NULL,
OctreeNodeT* bottom_left_front_Node = NULL,
OctreeNodeT* bottom_left_back_Node = NULL,
OctreeNodeT* bottom_right_front_Node = NULL,
OctreeNodeT* bottom_right_back_Node = NULL )
:data(nodeValue),
xmin(xminValue),xmax(xmaxValue),
ymin(yminValue),ymax(ymaxValue),
zmin(zminValue),zmax(zmaxValue),
top_left_front(top_left_front_Node),
top_left_back(top_left_back_Node),
top_right_front(top_right_front_Node),
top_right_back(top_right_back_Node),
bottom_left_front(bottom_left_front_Node),
bottom_left_back(bottom_left_back_Node),
bottom_right_front(bottom_right_front_Node),
bottom_right_back(bottom_right_back_Node){}
};
//创建八叉树
template class T
void createOctree(OctreeNodeT * root,int maxdepth,double xmin,double xmax,double ymin,double ymax,double zmin,double zmax)
{
cout"处理中，请稍候……"endl;
maxdepth=maxdepth-1; //每递归一次就将最大递归深度-1
if(maxdepth=0)
{
root=new OctreeNodeT();
root-data = 9; //为节点赋值，可以存储节点信息，如物体可见性。由于是简单实现八叉树功能，简单赋值为。
root-xmin=xmin; //为节点坐标赋值
root-xmax=xmax;
root-ymin=ymin;
root-ymax=ymax;
root-zmin=zmin;
root-zmax=zmax;
double xm=(xmax-xmin)/2;//计算节点个维度上的半边长
double ym=(ymax-ymin)/2;
double zm=(ymax-ymin)/2;
//递归创建子树，根据每一个节点所处（是几号节点）的位置决定其子结点的坐标。
createOctree(root-top_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root-top_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root-top_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmax-zm,zmax);
createOctree(root-top_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmax-zm,zmax);
createOctree(root-bottom_left_front,maxdepth,xmin,xmax-xm,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root-bottom_left_back,maxdepth,xmin,xmax-xm,ymin,ymax-ym,zmin,zmax-zm);
createOctree(root-bottom_right_front,maxdepth,xmax-xm,xmax,ymax-ym,ymax,zmin,zmax-zm);
createOctree(root-bottom_right_back,maxdepth,xmax-xm,xmax,ymin,ymax-ym,zmin,zmax-zm);
}
}
int i=1;
//先序遍历八叉树
template class T
void preOrder( OctreeNodeT * p)
{
if(p)
{
couti".当前节点的值为："p-data"\n坐标为：";
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
i+=1;
coutendl;
preOrder(p-top_left_front);
preOrder(p-top_left_back);
preOrder(p-top_right_front);
preOrder(p-top_right_back);
preOrder(p-bottom_left_front);
preOrder(p-bottom_left_back);
preOrder(p-bottom_right_front);
preOrder(p-bottom_right_back);
coutendl;
}
}
//求八叉树的深度
templateclass T
int depth(OctreeNodeT * p)
{
if(p == NULL)
return -1;
int h = depth(p-top_left_front);
return h+1;
}
//计算单位长度，为查找点做准备
int cal(int num)
{
int result=1;
if(1==num)
result=1;
else
{
for(int i=1;inum;i++)
result=2*result;
}
return result;
}
//查找点
int maxdepth=0;
int times=0;
static double xmin=0,xmax=0,ymin=0,ymax=0,zmin=0,zmax=0;
int tmaxdepth=0;
double txm=1,tym=1,tzm=1;
templateclass T
void find(OctreeNodeT * p,double x,double y,double z)
{
double xm=(p-xmax-p-xmin)/2;
double ym=(p-ymax-p-ymin)/2;
double zm=(p-ymax-p-ymin)/2;
times++;
if(xxmax || xxmin || yymax || yymin || zzmax || zzmin)
{
cout"该点不在场景中！"endl;
return;
}
if(x=p-xmin+txm x=p-xmax-txm y=p-ymin+tym y=p-ymax-tym z=p-zmin+tzm z=p-zmax-tzm )
{
coutendl"找到该点！""该点位于"endl;
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
cout"节点内！"endl;
cout"共经过"times"次递归！"endl;
}
else if(x(p-xmax-xm) y(p-ymax-ym) z(p-zmax-zm))
{
cout"当前经过节点坐标："endl;
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
coutendl;
find(p-bottom_left_back,x,y,z);
}
else if(x(p-xmax-xm) y(p-ymax-ym) z(p-zmax-zm))
{
cout"当前经过节点坐标："endl;
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
coutendl;
find(p-top_left_back,x,y,z);
}
else if(x(p-xmax-xm) y(p-ymax-ym) z(p-zmax-zm))
{
cout"当前经过节点坐标："endl;
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
coutendl;
find(p-bottom_right_back,x,y,z);
}
else if(x(p-xmax-xm) y(p-ymax-ym) z(p-zmax-zm))
{
cout"当前经过节点坐标："endl;
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
coutendl;
find(p-top_right_back,x,y,z);
}
else if(x(p-xmax-xm) y(p-ymax-ym) z(p-zmax-zm))
{
cout"当前经过节点坐标："endl;
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
coutendl;
find(p-bottom_left_front,x,y,z);
}
else if(x(p-xmax-xm) y(p-ymax-ym) z(p-zmax-zm))
{
cout"当前经过节点坐标："endl;
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
coutendl;
find(p-top_left_front,x,y,z);
}
else if(x(p-xmax-xm) y(p-ymax-ym) z(p-zmax-zm))
{
cout"当前经过节点坐标："endl;
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
coutendl;
find(p-bottom_right_front,x,y,z);
}
else if(x(p-xmax-xm) y(p-ymax-ym) z(p-zmax-zm))
{
cout"当前经过节点坐标："endl;
cout" xmin: "p-xmin" xmax: "p-xmax;
cout" ymin: "p-ymin" ymax: "p-ymax;
cout" zmin: "p-zmin" zmax: "p-zmax;
coutendl;
find(p-top_right_front,x,y,z);
}
}
//main函数
int main ()
{
OctreeNodedouble * rootNode = NULL;
int choiced = 0;
while(true)
{
system("cls");
cout"请选择操作：\n";
cout"1.创建八叉树 2.先序遍历八叉树\n";
cout"3.查看树深度 4.查找节点 \n";
cout"0.退出\n\n";
cinchoiced;
if(choiced == 0)
return 0;
else if(choiced == 1)
{
system("cls");
cout"请输入最大递归深度："endl;
cinmaxdepth;
cout"请输入外包盒坐标，顺序如下：xmin,xmax,ymin,ymax,zmin,zmax"endl;
cinxminxmaxyminymaxzminzmax;
if(maxdepth=0 || xmaxxmin || ymaxymin || zmaxzmin || xmin0 || ymin0 ||zmin0)
{
tmaxdepth=cal(maxdepth);
txm=(xmax-xmin)/tmaxdepth;
tym=(ymax-ymin)/tmaxdepth;
tzm=(zmax-zmin)/tmaxdepth;
createOctree(rootNode,maxdepth,xmin,xmax,ymin,ymax,zmin,zmax);
}
else
{
cout"输入错误！";
return 0;
}
}
else if(choiced == 2)
{
system("cls");
cout"先序遍历八叉树结果：\n";
i=1;
preOrder(rootNode);
coutendl;
system("pause");
}
else if(choiced == 3)
{
system("cls");
int dep = depth(rootNode);
cout"此八叉树的深度为"dep+1endl;
system("pause");
}
else if(choiced == 4)
{
system("cls");
cout"请输入您希望查找的点的坐标，顺序如下：x,y,z\n";
double x,y,z;
cinxyz;
times=0;
coutendl"开始搜寻该点……"endl;
find(rootNode,x,y,z);
system("pause");
}
else
{
system("cls");
cout"\n\n错误选择！\n";
system("pause");
}
}
}
代码在C-free下测试可用
关于C语言二叉树?
首先二叉树的结点是由做孩子指针*lchild 右孩子指针*rchild 以及数据成员data
L表示左孩子R表示右孩子T表示他们的父结点
后序遍历的访问顺序是LRT
中序遍历的访问顺序是LTR
前序遍历的访问顺序是TLR
其中说的前中后就是指访问父结点的次序；
拓扑图在这里没法给出啊。。。
--------------------------------------------
这是我用C++类写的二叉树的头文件，里面有几个函数你可能用不到，你主要看看那几个遍历函数
#includeiostream
using namespace std;
typedef char elemType;
struct bnode
{
bnode *lchild,*rchild;
elemType data;
};
class BinaryTree
{
public:
BinaryTree();
void create(bnode* tempR);
void visite(bnode *T);
void preorder(bnode *T);
void inorder(bnode *T);
void postorder(bnode *T);
int high(bnode *T);
void convert(bnode* tempR,string a,int i);
void copy(bnode *T,bnode *T1);
void level(bnode *T,int i);
void swap(bnode *T);
bnode *root;
private:
int count;
};
BinaryTree::BinaryTree()
{
root = NULL;
count = 0;
}
void BinaryTree::create(bnode* tempR)
{
elemType x;
cinx;
if(x == '.')
{
tempR = NULL;
}
else
{
tempR = new bnode;
count++;
tempR-data = x;
create(tempR-lchild);
create(tempR-rchild);
}
}
void BinaryTree::visite(bnode *T)
{
if(T!=NULL)
coutT-data' ';
}
void BinaryTree::preorder(bnode *T)
{
if(T!=NULL)
{
visite(T);
preorder(T-lchild);
preorder(T-rchild);
}
}
void BinaryTree::inorder(bnode *T)
{
if(T!=NULL)
{
inorder(T-lchild);
visite(T);
inorder(T-rchild);
}
}
void BinaryTree::postorder(bnode *T)
{
if(T!=NULL)
{
postorder(T-lchild);
postorder(T-rchild);
visite(T);
}
}
int BinaryTree::high(bnode *T)
{
if(T==NULL)
return 0;
else if(high(T-lchild)high(T-rchild))
return high(T-lchild)+1;
else
return high(T-rchild)+1;
}
void BinaryTree::level(bnode *T,int i)
{
if(T!=NULL)
{
level(T-lchild,i+1);
visite(T);
couti' ';
level(T-rchild,i+1);
}
}
void BinaryTree::convert(bnode *T,string a,int i)
{
elemType x;
if(i=a.length())
{
x = a[i-1];
T = new bnode;
count++;
T-data = x;
convert(T-lchild,a,2*i);
convert(T-rchild,a,2*i+1);
}
else
{
T=NULL;
}
}
void BinaryTree::copy(bnode *T,bnode *T1)
{
elemType x;
if(T!=NULL)
{
x=T-data;
if(x == '.')
{
T1 = NULL;
}
else
{
T1 = new bnode;
T1-data = x;
T1-lchild = NULL;
T1-rchild = NULL;
copy(T-lchild,T1-lchild);
copy(T-rchild,T1-rchild);
}
}
}
void BinaryTree::swap(bnode *T)
{
if(T!=NULL)
{
bnode *temp;
temp=T-lchild;
T-lchild=T-rchild;
T-rchild=temp;
swap(T-lchild);
swap(T-rchild);
}
}
C语言二叉树
在create_tree中，参数t只在一开始被bintree初始化，此时他们同时指向未初始化的内存。当执行到t=(tree * )malloc(sizeof(tree));时候，t被赋予了新的内存空间，注意，这里新分配的内存仅仅是分配给了t，与bintree没有关系。每次进入create_tree后都为局部变量t分配内存，而你在函数退出之后无法进行内存回收，进而造成内存泄露。
正确的做法是，给create_tree传递一个指针类型的引用，tree *t，这样你在操作t的时候就像在操作bintree一样，才能达到给bintree分配内存的目的。
最后别忘了写一个释放内存的方法：
void free_tree(tree *t)
{
if (t)
{
free_tree(t-lchild);
free_tree(t-rchild);
printf("\n%c has freed.", t-data);
free(t);
}
}
跪求关于c语言多叉树添加节点的问题
数据结构:
struct list
{
/* other data */
int effectif_class_1;
int effectif_class_2;
struct list *parent;
struct list *child[];
}
struct list * findNode(struct list *point)
{
int i;
if(point-data == data)
return point;
i=0;
while(point-child[i] != NULL){
if( (findNode(point-child[i])) == point-child[i])
return point-child[i];
i++;
}
return NULL;
}
void addNode_changeNoeud(struct list *point)
{
int i=0;
while(point-child[i] != NULL)
{
point-child[i]-Noeud ++;
addNode_changeNoeud(point-child[i]);
i++;
}
}
void addNode(struct list *point, /* data */)
{ //在point的最右端插入一个子节点
int i=0;
/* 定位到最右端 */
while(point-child[i] != NULL){
i++;
}
point-child[i] = (struct list *)malloc(sizeof(struct list));
/* 保存其他数据到 point-child[i]-data */
/* 更改所有父节点的 effectif_class */
struct list *tmp;
tmp = point-parent;
while(tmp != NULL){
tmp-effectif_class_1 = tmp-effectif_class_1 + /* effectif_class_1 */ ;
tmp-effectif_class_2 = tmp-effectif_class_2 + /* effectif_class_2 */ ;
tmp = tmp-parent;
}
/* 插入节点后,更新编号 */
point-child[i] = point-child[i-1] + 1;
addNode_changeNoeud(point); /* 这个不好说,用于更新编号Noeud的,自己理解吧... */
}
请问C语言如何创建二叉树？？？？
创建二叉树的源程序如下：
#include cstdlib
#include stdio.h
typedef struct node
{ //树的结点
int data;
struct node* left;
struct node* right;
} Node;
typedef struct
{ //树根
Node* root；
} Tree;
void insert(Tree* tree, int value)//创建树
{
Node* node=(Node*)malloc(sizeof(Node));//创建一个节点
node-data = value;
node-left = NULL;
node-right = NULL;
if (tree-root == NULL)//判断树是不是空树
{
tree-root = node;
}
else
{//不是空树
Node* temp = tree-root;//从树根开始
while (temp != NULL)
{
if (value temp-data)//小于就进左儿子
{
if (temp-left == NULL)
{
temp-left = node;
return;
}
else
{//继续判断
temp = temp-left;
}
}
else {//否则进右儿子
if (temp-right == NULL)
{
temp-right = node;
return;
}
else {//继续判断
temp = temp-right;
}
}
}
}
return；
}
void inorder(Node* node)//树的中序遍历
{
if (node != NULL)
{
inorder(node-left);
printf("%d ",node-data);
inorder(node-right);
}
}
int main()
{
Tree tree;
tree.root = NULL;//创建一个空树
int n;
scanf("%d",n);
for (int i = 0; i n; i++)//输入n个数并创建这个树
{
int temp;
scanf("%d",temp);
insert(tree, temp);
}
inorder(tree.root);//中序遍历
getchar();
getchar();
return 0;
}
扩展资料：
简单二叉树定义范例：此树的顺序结构为：ABCDE
#include cstdlib
#include stdio.h
#include string
int main()
{
node* p = newnode;
node* p = head;
head = p;
string str;
cin str;
creat(p, str, 0)//默认根结点在str下标0的位置
return 0;
}
//p为树的根结点（已开辟动态内存）,str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组，r当前结点所在顺序存储数组位置
void creat(node* p, string str, int r)
{
p-data = str[r];
if (str[r * 2 + 1] == '#' || r * 2 + 1 str.size() - 1)p-lch = NULL；
else
{
p-lch = newnode;
creat(p-lch, str, r * 2 + 1);
}
if (str[r * 2 + 2] == '#' || r * 2 + 2 str.size() - 1)p-rch = NULL;
else
{
p-rch = newnode;
creat(p-rch, str, r * 2 + 2);
}
}
C语言二叉树定义
这个结构体的{}之后，表示的是类型名称啊，BiTNode表示这种结构体的类型名称为BiTNode，*BiTree表示指向这种结构体的指针的类型名称为BiTree。
比如你定义变量的时候：
BiTNode a;//定义了一个上面那样的结构体
BiTree b;//定义了一个指针，该指针的类型是指向一个上面那样的结构体的
