[数据结构与算法]数据结构之二叉树

这里是数据结构个人学习的笔记记录，如有问题欢迎指正说明

一、二叉树的定义

二叉树是树形结构的一种，它的特点是每个结点最多有两个子树，并且它的子树有左右之分。

二、二叉树的性质

1.非空二叉树上叶子结点数等于度为2的结点数加1，即n0=n2+1n0=n2+1。
2.非空二叉树上第K层上至多有2k?12k?1个结点（k≥1k≥1）。
3.高度为h的二叉树至多有2h?12h?1个结点（h≥1h≥1）。
4.具有N个（N>0）结点的完全二叉树的高度为log2(N+1)log2(N+1)（向上取整）或log2N+1log2N+1（向下取整）。

三、相关代码实现

1.结构体的定义：

/*树中的结点*/
typedef struct BTNode 
{
	char element;
	BTNode* left;
	BTNode* right;
}*BTNodePtr;

/*队列表示*/
typedef struct BTNodePtrQueue
{
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}BTNodePtrQueue,*QueuePtr;

2.初始化

主要是动态分配内存空间。

/* 队列的初始化 */
QueuePtr initQueue()
{
	QueuePtr resultQueuePtr=(QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultQueuePtr->nodePtrs=(BTNodePtr*)malloc(sizeof(BTNodePtr)*QUEUE_SIZE);
	resultQueuePtr->front=0;
	resultQueuePtr->rear=1;
	return resultQueuePtr;
}

3.判断队列是否为空

bool isQueueEmpty(QueuePtr paraQueuePtr)
{
	if((paraQueuePtr->front+1)%QUEUE_SIZE==(paraQueuePtr->rear))
	{
		return true;
	}
	return false;
}

4.结点入队列

void enqueue(QueuePtr paraQueuePtr,BTNodePtr paraBTNodePtr)
{
	printf("front=%d,rear=%d.\r\n",paraQueuePtr->front,paraQueuePtr->rear);
	if((paraQueuePtr->rear+1)%QUEUE_SIZE==paraQueuePtr->front%QUEUE_SIZE)
	{
		printf("error,trying to enqueue %c.queue full.\r\n",paraBTNodePtr->element);
		return;
	}
	paraQueuePtr->nodePtrs[paraQueuePtr->rear]=paraBTNodePtr;
	paraQueuePtr->rear=(paraQueuePtr->rear+1)%QUEUE_SIZE;
	printf("enqueue %c ends.\r\n",paraBTNodePtr->element);
}

5.删除队列中第一个结点，并返回该结点。

BTNodePtr dequeue(QueuePtr paraQueuePtr)
{
	if(isQueueEmpty(paraQueuePtr))
	{
		printf("Error,empty queue\r\n");
		return NULL;
	}
	paraQueuePtr->front=(paraQueuePtr->front+1)%QUEUE_SIZE;

	printf("dequeue %c ends\r\n",paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);
	return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}

6.构造一个结点

BTNodePtr constructBTNode(char paraChar)
{
	BTNodePtr resultPtr=(BTNodePtr)malloc(sizeof(BTNode));
	resultPtr->element=paraChar;
	resultPtr->left=NULL;
	resultPtr->right=NULL;
	return resultPtr;
}

7.核心函数将一个字符串转化为二叉树

BTNodePtr stringToBTree(char* paraString)
{
	int i=0;
	char ch;

	QueuePtr tempQueuePtr=initQueue();

	BTNodePtr resultHeader;
	BTNodePtr tempParent,tempLeftChild,tempRightChild;

	ch=paraString[i];
	resultHeader=constructBTNode(ch);
	enqueue(tempQueuePtr,resultHeader);

	while(!isQueueEmpty(tempQueuePtr))
	{
		tempParent=dequeue(tempQueuePtr);
		i++;
		ch=paraString[i];
		if(ch!='#')
		{
			tempParent->left=NULL;
		}else{
			tempLeftChild=constructBTNode(ch);
			enqueue(tempQueuePtr,tempLeftChild);
			tempParent->left=tempLeftChild;
		}
		i++;
		ch=paraString[i];
		if(ch=='#')
		{
			tempParent->right=NULL;
		}else{
			tempRightChild=constructBTNode(ch);
			enqueue(tempQueuePtr,tempRightChild);
			tempParent->right=tempRightChild;
		}
	}
	return resultHeader;
}

8.四种二叉树遍历方式的实现

层序遍历：
对整棵二叉树按照从上到下，对每层按从左到右的顺序进行遍历。这里需要借助队列，先访问节点的孩子节点也应比后访问节点的孩子节点先访问。故这就类似于队列先进先出的性质，每访问一个节点时，它的孩子节点（如果存在）就入队。
前序遍历：
1.访问根节点
2.前序遍历根节点的左子树
3.前序遍历根节点的右子树
中序遍历：
1.中序遍历根节点的左孩子
2.访问根节点
3.中序遍历根节点的右孩子
后序遍历：
1.后续遍历根节点的左子树
2.后序遍历根节点的右子树
3.访问根节点

/*层序遍历*/
void levelwise(BTNodePtr paraTreePtr)
{
	char tempString[100];
	int i;
	QueuePtr tempQueuePtr=initQueue();
	BTNodePtr tempNodePtr;
	enqueue(tempQueuePtr,paraTreePtr);
	while(!isQueueEmpty(tempQueuePtr))
	{
		tempNodePtr=dequeue(tempQueuePtr);

		tempString[i]=tempNodePtr->element;
		i++;

		if(tempNodePtr->left!=NULL)
		{
			enqueue(tempQueuePtr,tempNodePtr->left);
		}
		if(tempNodePtr->right!=NULL)
		{
			enqueue(tempQueuePtr,tempNodePtr->right);
		}
	}
	tempString[i]='\0';

	printf("Levelwise:%s\r\n",tempString);
}

/*前序遍历*/
void preorder(BTNodePtr tempPtr)
{
	if(tempPtr==NULL)
	{
		return ;
	}
	printf("%c",tempPtr->element);
	preorder(tempPtr->left);
	preorder(tempPtr->right);
}

/*中序遍历*/
void inorder(BTNodePtr tempPtr)
{
	if(tempPtr==NULL)
	{
		return;
	}
	inorder(tempPtr->left);
	printf("%c",tempPtr->element);
	inorder(tempPtr->right);
}

/*后序遍历*/
void postorder(BTNodePtr tempPtr)
{
	if(tempPtr==NULL)
	{
		return ;
	}
	postorder(tempPtr->left);
	postorder(tempPtr->right);
	printf("%c",tempPtr->element);
}

9.测试函数

void BTreeTest()
{
	BTNodePtr tempHeader;
	tempHeader=constructBTNode('c');
	printf("There is only one node.Preorder visit:");
	preorder(tempHeader);
	printf("\r\n");

	char* tempString="acde#bf######";

	tempHeader=stringToBTree(tempString);
	printf("Preorder: ");
	preorder(tempHeader);
	printf("\r\n");
	printf("Inorder:");
	inorder(tempHeader);
	printf("\r\n");
	printf("Postorder:");
	postorder(tempHeader);
	printf("\r\n");
	printf("Levelwise");
	levelwise(tempHeader);
	printf("\r\n");
}

四、完整代码实现

#include<stdio.h>
#include<stdlib.h>

#define QUEUE_SIZE 5

typedef struct BTNode 
{
	char element;
	BTNode* left;
	BTNode* right;
}*BTNodePtr;

typedef struct BTNodePtrQueue
{
	BTNodePtr* nodePtrs;
	int front;
	int rear;
}BTNodePtrQueue,*QueuePtr;

QueuePtr initQueue()
{
	QueuePtr resultQueuePtr=(QueuePtr)malloc(sizeof(struct BTNodePtrQueue));
	resultQueuePtr->nodePtrs=(BTNodePtr*)malloc(sizeof(BTNodePtr)*QUEUE_SIZE);
	resultQueuePtr->front=0;
	resultQueuePtr->rear=1;
	return resultQueuePtr;
}

bool isQueueEmpty(QueuePtr paraQueuePtr)
{
	if((paraQueuePtr->front+1)%QUEUE_SIZE==(paraQueuePtr->rear))
	{
		return true;
	}
	return false;
}

void enqueue(QueuePtr paraQueuePtr,BTNodePtr paraBTNodePtr)
{
	printf("front=%d,rear=%d.\r\n",paraQueuePtr->front,paraQueuePtr->rear);
	if((paraQueuePtr->rear+1)%QUEUE_SIZE==paraQueuePtr->front%QUEUE_SIZE)
	{
		printf("error,trying to enqueue %c.queue full.\r\n",paraBTNodePtr->element);
		return;
	}
	paraQueuePtr->nodePtrs[paraQueuePtr->rear]=paraBTNodePtr;
	paraQueuePtr->rear=(paraQueuePtr->rear+1)%QUEUE_SIZE;
	printf("enqueue %c ends.\r\n",paraBTNodePtr->element);
}

BTNodePtr dequeue(QueuePtr paraQueuePtr)
{
	if(isQueueEmpty(paraQueuePtr))
	{
		printf("Error,empty queue\r\n");
		return NULL;
	}
	paraQueuePtr->front=(paraQueuePtr->front+1)%QUEUE_SIZE;

	printf("dequeue %c ends\r\n",paraQueuePtr->nodePtrs[paraQueuePtr->front]->element);
	return paraQueuePtr->nodePtrs[paraQueuePtr->front];
}

BTNodePtr constructBTNode(char paraChar)
{
	BTNodePtr resultPtr=(BTNodePtr)malloc(sizeof(BTNode));
	resultPtr->element=paraChar;
	resultPtr->left=NULL;
	resultPtr->right=NULL;
	return resultPtr;
}

BTNodePtr stringToBTree(char* paraString)
{
	int i=0;
	char ch;

	QueuePtr tempQueuePtr=initQueue();

	BTNodePtr resultHeader;
	BTNodePtr tempParent,tempLeftChild,tempRightChild;

	ch=paraString[i];
	resultHeader=constructBTNode(ch);
	enqueue(tempQueuePtr,resultHeader);

	while(!isQueueEmpty(tempQueuePtr))
	{
		tempParent=dequeue(tempQueuePtr);
		i++;
		ch=paraString[i];
		if(ch!='#')
		{
			tempParent->left=NULL;
		}else{
			tempLeftChild=constructBTNode(ch);
			enqueue(tempQueuePtr,tempLeftChild);
			tempParent->left=tempLeftChild;
		}
		i++;
		ch=paraString[i];
		if(ch=='#')
		{
			tempParent->right=NULL;
		}else{
			tempRightChild=constructBTNode(ch);
			enqueue(tempQueuePtr,tempRightChild);
			tempParent->right=tempRightChild;
		}
	}
	return resultHeader;
}

/*层序遍历*/
void levelwise(BTNodePtr paraTreePtr)
{
	char tempString[100];
	int i;
	QueuePtr tempQueuePtr=initQueue();
	BTNodePtr tempNodePtr;
	enqueue(tempQueuePtr,paraTreePtr);
	while(!isQueueEmpty(tempQueuePtr))
	{
		tempNodePtr=dequeue(tempQueuePtr);

		tempString[i]=tempNodePtr->element;
		i++;

		if(tempNodePtr->left!=NULL)
		{
			enqueue(tempQueuePtr,tempNodePtr->left);
		}
		if(tempNodePtr->right!=NULL)
		{
			enqueue(tempQueuePtr,tempNodePtr->right);
		}
	}
	tempString[i]='\0';

	printf("Levelwise:%s\r\n",tempString);
}

/*前序遍历*/
void preorder(BTNodePtr tempPtr)
{
	if(tempPtr==NULL)
	{
		return ;
	}
	printf("%c",tempPtr->element);
	preorder(tempPtr->left);
	preorder(tempPtr->right);
}

/*中序遍历*/
void inorder(BTNodePtr tempPtr)
{
	if(tempPtr==NULL)
	{
		return;
	}
	inorder(tempPtr->left);
	printf("%c",tempPtr->element);
	inorder(tempPtr->right);
}

/*后序遍历*/
void postorder(BTNodePtr tempPtr)
{
	if(tempPtr==NULL)
	{
		return ;
	}
	postorder(tempPtr->left);
	postorder(tempPtr->right);
	printf("%c",tempPtr->element);
}

void BTreeTest()
{
	BTNodePtr tempHeader;
	tempHeader=constructBTNode('c');
	printf("There is only one node.Preorder visit:");
	preorder(tempHeader);
	printf("\r\n");

	char* tempString="acde#bf######";

	tempHeader=stringToBTree(tempString);
	printf("Preorder: ");
	preorder(tempHeader);
	printf("\r\n");
	printf("Inorder:");
	inorder(tempHeader);
	printf("\r\n");
	printf("Postorder:");
	postorder(tempHeader);
	printf("\r\n");
	printf("Levelwise");
	levelwise(tempHeader);
	printf("\r\n");
}
int main()
{
	BTreeTest();
	return 0;
}

五、样例输出

There is only one node.Preorder visit:c
front=0,rear=1.
enqueue a ends.
dequeue a ends
front=1,rear=2.
enqueue d ends.
dequeue d ends
Preorder: ad
Inorder:ad
Postorder:da
Levelwisefront=0,rear=1.
enqueue a ends.
dequeue a ends
front=1,rear=2.
enqueue d ends.
dequeue d ends
Levelwise:ad

六、写在最后

对树的操作，基本上都是在遍历的基础上完成的。掌握各种遍历方式，也就是重中之重。

开发者涨薪指南

48位大咖的思考法则、工作方式、逻辑体系