使用二叉链表的存储结构存储二叉树:
typedef struct BinNode{
int data;
struct BinNode *lchild;
struct BinNode *rchild;
}BinNode,*BinTree;
BinTree binTree;
一个简单的结构体存储节点。。
递归的思想实现对二叉树的遍历构建以及查找操作
先序遍历:
void firstSeek(BinTree node){
if(node==NULL){
return;
}
printf("%d ",node->data);
firstSeek(node->lchild);
firstSeek(node->rchild);
}
中序遍历:
void midSeek(BinTree node){
if(node==NULL)
return ;
midSeek(node->lchild);
printf("%d ",node->data);
midSeek(node->rchild);
}
后序遍历:
void lastSeek(BinTree node){
if(node==NULL)
return ;
lastSeek(node->lchild);
lastSeek(node->rchild);
printf("%d ",node->data);
}
代码很简单,理解了二叉树的基本结构和递归思想是关键
可以输入数据测试一下代码,构建二叉树输入叶子节点的左右孩子时输入数据置-1即可:
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ElemType int
using namespace std;
typedef struct BinNode{
int data;
struct BinNode *lchild;
struct BinNode *rchild;
}BinNode,*BinTree;
BinTree binTree;
//先序建立
void createBinTree(BinTree &binTree){
ElemType info;
BinNode *r,*l,*s;
scanf("%d",&info);
if(info==-1){
return ;
}
if(binTree==NULL){
binTree = (BinNode *)malloc(sizeof(BinNode));
binTree->data=info;
binTree->lchild=NULL;
binTree->rchild=NULL;
}
createBinTree(binTree->lchild);
createBinTree(binTree->rchild);
}
//先序遍历
void firstSeek(BinTree node){
if(node==NULL){
return;
}
printf("%d ",node->data);
firstSeek(node->lchild);
firstSeek(node->rchild);
}
//中序遍历
void midSeek(BinTree node){
if(node==NULL)
return ;
midSeek(node->lchild);
printf("%d ",node->data);
midSeek(node->rchild);
}
//后续遍历
void lastSeek(BinTree node){
if(node==NULL)
return ;
lastSeek(node->lchild);
lastSeek(node->rchild);
printf("%d ",node->data);
}
int main(){
createBinTree(binTree);
printf("二叉树构建完成!\n先序遍历:");
firstSeek(binTree);
printf("\n中序遍历:");
midSeek(binTree);
printf("\n后续遍历:");
lastSeek(binTree);
return 0;
}
以上仅供参考,欢迎纠错讨论