数据结构--二叉树遍历

目录

1.介绍

（1）前序遍历

（2）定义结构体

（3）前序遍历实现

（4）中序遍历实现

（5）二叉树的节点个数

（6）二叉树树叶节点个数

（7）二叉树的高度

（8）二叉树节点的开辟

（9）建立一个测试二叉树

（10）测试二叉树相关函数的功能

（11）第k层的数据个数

（12）二叉树里面查找节点

---

1.介绍

（1）前序遍历

前序遍历就是针对于树根而言的，就是这个树的树根是先被我们遍历的，因为这个二叉树里面划分为树根，左子树和右子树，这个前中后表示的就是这三个里面的树根的访问顺序，树根先被访问就是前序遍历，树根是第二个被访问的就是中序遍历，最后被访问到就是后序遍历；

（2）定义结构体

下面看一下这个前序遍历的具体实现；

首先我们要进行这个结构体的定义，这个结构体就是表示的每一个节点，具体来讲就是包括这个节点数据，节点的左节点，节点的右节点；

（3）前序遍历实现

这个代码里面的N表示的就是这个位置的节点是不存在的，因为不是所有的节点都存在，就是标准情况下，一个节点应该是有两个子节点的，一个左节点，一个右节点，但是不可避免的有的节点是没有左节点，或者是没有右节点的，这个时候我们不会不打印任何数据，而是使用N代替说明这个位置的节点不存在；

（4）中序遍历实现

这个就是先访问左边的节点，再访问根节点，最后访问右边的节点，没有字节点的就会打印N代替

（5）二叉树的节点个数

这个地方是使用的递归的方法，如果自己没有根节点，说明这个二叉树的节点的个数是0，否则就是用递归去进行节点个数的计算；

（6）二叉树树叶节点个数

这个也是分为有树根节点，没有树根节点，以及正常的使用递归进行计算的情况，这个时候使用递归进行计算就不需要加上1，因为上面的加1表示这个要加上树根节点，但是这个地方计算的是树叶节点，所以不需要加上1；

（7）二叉树的高度

这个地方是使用这个leftheight表示这个左子树的高度，rightheight表示这个右子树的高度，这个地方其实是可以直接写到返回值里面的，但是这个地方使用的是递归，如果不进行这个临时变量的定义而是直接写到这个return里面，这个调用的次数就会增加，放到oj里面运行就不会通过，显示这个运行时间过长，我们定义两个中间变量就可以去解决这个问题；

（8）二叉树节点的开辟

使用malloc函数开辟内存空间，需要包含对应的文件stdlib.h

（9）建立一个测试二叉树

调用上面的buynode函数进行这个节点开辟，并建立不同的节点之间的连接关系，最后返回第一个节点；

（10）测试二叉树相关函数的功能

打印输出这个二叉树的高度，节点个数，树叶节点个数进行这个功能的测试；

（11）第k层的数据个数

使用递归，把下一层即k-1层的左子树和右子树节点数量的和作为这个返回值；

（12）二叉树里面查找节点

这个里面就是查找某一个特定的节点，这个节点作为返回值，我们定义两个临时变量作为左子树和右子树的返回值，如果左子树找到这个节点，我们就可以直接返回，否则的话，我们就需要去右子树去查找，找到这个节点后作为返回值，如果左子树，右子树找不到的话就返回NULL；

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
typedef int btdatatype;
typedef struct binarytreenode
{
	btdatatype data;
	struct binarytree* left;
	struct binarytree* right;
}btnode;
 
void prevorder(btnode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->data);
	prevorder(root->left);
	prevorder(root->right);
}
 
void inorder(btnode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	inorder(root->left);
	printf("%d ", root->data);
	inorder(root->right);
}
 
 
int treesize(btnode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return treesize(root->left) + treesize(root->right) + 1;
}
 
int leafsize(btnode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return leafsize(root->left) + leafsize(root->right);
}
 
int heightsize(btnode* root)
{
	if (root == NULL)
		return 0;
	int leftheight = heightsize(root->left);
	int rightheight = heightsize(root->right);
	return leftheight > rightheight ? heightsize(root->left) + 1 : heightsize(root->right) + 1;
}
 
int treesizek(btnode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return treesizek(root->left, k - 1) + treesizek(root->right, k - 1);
}
 
//二叉树里面查找指定的节点
btnode* treefind(btnode* root, btdatatype x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	btnode* ret1 = treefind(root->left, x);
	if (ret1)
	{
		return ret1;
	}
	btnode* ret2 = treefind(root->right, x);
	if (ret2)
	{
		return ret2;
	}
	return NULL;
}
 
btnode* buynode(int x)
{
	btnode* node = (btnode*)malloc(sizeof(btnode));
	if (node == NULL)
	{
		perror("malloc fail");
		return;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
}
 
 
 
btnode* creattree()
{
	btnode* node1 = buynode(1);
	btnode* node2 = buynode(2);
	btnode* node3 = buynode(3);
	btnode* node4 = buynode(4);
	btnode* node5 = buynode(5);
	btnode* node6 = buynode(6);
 
 
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
 
	return node1;
}
int main()
{
	btnode* root = creattree();
	prevorder(root);
	printf("\n");
 
 
	inorder(root);
	printf("\n");
 
	int size = treesize(root);
	printf("treesize：%d\n", size);
 
	int size2 = leafsize(root);
	printf("leafsize：%d\n", size2);
 
	int size3 = heightsize(root);
	printf("heightsize：%d\n", size3);
 
	int size4 = treesizek(root,3);
	printf("treesizek：%d\n", size4);
	return 0;
}