建树

C语⾔建树

话不多说，先看代码：

#include

#include

#include

structTreeNode{//结构体⽤来储存树结点，包括节点的值data，分别指向左孩⼦右孩⼦的指针；

intdata;

structTreeNode*left,*right;

};

voidSetTree(structTreeNode**root,intval){//建树函数，传参为根节点的地址，新增数；

structTreeNode*t;//储存新结点；

t=(structTreeNode*)malloc(sizeof(structTreeNode));

t->data=val;

t->left=NULL;

t->right=NULL;

if((*root)==NULL){//if根结点为空，把新增节点设为根结点；

(*root)=t;

return;

}

if((*root)->data>val)SetTree(&((*root)->left),val);//新增值⼩于该结点的值，放到左孩⼦，递归；

elSetTree(&((*root)->right),val);//⼤于，右孩⼦，递归；

}

voidShowTree(structTreeNode*root){//打印函数；中序遍历；

if(root==NULL){

return;

}

//left;

ShowTree(root->left);

//root;

printf("%d",root->data);

//right;

ShowTree(root->right);

}

intmain(){

intN;

intval;

structTreeNode*root;

root=NULL;

scanf("%d",&N);

while(N--){

scanf("%d",&val);

SetTree(&root,val);

}

ShowTree(root);

return0;

}

注意：上边代码，树的打印顺序是中序遍历；

有中则必有先后；

树的遍历有三种⽅法，前序遍历，中序遍历，后序遍历；

如上图

前序遍历（DLR）是先遍历根结点，然后遍历左⼦树，最后遍历右⼦树。

ABDGHECKFIJ;

中序遍历（LDR）是先遍历左⼦树，然后遍历根结点，最后遍历右⼦树。

GDHBEACKFIJ;

后序遍历（LRD）是先遍历左⼦树，然后遍历右⼦树，最后遍历根节点。

GHDEBKJIFCA;

其实代码很好写的，中序遍历就不再重复写了，下⾯写前序遍历和后序遍历；

前序遍历：

voidDLRShowTree(structTreeNode*root){//打印函数；前序遍历；

if(root==NULL){

return;

}

//root;

printf("%d",root->data);

//left;

DLRShowTree(root->left);

//right;

DLRShowTree(root->right);

}

后序遍历：

voidLRDShowTree(structTreeNode*root){//打印函数；后序遍历；

if(root==NULL){

return;

}

//left;

LRDShowTree(root->left);

//right;

LRDShowTree(root->right);

//root;

printf("%d",root->data);

}

#include

#include

#include

usingnamespacestd;

typedefstructnode*position;

typedefpositionTree;

structnode{

intval;

Treeleft,right;

};

TreebuildTree(Treeroot,intx){

if(root==NULL){

Treerr=(structnode*)malloc(sizeof(structnode));

rr->val=x;

rr->left=rr->right=NULL;

root=rr;

returnroot;

}

if(xval)root->left=buildTree(root->left,x);

elroot->right=buildTree(root->right,x);

returnroot;

}

voidprintTree(Treeroot){

if(root==NULL)return;

printTree(root->left);

cout<val<

printTree(root->right);

}

intmain(){

intn;

cin>>n;

intx;

Treeroot=NULL;

for(inti=0;i

cin>>x;

root=buildTree(root,x);

}

printTree(root);

return0;

}