c語言八叉樹,二叉樹構造c語言實現

本文目錄一覽：

• 1、如何使用C或C++結構建立八叉樹的模型
• 2、關於C語言二叉樹?
• 3、C語言二叉樹
• 4、跪求關於c語言多叉樹添加節點的問題
• 5、請問C語言如何創建二叉樹？？？？
• 6、C語言二叉樹定義

如何使用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;//定義了一個指針，該指針的類型是指向一個上面那樣的結構體的