C语言实现一个二叉树

时间：2021-10-02 10:10:11

命名恐慌症，stack和二叉树的结点名字，函数名字有点相似，希望以后能注意这个问题

收获

typedef struct node{
	BiTree lchild;
	BiTree rchild;
	T data;
}Node;
Node为一个类型（相当于int char）,这样写是为了方便，以后写类型的时候不用写struct node 

struct node{	BiTree lchild;	BiTree rchild;	T data;}Node;
Node是一个变量，此时可以直接给Node赋值，以后写结构类型的时候还是要写成struct node。


正文

BiTree.h

/*************************************************************************
	> File Name: BiTree.h
	> Author: bairutai
	> Mail: bairutai@aliyun.com 
	> Created Time: 2015年09月22日 星期二 11时40分49秒
 ************************************************************************/
#ifndef _BITREE_H_
#define _BITREE_H_
#include <stdbool.h>
typedef int T;
typedef struct node *BiTree;
typedef struct node{
	BiTree lchild;
	BiTree rchild;
	T data;
}Node;

//初始化一个二叉树
BiTree* initBiTree(Node **);
//摧毁一个二叉树
void DestoryBiTree(BiTree *);
//判断一个二叉树是否为空
bool isEmpty(BiTree);
//得到一个二叉树的深度
int getDepth(BiTree);
//生成节点
Node* MakeNode(T data, Node* lchild, Node* rchild);
//先序遍历
void pre_order(Node *);
//中序遍历
void mid_order(Node *);
//后序遍历
void after_order(Node *);
//非递归先序遍历
void pre_order_(Node *);
//非递归中序遍历
void mid_order_(Node *);
//非递归后序遍历
void after_order_(Node *);
#endif

BiTree.c 

/*************************************************************************
  > File Name: BiTree.c
  > Author: bairutai
  > Mail: bairutai@aliyun.com 
  > Created Time: 2015年09月22日 星期二 14时23分50秒
 ************************************************************************/

#include<stdio.h>
#include<malloc.h>
#include"BiTree.h"
#include"stack.h"

// 制造一个空的二叉树
BiTree* initBiTree(Node** root){
	BiTree* biTree = root;
	return biTree;
}

/* 摧毁二叉树
 * 这里传入二级指针是因为，指针传递的时候，是传递了一份拷贝，这样并不能
 * 改变指针的值或者操作指针（比如这个函数里面要free掉），所以这里传入二
 * 级指针，可以方便的free掉指针
 */

void DestoryBiTree(BiTree *biTree)
{
	if (NULL == *biTree){
		return;
	}
	else{
		DestoryBiTree(&((*biTree)->lchild));
		DestoryBiTree(&((*biTree)->rchild));
	}
	printf("destory  %d \n", (*biTree)->data);
	free(*biTree);
	*biTree = NULL;
}

// 判断二叉树是否为空
bool isEmpty(BiTree biTree)
{
	if (NULL == biTree){
		return true;
	}
	else{
		return false;
	}
}

// 得到二叉树深度
int getDepth(BiTree biTree)
{
	int depth,ldepth,rdepth;
	depth = ldepth = rdepth = 0;
	if (NULL == biTree){
		return 0;
	}
	else{
		ldepth = getDepth(biTree->lchild);
		rdepth = getDepth(biTree->rchild);
		depth = ldepth > rdepth ? ldepth:rdepth;
		return depth + 1;
	}
}

// 制造二叉树结点
Node* MakeNode(T data, Node *lchild, Node *rchild)
{
	Node *node =(Node*)malloc(sizeof(Node));
	node->data = data;
	node->lchild = lchild;
	node->rchild = rchild;
	return node;
}

// 递归前序遍历
// 根->左->右
void pre_order(Node *node)
{
	if (NULL == node) {
		return;
	}
	else {
		printf("%d ", node->data);
		pre_order(node->lchild);
		pre_order(node->rchild);
	}
}

// 递归中序遍历
// 左->根->右
void mid_order(Node *node)
{
	if (NULL == node) {
		return;
	}
	else {
		mid_order(node->lchild);
		printf("%d ", node->data);
		mid_order(node->rchild);
	}
}

// 递归后序遍历
// 左->右->根
void after_order(Node *node)
{
	if (NULL == node) {
		return;
	}
	else {
		after_order(node->lchild);
		after_order(node->rchild);
		printf("%d ", node->data);
	}
}

/* 非递归前序遍历
 * 1)访问结点P，并将结点P入栈;
 * 2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右子结点置为当前的结点P，循环1);若不为空，则将P的左子结点置为当前的结点P;
 * 3)直到P为NULL并且栈为空，则遍历结束。
 */
void pre_order_(Node *node)
{
	Stack *stack = InitEmptyStack();
	while(NULL != node || !isEmpty_(stack)){
		while(NULL != node){
			// 访问结点
			printf("%d ",node->data);
			// 入栈
			push(stack, node);
			// 左子结点直为当前结点
			node = node->lchild;
		}
		if(!isEmpty_(stack)){
			// 出栈
			PNode pnode = pop(stack);
			node = pnode->data;
			// 右子结点置为当前结点
			node = node->rchild;
		}
	}
}

/* 非递归中序遍历
 * 1)若其左子结点不为空，则将P入栈并将P的左子结点置为当前的结点P，然后对当前结点P再进行相同的处理；
 * 2)若其左孩子为空，则取栈顶元素并进行出栈操作，并访问该栈顶结点，然后将当前的P置为栈顶结点的右子结点；
 * 3)直到P为NULL并且栈为空则遍历结束
 */
void mid_order_(Node *node)
{
	Stack *stack = InitEmptyStack();
	while(NULL != node || !isEmpty_(stack)){
		while(NULL != node){
			// 入栈
			push(stack, node);
			// 左子结点置为当前结点
			node = node->lchild;
		}
		if(!isEmpty_(stack)){
			// 出栈
			PNode pnode = pop(stack);
			node = pnode->data;
			// 访问栈顶结点
			printf("%d ",node->data);
			// 右子结点置为当前结点
			node = node->rchild;
		}
	}
}

/* 非递归后序遍历
 * 对于任一结点P，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左子结点的结点，此时该结点出现在栈顶，但是此时不能将其出栈并访问，因为其右子结点还未被访问。
 * 所以接下来按照相同的规则对其右子结点进行相同的处理，当访问完其右子结点时，该结点又出现在栈顶，此时可以将其出栈并访问。
 * 这样就保证了正确的访问顺序。可以看出，在这个过程中，每个结点都两次出现在栈顶，只有在第二次出现在栈顶时，才能访问它。
 */
void after_order_(Node *node)
{
	// 记录前一个被访问的结点
	Node *prenode = NULL;
	Stack *stack = InitEmptyStack();
	while(NULL != node || !isEmpty_(stack)){
		while(NULL != node){
			// 入栈
			push(stack, node);
			// 左子结点置为当前结点
			node = node->lchild;
		}
		// 左子结点为空时，将当前结点置为栈顶结点
		node = stack->head->data;
		// 当前结点的右子结点为空或者右子结点已经访问过，则访问该结点
		if(NULL == node->rchild || prenode == node->rchild){
			// 访问该结点
			printf("%d ",node->data);
			// 更新标记的访问过的结点
			prenode = node;
			// 出栈
			PNode pnode = pop(stack);
			// 将当前结点置为空
			node = pnode->data = NULL;
		}
		else{
			// 否则将右子结点置为当前结点
			node = node->rchild;
		}
	}
}

stack.h

/*************************************************************************
	> File Name: stack.h
	> Author: bairutai
	> Mail: bairutai@aliyun.com 
	> Created Time: 2015年09月11日 星期五 10时51分13秒
 ************************************************************************/
#ifndef _STACK_H_
#define _STACK_H_
#include <stdbool.h>
#include "BiTree.h"

typedef Node* L;
typedef struct node_ *PNode;
typedef struct node_{
	L data;
	PNode next;
}Node_;
typedef struct{
	int size;
	PNode head;
}Stack;

/*构造一个空栈*/
Stack *InitEmptyStack();

//摧毁一个栈
void destory(Stack *);

//栈头元素出栈
PNode pop(Stack*);

//元素入栈
void push(Stack *, L);

//判断是否为空栈
bool isEmpty_(Stack *);
#endif

stack.c 

/*************************************************************************
	> File Name: Stack/stack.c
	> Author: bairutai
	> Mail: bairutai@aliyun.com 
	> Created Time: 2015年09月11日 星期五 11时07分12秒
 ************************************************************************/

#include<stdio.h>
#include"stack.h"
#include<malloc.h>

Stack *InitEmptyStack()
{
	Stack *stack = (Stack*)malloc(sizeof(Stack));
	stack->size = 0;
	stack->head = NULL;
}


void destory(Stack *stack)
{
	if (NULL == stack) {
		return;
	}
	while(!isEmpty_(stack))
	{
		pop(stack);
	}
	free(stack);
}

bool isEmpty_(Stack *stack)
{
	if (NULL == stack) 
	{
		return false;
	}
	else
	{
		if(0 == stack->size && NULL == stack->head)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}

void push(Stack *stack, L data)
{
	if (NULL == stack)
	{
		return;
	}
	else 
	{
		if (isEmpty_(stack))
		{
			PNode node = (PNode)malloc(sizeof(Node_));
			node->data = data;
			node->next = NULL;
			stack->head = node;
			stack->size++;
		}
		else
		{
			PNode node = (PNode)malloc(sizeof(Node_));
			node->data = data;
			node->next = stack->head;
			stack->head = node;
			stack->size++;
		}
	}
}

PNode pop(Stack *stack)
{
	if(NULL == stack)
	{
		return NULL;
	}
	else
	{
		if(isEmpty_(stack))
		{
			return NULL;
		}
		else
		{
			PNode node = stack->head;
			stack->head = node->next;
			stack->size--;
			return node;
		}
	}
}

test.c 

/*************************************************************************
	> File Name: test.c
	> Author: bairutai
	> Mail: bairutai@aliyun.com 
	> Created Time: 2015年09月22日 星期二 16时11分26秒
 ************************************************************************/

#include<stdio.h>
#include"BiTree.h"
main()
{
	Node* n1 = MakeNode(10,NULL,NULL);
	Node* n2 = MakeNode(20,NULL,NULL);
	Node* n3 = MakeNode(30,n1,n2);
	Node* n4 = MakeNode(40,NULL,NULL);
	Node* n5 = MakeNode(50,NULL,NULL);
	Node* n6 = MakeNode(60,n4,n5);
	Node* root = MakeNode(70,n3,n6);
	BiTree *biTree = initBiTree(&root);
	printf("the depth is %d \n", getDepth(*biTree));
	printf("前序遍历：");
	pre_order(root);
	printf("\n");
	printf("中序遍历：");
	mid_order(root);
	printf("\n");
	printf("后序遍历：");
	after_order(root);
	printf("\n");
	printf("非递归前序遍历：");
	pre_order_(root);
	printf("\n");
	printf("非递归中序遍历：");
	mid_order_(root);
	printf("\n");
	printf("非递归后序遍历：");
	after_order_(root);
	printf("\n");
	DestoryBiTree(biTree);
	if(isEmpty(*biTree)){
		printf("二叉树为空\n");
	}
	else{
		printf("the address of biTree is %p\n", biTree);
	}
}

结果 

the depth is 3 
前序遍历：70 30 10 20 60 40 50 
中序遍历：10 30 20 70 40 60 50 
后序遍历：10 20 30 40 50 60 70 
非递归前序遍历：70 30 10 20 60 40 50 
非递归中序遍历：10 30 20 70 40 60 50 
非递归后序遍历：10 20 30 40 50 60 70 
destory  10 
destory  20 
destory  30 
destory  40 
destory  50 
destory  60 
destory  70 
二叉树为空



标签：

相关文章