c语言实现二叉树基本功能

妖狐艹你老母 2022-05-17 08:50 176阅读 0赞

**二叉树声明:**

typedef struct Node{
    	int data;
    	Node *left;
    	Node *right;
    }Node,*pNode;

**二叉树创建:**

int create(pNode *t){
    	int ch;
    	scanf_s("%d",&ch);
    	if(ch==-1){
    		*t=NULL;
    		return 0;
    	}else{
    		*t=(pNode)malloc(sizeof(Node));
    		if((*t)==NULL){
    			printf("failed\n");
    			return 0;
    		}else{
    			(*t)->data=ch;
    			printf("请输入%d的左节点数据:",ch);
    			create(&((*t)->left));
    			printf("请输入%d的右节点数据:",ch);
    			create(&((*t)->right));
    		}
    	}
    	return 1;
    }

注意：(1).当输入-1时，需要把该节点设置为null，要不然在后边的遍历会一直循环下去，并且要return，不再执行create（）;

(2).使用结构体指针，函数传入参数只需要指针（4个字节），而传入结构体需要更多字节，所以用结构体指针更好

(3).在main函数中，如果int x，想在另外函数中改变此值并且不返回该值，f1函数需要传入int \*x（指针就是该变量的地址），然后在main函数中使用f1（&x）把变量地址传递过去，然后在f1函数中使用\*x=5，改变x的值，此时在main函数中输出x就是5，就可以实现在别的函数中改变main函数中变量x的值了

(4).如（3），所以在pNode \*t，使用\*t进行操作，把main函数声明的空树变成二叉树

**前序遍历:**

void PreOrderBinaryTree(pNode t){
    	if(t==NULL){
    		return;
    	}else{
    		printf("%d ",t->data);
    	    PreOrderBinaryTree(t->left);
    		PreOrderBinaryTree(t->right);
    	}
    }

**中序遍历:**

void MiddleOrderBinaryTree(pNode t){
    	if(t==NULL){
    		return;
    	}else{
    	    MiddleOrderBinaryTree(t->left);
    		printf("%d ",t->data);
    		MiddleOrderBinaryTree(t->right);
    	}
    }

**后序遍历：**

void PostOrderBinaryTree(pNode t){
    	if(t==NULL){
    		return;
    	}else{
    	    PostOrderBinaryTree(t->left);
    		PostOrderBinaryTree(t->right);
    		printf("%d ",t->data);
    	}
    }

注意：（1）.遍历需要加入条件t！=null才进行遍历，否则使用递归会一直循环下去

（2）.前序：先根再左右 中序：先左再根再右 后序:先左再右再根

**main函数：**

void main(){
    pNode t;
    printf("请输入第一个节点的数据,-1表示没有值:");
    create(&t);
    printf("前序遍历二叉树:");
    PreOrderBinaryTree(t);
    printf("\n");
    system("pause");
    printf("中序遍历二叉树:");
    MiddleOrderBinaryTree(t);
    printf("\n");
    system("pause");
    printf("后序遍历二叉树:");
    PostOrderBinaryTree(t);
    printf("\n");
    system("pause");
    }

注意：（1）.pNode t相当于int x，create（&t）相当于f1（&x），这些函数都是对变量t或x的值进行改变，而在PreOrderBinaryTree（t），只传入t，没有传入&t，因为此时t已经有值，我们只需要对他进行遍历，不需要对t的值进行改变，所以只传入t

**完整代码：**

#include<stdlib.h>
    #include<stdio.h>
    #include<malloc.h>
    typedef struct Node{
    	int data;
    	Node *left;
    	Node *right;
    }Node,*pNode;
    int create(pNode *t){
    	int ch;
    	scanf_s("%d",&ch);
    	if(ch==-1){
    		*t=NULL;
    		return 0;
    	}else{
    		*t=(pNode)malloc(sizeof(Node));
    		if((*t)==NULL){
    			printf("failed\n");
    			return 0;
    		}else{
    			(*t)->data=ch;
    			printf("请输入%d的左节点数据:",ch);
    			create(&((*t)->left));
    			printf("请输入%d的右节点数据:",ch);
    			create(&((*t)->right));
    		}
    	}
    	return 1;
    }
    
    void PreOrderBinaryTree(pNode t){
    	if(t==NULL){
    		return;
    	}else{
    		printf("%d ",t->data);
    		PreOrderBinaryTree(t->left);
    		PreOrderBinaryTree(t->right);
    	}
    }
    void PostOrderBinaryTree(pNode t){
    	if(t==NULL){
    		return;
    	}else{
    		PostOrderBinaryTree(t->left);
    		PostOrderBinaryTree(t->right);
    		printf("%d ",t->data);
    	}
    }
    void MiddleOrderBinaryTree(pNode t){
    	if(t==NULL){
    		return;
    	}else{
    		MiddleOrderBinaryTree(t->left);
    		printf("%d ",t->data);
    		MiddleOrderBinaryTree(t->right);
    	}
    }
    void main(){
    	pNode t;
    	printf("请输入第一个节点的数据,-1表示没有值:");
    	create(&t);
    	printf("前序遍历二叉树:");
    	PreOrderBinaryTree(t);
    	printf("\n");
    	system("pause");
    	printf("中序遍历二叉树:");
    	MiddleOrderBinaryTree(t);
    	printf("\n");
    	system("pause");
    	printf("后序遍历二叉树:");
    	PostOrderBinaryTree(t);
    	printf("\n");
    	system("pause");
    }