前面完全二叉树适合存放数据,又因为它在内存中连续存储,因此用顺序表来实现它,并介绍了堆排序及TOP-K问题。
今天我们了解一下二叉树的遍历问题,并完成几道二叉树基础练习
目录
二叉树的遍历
先序
访问顺序:
图示:
中序
访问顺序:
图示:
后序
访问顺序:
图示:
手动构建链式二叉树
定义
创建节点
创建二叉树
前序遍历
中序遍历
后序遍历
练习
求二叉树节点树
求二叉树叶子节点个数
第k层节点数
二叉树深度
二叉树查找值为x的节点
二叉树的遍历
二叉树的遍历有:前序/中序/后序的递归结构遍历:
1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之间。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
以下面二叉树为例,进行先序,中序,后序遍历:
先序
分析:从根节点开始,先访问根,再访问左子树(左子树中先访问根节点,在访问左子树和右子 树),最后访问右子树(先访问根节点,在访问左子树和右子树)
访问顺序:
先访问树tree根1,再访问tree左子树L1:
访问L1根2,再访问其左子树Ll2:
访问Ll2根3,再访问其左子树:左子树为空,访问其右子树,右子树为空,返回上一个子树L1;
此时L1左子树访问完毕,访问L1右子树NULL,为空返回上一个树tree;
此时tree根和左子树访问完毕,访问tree右子树R1:
访问R1根4,再访问R1左子树Rl1:
访问Rl1根5,再访问Rl1左子树和右子树NULL,返回上一个树R1;
此时,R1左子树Rl1访问完毕,接着访问R1右子树Rr1:
访问Rr1根6,再访问Rr1左右子树NULL,返回上一个树R1;
此时R1根和左右子树访问完毕,返回上一个树tree;
此时tree的根和左子树访问完毕,及整个树访问完毕。
图示:
中序
分析:即先访问左子树,左子树访问完毕后再访问根节点,根节点访问完后,最后访问右子树。左子树和右子树中也是先访问左子树,再根,最后右子树。
访问顺序:
从tree根开始,先访问其左子树L1:
左子树L1不为空,访问L1左子树Ll2:
左子树Ll2不为空,访问Ll2左子树:
左子树为空,访问Ll2根3,再访问Ll2的右节点,右节点为空,返回子树L1;
子树L1的左子树访问完毕,访问L1的根2,再访问L1的右子树,为空,返回树tree;
tree的左子树访问完毕,访问tree根1,接着访问tree右子树R1:
右子树R1不为空,访问R1左子树Rl1:
Rl1不为空,访问Rl1左子树,左子树为空,访问Rl1根5,再访问其右子树:
右子树为空,返回上一个树R1;
R1左子树访问完毕,访问其根4,接着访问其右子树Rr1:
Rr1不为空,访问其左子树,左子树为空,访问Rr1根6,再访问其右子树为空,返回R1;
此时tree的左子树,根,和右子树都访问完毕。
图示:
后序
分析:先访问左子树(左子树中也是左子树,右子树,根),再访问右子树(右子树中也是左子树,右子树,根),最后访问根节点。
访问顺序:
先访问tree,不为空,访问其左子树L1,L1不为空,访问其左子树Ll2;
Ll2不为空,访问其左子树,为空;访问其右子树,为空;访问其根3,返回上一个树L1;
L1左子树访问完毕,访问其右子树,为空;访问其根2,返回上一个树tree;
tree的左子树访问完毕,访问其右子树R1,R1不为空,访问其左子树Rl1;
Rl1不为空,访问其左子树,为空;访问其右子树,为空,访问其根5,返回上一个树R1;
R1左子树访问完毕,访问其右子树Rr1,Rr1不为空,访问其左子树;
Rr1左子树为空,访问其右子树,为空,访问其根6,返回上一个树R1;
此时R1左子树右子树访问完毕,访问其根4,放回上一个树tree;
此时tree的左右子树访问完毕,访问其根1;整个树访问完毕。
图示:
手动构建链式二叉树
不难发现,上述遍历时中途总会返回上一层树,已经用到了递归思想,这里我们手动实现一个简单的链式二叉树,完成我们的前序,中序,后序的遍历。
定义
定义每个节点由数据,左子树地址和右子树地址组成
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType data; //数据
struct BinaryTreeNode* left; //左子树地址
struct BinaryTreeNode* right; //右子树地址
}BTNode;
创建节点
将固定的数据放入创建的节点中,左右子树指针置空
BTNode* BuyNode(BTDataType x)
{
BTNode* root = (BTNode*)malloc(sizeof(BTNode));
root->data = x;
root->left = NULL;
root->right = NULL;
return root;
}
创建二叉树
手动创建节点,并将左右子树指针指向固定的位置,以上述二叉树为例:
//手动创建
BTNode* CreatBinaryTree()
{
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;
}
前序遍历
依照我们对前序遍历的顺序分析:根,左子树,右子树,编写前序代码:
// 二叉树前序遍历
void PreOrder(BTNode* root)
{
if (root==NULL)
{
return;
}
printf("%d ",root->data);
PreOrder(root->left);
PreOrder(root->right);
}
中序遍历
// 二叉树中序遍历
void InOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
InOrder(root->left);
printf("%d ", root->data);
InOrder(root->right);
}
后序遍历
// 二叉树后序遍历
void PostOrder(BTNode* root)
{
if (root == NULL)
{
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->data);
}
练习
求二叉树节点树
方法一:前序中序后序时添加一个计数变量(变量为全局或者静态,防止递归时计数重置)
缺点:重复调用时计数会累加,每次调用时须将count重新置0;
//定义全局或者静态变量 //多次调用会累加 int count = 0; int BTreeSize(BTNode* root) { if (root == NULL) return; ++count; BTreeSize(root->left); BTreeSize(root->right); return count; }
方法二:遍历+计数(遍历时将遍历地址传过去)
//遍历+计数 //将变量地址传过去,计数---思想最优 void BTreeSize(BTNode* root,int* count) { if (root == NULL) return; ++(*count); BTreeSize(root->left,count); BTreeSize(root->right,count); }
方法三:递归--分治思想
当根为空时,返回0,左子树节点个数+右子树节点个数+1(根节点本身)
//递归--分治思想--节点个数 int BTreeSize(BTNode* root) { return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1; }
求二叉树叶子节点个数
二叉树叶子节点数 = 左子树叶子节点数 + 右子树节点数
叶子节点:左子树和右子树为空的节点
//叶子节点个数 int BTreeLeafSize(BTNode* root) { if (root==NULL) { return 0; } if (root->left == NULL&&root->right==NULL) { return 1; } return BTreeLeafSize(root->left) + BTreeLeafSize(root->right); }
第k层节点数
求tree的第三层节点数
即L1和R1的第二层节点数之和
即Ll1、Rl1和Rr1第一层节点数之和
当k=1时,返回1即可
//第k层节点个数 int BTreeLeveSize(BTNode* root,int k) { assert(k>=1); if (root==NULL) { return 0; } if (k == 1) { return 1; } return BTreeLeveSize(root->left, k - 1) + BTreeLeveSize(root->right, k - 1);
二叉树深度
二叉树的深度 = 左子树和右子树中最大深度度+1
需要比较左右子树高度,判断返回哪一个
//二叉树深度 int BTreeDepth(BTNode* root) { if (root==NULL) { return 0; } int leftdepth = BTreeDepth(root->left); int rightdepth = BTreeDepth(root->right); return leftdepth >rightdepth ? leftdepth + 1 : rightdepth + 1; }
二叉树查找值为x的节点
判断根是否为要找的节点,是则返回节点地址
不是则进左子树中去找,找到返回节点地址,找不到返回空
再进右子树取找,找到返回节点地址,找不到返回空文章来源:https://www.toymoban.com/news/detail-488384.html
// 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root==NULL) { return NULL; } if (root->data == x) return root; if (BinaryTreeFind(root->left, x)) return BinaryTreeFind(root->left,x); if (BinaryTreeFind(root->right, x)) return BinaryTreeFind(root->right, x); return NULL; }
文章来源地址https://www.toymoban.com/news/detail-488384.html
到了这里,关于二叉树的遍历+基础练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!