数据结构--二叉树遍历
目录
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;
}原文地址：https://blog.csdn.net/binhyun/article/details/140413066
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！