C语言：二叉树的相关操作

ゝ一世哀愁。 2022-08-05 08:59 179阅读 0赞

/*
    	二叉树的例子：二叉链建立表结构
    	1.二叉树的遍历建立
    	2.二叉树的三种递归遍历
    	3.非递归（栈结构）的中序遍历
    	4.层序遍历（队列）
    */
    
    # include <stdio.h>
    # include <malloc.h>
    # include <stdlib.h>
    
    //二叉树节点
    typedef struct Node
    {
    	int data;   //数据域  
    	struct Node * Lchild;   //指向左孩子
    	struct Node * Rchild;   //指向右孩子
    }BiNode, * BiTree;
    
    //定义栈,用非递归的方法中序遍历二叉树
    typedef struct stack
    {
    	int top;  //指向栈顶，有效元素的上一个位置
    	BiTree * ele;  //栈存储空间的基址,存储二叉树节点
    }Stack;
    
    //以树节点为元素的链表节点
    typedef struct node
    {
    	BiTree data;
    	struct node * pNext;
    }NODE, * PNODE;
    
    //定义队列，层序遍历
    typedef struct queue
    {
    	PNODE front;  //对首
    	PNODE rear;  //队尾	
    }Queue;
    
    
    void inital(BiTree &T);
    void creat(BiTree &T);
    int BiTreeDepth(BiTree T);
    void InOrderTraverse(BiTree T);
    void PreOrderTraverse(BiTree T);
    void PostOrderTraverse(BiTree T);
    
    void inOrder(BiTree T);
    void initalStack(Stack &s);
    void push(Stack &S, BiTree t);
    void pop(Stack &S, BiTree &t);
    bool empty_stack(Stack S);
    bool getTop(Stack S, BiTree &p);
    void visit(BiTree p);
    
    void levelTraverse(BiTree T);
    void initalQueue(Queue &Q);
    void inQueue(Queue &Q, BiTree T);
    void outQueue(Queue &Q, PNODE &p);
    bool empty_queue(Queue Q);
    void visit_pnode(PNODE p);
    
    int main(void)
    {
    	BiTree T;
    	inital(T);  //二叉树初始化
    
    	//创建二叉树
    	creat(T);  
    
    	//求二叉树的深度
    	int deep = BiTreeDepth(T);
    	printf("树T的深度为：%d\n", deep);
    
    	//中序遍历二叉树
    	printf("中序遍历：");
    	InOrderTraverse(T);
    	printf("\n");
    
    	printf("前序遍历：");
    	PreOrderTraverse(T);
    	printf("\n");
    
    	printf("后序遍历：");
    	PostOrderTraverse(T);
    	printf("\n");
    
    	printf("非递归中序遍历：");
    	inOrder(T);
    	printf("\n");
    
    	printf("层序遍历：");
    	levelTraverse(T);
    	printf("\n");
    
    	return 0;
    }
    
    //初始化树
    void inital(BiTree &T)
    {
    	T = NULL;  //根节点为NULL
    }
    
    //创建二叉树
    /*递归的按先序的方法创建二叉树*/
    void creat(BiTree &T)
    {
    	int ch;
    	printf("输入节点的值,0代表空值："); 
    	scanf("%d", &ch);    //输入一个整数值,回车
    
    	if(ch == 0)    //值为0时，不创建节点
    		T = NULL;
    	else            //值不为0时，创建新节点
    	{
    		T = (BiTree)malloc(sizeof(BiNode));
    		if(T == NULL)
    			exit(0);
    
    		T->data = ch;
    		creat(T->Lchild);
    		creat(T->Rchild);
    	}
    	
    	return;
    }
    
    //求二叉树的深度
    int BiTreeDepth(BiTree T)
    {
    	int i, j;
    
    	if(T == NULL)   //程序的出口
    		return 0;
    	else
    	{
    		if(T->Lchild)   //左孩子深度
    		{
    			i = BiTreeDepth(T->Lchild);
    		}
    		else   //为空时，深度为0
    		{
    			i = 0;
    		}
    
    		if(T->Rchild)   //右孩子深度
    		{
    			j = BiTreeDepth(T->Rchild);
    		}
    		else
    		{
    			j = 0;
    		}
    
    		return (i >= j) ? (i+1):(j+1);   //去左右孩子的最大深度
    	}
    }
    
    //中序遍历，左子树，根节点，右子树
    void InOrderTraverse(BiTree T)
    {
    	if(T == NULL)
    		return;
    	else
    	{
    		InOrderTraverse(T->Lchild);  
    		printf("%d ", T->data);
    		InOrderTraverse(T->Rchild);
    	}
    }
    
    //前序遍历，根节点，左子树，右子树
    void PreOrderTraverse(BiTree T)
    {
    	if(T == NULL)
    		return;
    	else
    	{
    		printf("%d ", T->data);
    		PreOrderTraverse(T->Lchild);
    		PreOrderTraverse(T->Rchild);
    	}
    }
    
    //后续遍历，左子树，右子树，根节点
    void PostOrderTraverse(BiTree T)
    {
    	if(T == NULL)
    		return; 
    	else
    	{
    		PostOrderTraverse(T->Lchild);
    		PostOrderTraverse(T->Rchild);
    		printf("%d ", T->data);
    	}
    }
    
    //非递归的中序遍历二叉树
    /*
    	1.所有左孩子入栈
    	2.栈顶元素出栈，并访问
    	3.栈顶元素的右孩子入栈
    */
    void inOrder(BiTree T)
    {
    	Stack S;   //建立栈
    	initalStack(S);  //初始化栈
    
    	BiTree p = NULL;
    
    	//根指针进栈
    	push(S, T);
    
    	while(!empty_stack(S))
    	{
    		//获取栈顶元素,	其左孩子入栈  		
    		while( getTop(S, p) && p != NULL )
    		{
    			push(S, p->Lchild);
    		}
    
    		//最后一个空元素出栈
    		pop(S, p);
    
    		if(!empty_stack(S))
    		{
    			//栈顶左孩子出栈
    			pop(S, p);
    
    			//访问该节点
    			visit(p);
    
    			//右孩子入栈顶 
    			push(S, p->Rchild);
    		}
    	}
    }
    
    //层序遍历
    /*
    	1.利用队列
    	2.首节点入队列，在出队列，左右孩子入队列
    	3.左孩子出队列，其左右孩子在入队列。。。
    */
    
    void levelTraverse(BiTree T)
    {
    	//建立队列
    	Queue Q;
    	PNODE p;
    	
    	//初始化队列
    	initalQueue(Q);
    
    	//根节点入队列
    	inQueue(Q, T);
    
    	while(!empty_queue(Q))  //队列不为空时
    	{
    		//对首元素出队列
    		outQueue(Q, p);
    
    		visit_pnode(p);   //访问p节点
    
    		//对首元素的的左右节点入队列
    		if(p->data->Lchild != NULL)
    			inQueue(Q, p->data->Lchild);
    		if(p->data->Rchild != NULL)
    			inQueue(Q, p->data->Rchild);
    	}
    
    
    }
    
    //初始化栈
    void initalStack(Stack &s)
    {
    	s.top = 0;
    	s.ele = (BiTree*)malloc(sizeof(BiTree) * 10);
    }
    
    //二叉树的节点入栈
    void push(Stack &S, BiTree t)
    {
    	S.ele[S.top] = t;
    	S.top ++;
    }
    
    //二叉树的节点出栈
    void pop(Stack &S, BiTree &t)
    {
    	S.top --;
    	t = S.ele[S.top];
    }
    
    //栈是否空
    bool empty_stack(Stack S)
    {
    	if(S.top == 0)
    		return true;
    	else
    		return false;
    }
    
    //获取栈顶元素，保存在p
    bool getTop(Stack S, BiTree &p)
    {
    	if(!empty_stack(S))  //栈为非空时
    		p = S.ele[S.top-1];
    	else
    		p = NULL;
    
    	return true;
    }
    
    //访问数节点p
    void visit(BiTree p)
    {
    	printf("%d ", p->data);
    }
    
    //初始化队列
    void initalQueue(Queue &Q)
    {
    	Q.front = (PNODE)malloc(sizeof(NODE));  //创建头结点，头指针
    	Q.front->pNext = NULL;    
    	Q.rear = Q.front;   //尾指针
    }
    
    //节点T入队列Q
    void inQueue(Queue &Q, BiTree T)
    {
    	PNODE pNew = (PNODE)malloc(sizeof(NODE));  //建立新节点
    	pNew->data = T;
    	pNew->pNext = NULL;
    
    	Q.rear->pNext = pNew;  //新节点挂在尾节点后面
    	Q.rear = pNew;
    
    }
    
    //判断队列是否为空
    bool empty_queue(Queue Q)
    {
    	if(Q.front->pNext == NULL)
    		return true;
    	else
    		return false;
    }
    
    //元素出队列
    void outQueue(Queue &Q, PNODE &p)
    {
     	p = Q.front->pNext;
    	Q.front ->pNext = p->pNext;
    
    	if(p == Q.rear)  //当最后一个元素出队后，重新把尾节点和头结点连在一起
    		Q.front = Q.rear;
    
    }
    
    //访问链表节点p
    void visit_pnode(PNODE p)
    {
    	printf("%d ", p->data->data);
    }

![Image 1][] ![Image 1][]

[Image 1]: