数据结构：C语言实现二叉树的构建以及遍历操作

约定不等于承诺〃 2022-05-17 13:04 121阅读 0赞

使用二叉链表的存储结构存储二叉树：

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;
    }

以上仅供参考，欢迎纠错讨论