数据结构之二叉树的基本实现

在我们之前已经了解的堆这样的完全二叉树的实现，也对树型结构有了一些了解，那么今天我们来看看二叉树的一些性质。

因为二叉树是一种每个节点至多只有两个子树（即二叉树的每个节点的度不大于2），并且二叉树的子树有左右之分，其次序不能任意颠倒，因此它的结构也是比较独特的。

目录

1.二叉树的结构定义

2.节点构造

3.节点生成树

3.二叉树的遍历方式

先序遍历：

中序遍历：

后序遍历

层次遍历：

4.求树的所有节点个数

5.求叶子节点个数

6.求二叉树树深度

7.二叉树第K层节点个数

8.返回值为x的节点

---

1.二叉树的结构定义

二叉树是一种每个节点至多只有两个子树（即二叉树的每个节点的度不大于2），并且二叉树的子树有左右之分，其次序不能任意颠倒。

//定义树的节点
typedef int DATAtype;
typedef struct TreeNode
{
	DATAtype data;
	struct TreeNode* leftchild;
	struct TreeNode* rightchild;
}BTnode;

2.节点构造

简单的节点构造，如同链表的结点，不同的是这里有两个节点表示左孩子与右孩子。

//构造树的节点
BTnode* CreateNode(DATAtype x)
{
	BTnode* newnode = (BTnode*)malloc(sizeof(BTnode));
	if (newnode == NULL)
	{
		perror("malloc fali");
		return NULL;
	}
	newnode->data = x;
	newnode->leftchild = NULL;
	newnode->rightchild = NULL;
	return newnode;
}

3.节点生成树

我们是通过链接节点之间形成树的逻辑关系，这里的树如图：

 先链接了六个节点，之后又添加了一个节点

//利用节点生成一个树
BTnode* TreeCreat()
{
	BTnode* node1=CreateNode(1);
	BTnode* node2=CreateNode(2);
	BTnode* node3=CreateNode(3);
	BTnode* node4=CreateNode(4);
	BTnode* node5=CreateNode(5);
	BTnode* node6=CreateNode(6);
	BTnode* node7 = CreateNode(6);
	//建立连接关系
	node1->leftchild = node2;
	node1->rightchild = node4;
	node2->leftchild = node3;
	node4->leftchild = node5;
	node4->rightchild = node6;
	node6->leftchild = node7;
	//返回根
	return node1;
}

3.二叉树的遍历方式

二叉树的遍历方式主要有四种，分别是先序遍历、中序遍历、后序遍历和层次遍历。123

先序遍历：

先访问根节点，再访问左子树，最后访问右子树。

//前序遍历
void Preverorder(BTnode*root)
{
	//根 左子树 右子树
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->data);
	Preverorder(root->leftchild);
	Preverorder(root->rightchild);
 
}

中序遍历：

先访问左子树，再访问根节点，最后访问右子树。

void Inorder(BTnode* root)
{
	// 左子树 根  右子树
	if (root == NULL)
	{
		return;
	}
	
	Preverorder(root->leftchild);
	printf("%d ", root->data);
	Preverorder(root->rightchild);
 
}

后序遍历

：先访问左子树，再访问右子树，最后访问根节点。

void Postorder(BTnode* root)
{
	// 左子树 右子树 根 
	if (root == NULL)
	{
		return;
	}
 
	Preverorder(root->leftchild);
	Preverorder(root->rightchild);
	printf("%d ", root->data);
	
}

层次遍历：

按照从上到下、从左到右的顺序依次访问每个节点。

层序遍历我们使用队列实现，思路：先进先出，上一层出队时带下一层节点入队。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"queue.h"
#define CRT_SECURE_NO_WARNINGS 1
 
//定义树的节点
typedef int DATAtype;
typedef struct TreeNode
{
	DATAtype data;
	struct TreeNode* leftchild;
	struct TreeNode* rightchild;
}BTnode;
 
//构造树的节点
BTnode* CreateNode(DATAtype x)
{
	BTnode* newnode = (BTnode*)malloc(sizeof(BTnode));
	if (newnode == NULL)
	{
		perror("malloc fali");
		return NULL;
	}
	newnode->data = x;
	newnode->leftchild = NULL;
	newnode->rightchild = NULL;
	return newnode;
}
//利用节点生成一个树
BTnode* TreeCreat()
{
	BTnode* node1=CreateNode(1);
	BTnode* node2=CreateNode(2);
	BTnode* node3=CreateNode(3);
	BTnode* node4=CreateNode(4);
	BTnode* node5=CreateNode(5);
	BTnode* node6=CreateNode(6);
	BTnode* node7 = CreateNode(6);
	//建立连接关系
	node1->leftchild = node2;
	node1->rightchild = node4;
	node2->leftchild = node3;
	node4->leftchild = node5;
	node4->rightchild = node6;
	node6->leftchild = node7;
	//返回根
	return node1;
}

 层序遍历：

//层序遍历
void leverorder(BTnode* root)
{
	LTnode p;
	Queueinit(&p);
	Queuedestroy(&p);
	//先入根节点
	if (root)
	{
		LTpush(&p, root);
	}
	while (!LTempety(&p))
	{
		//队中数据全是树节点指针型
		BTnode* front = LTfront(&p);
			LTpop(&p);//出队头
 
			printf("%d", front->data);
         //判断孩子节点
			if (front->leftchild)
			{
				LTpush(&p, front->leftchild);
			}
			if (front->rightchild)
			{
				LTpush(&p, front->rightchild);
			}
	}
	printf("\n");
}

4.求树的所有节点个数

这里有两种方法，除了定义全局变量利用计数的方法来计算树的节点个数，但还需注意全局变量使用后需置零，其次我们也是利用递归的返回值累加计算出节点个数。

//求树的所有节点个数
int size = 0;
int Binarytreesize(BTnode* root)
{
	/*分治思想  从左子树到右子树再到根*/
	if (root == NULL)
	{
		return 0;
	}
	return (1 + Binarytreesize(root->leftchild) + Binarytreesize(root->rightchild));
 
 
	/*if (root)
	{
		size++;
		Binarytreesize(root->leftchild);
		Binarytreesize(root->rightchild);
	}
	return size;*/
}

5.求叶子节点个数

寻找递归条件，叶子节点没有左右孩子，否则就不返回一，符合条件的返回一相加。注意递归中返回值的设定。

//求叶子节点个数
int BTreeleavessize(BTnode* root)
{
	//自己的左子树与左右子树为空
	if (root == NULL)
	{
		return 0;
	}
	if (root->leftchild == NULL && root->rightchild == NULL)
	{
		return 1;
	}
	else
	{
		return BTreeleavessize(root->leftchild) + BTreeleavessize(root->rightchild);
	}
}

6.求二叉树树深度

分治思想，两边同时遍历，每有一层加一，左孩子层数与右孩子层数中较大的那个就是深度。

//求二叉树的深度
int BTreeheight(BTnode* root)
{
	//左右同时遍历，选最大的哪一个
	if (root == NULL)
	{
		return 0;
	}
	//这里注意用变量保存一下左 右子树的数目
	int left = BTreeheight(root->leftchild) + 1;
	int right= BTreeheight(root->rightchild) + 1;
	if (left > right)
	{
		return left;
	}
	else
	{
		return right;
	}
}

7.二叉树第K层节点个数

这里的递归主要是找的第k层，利用k==1作为递归返回条件。

//二叉树第k层结点的个数
int BTree_knumber(BTnode* root,int k)
{
	//分情况讨论
	if (root == NULL)
	{
		return 0;
	}
	if (k==1)
	{
		return 1;
	}
 
	return  BTree_knumber(root->leftchild, k - 1) +
			BTree_knumber(root->rightchild, k - 1);
 
	
	
}

8.返回值为x的节点

这里的难度在与返回值，我们知道在递归里面函数返回值不能直接返回，我们需要判断，对于返回值是需要我们好好检查的，在这里，我们从根，左孩子，右孩子的顺序逐个判断，对于左右孩子并保存返回值，来确定是当前节点。

//返回为x的树节点
BTnode* BTreenode(BTnode* root, DATAtype x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	
	BTnode* left = BTreenode(root->leftchild,x);
	
	if (left->data==x)
	{
		return left;
	}
	BTnode* right = BTreenode(root->rightchild,x);
	if (right->data==x)
	{
		return right;
	}
	return NULL;
}

一些测试用例：

int main()
{
	BTnode* root = TreeCreat();
	/*Preverorder(root);
	printf("\n");
	Inorder(root);
	printf("\n");
	Postorder(root);*/
	//Binarytreesize(root);
	// BTreeleavessize(root);//BTreeheight(root);
	int x = BTree_knumber(root, 2);
 
	printf("%d ", BTreenode(root, 2)->data);
	//printf("%d", x);
	return 0;
}