百度网站链接,兰州专业网站建设报价,女生适合专业15个,简洁大气的网站简单不先于复杂#xff0c;而是在复杂之后。 文章目录 1. 二叉树链式结构的实现1.1 前置说明1.2 二叉树的遍历1.2.1 前序、中序以及后序遍历1.2.2 层序遍历 1.3 节点个数以及高度等1.4 二叉树基础oj练习1.5 二叉树的创建和销毁 1. 二叉树链式结构的实现
1.1 前置说明 在学习二…简单不先于复杂而是在复杂之后。 文章目录 1. 二叉树链式结构的实现1.1 前置说明1.2 二叉树的遍历1.2.1 前序、中序以及后序遍历1.2.2 层序遍历 1.3 节点个数以及高度等1.4 二叉树基础oj练习1.5 二叉树的创建和销毁 1. 二叉树链式结构的实现
1.1 前置说明 在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。 由于现在所学的内容不够让我们深入掌握二叉树结构为了降低学习成本此处手动快速创建一颗二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时后面的博客再来研究二叉树真正的创建方式。 typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
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;
}注意上述代码并不是创建二叉树的方式真正创建二叉树方式后序博客详细介绍。 在看二叉树基本操作前再来回顾下二叉树的概念二叉树是 空树非空根节点、根节点的左子树、根节点的右子树组成的。 从概念中可以看出二叉树定义是递归式的因此后序基本操作中基本都是按照该概念实现的。 1.2 二叉树的遍历
1.2.1 前序、中序以及后序遍历 学习二叉树结构最简单的方式就是遍历。 所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。 访问节点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其他运算的基础。 按照规则二叉树的遍历有前序/中序/后序的递归结构遍历 前序遍历(Preorder Traversal 亦称先序遍历)-----访问根结点的操作发生在遍历其左右子树之前。中序遍历(Inorder Trabersal)-----访问根结点的操作发生在遍历其左右子树之中(间)。后序遍历Postorder Traversal------访问根结点的操作发生在遍历其左右子树之后。 由于被访问的节点必是某子树的根所以N(Node)、L(Left subtree)和R(Right subtree)又可解释为根、根的左子树和根的右子树。 NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。 // 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);下面主要分析前序递归遍历中序与后序图解类似。 前序遍历递归图解 前序遍历结果1 2 3 4 5 6 中序遍历结果3 2 1 5 4 6 后序遍历结果3 2 5 6 4 1 1.2.2 层序遍历 层序遍历除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。 设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。 // 层序遍历
void LevelOrder(BTNode* root);练习请写出下面的前序/中序/后序/层序遍历 选择题 1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为
A ABDHECFG
B ABCDEFGH
C HDBEAFCG
D HDEBFGCA2.二叉树的先序遍历和中序遍历如下先序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为
A E
B F
C G
D H3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为____。
A adbce
B decab
C debac
D abcde4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出同一层从左到右的序列
为
A FEDCBA
B CBAFED
C DEFCBA
D ABCDEF选择题答案 1.A
2.A
3.D
4.A1.3 节点个数以及高度等 // 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);1.4 二叉树基础oj练习 单值二叉树。检查两颗树是否相同。对称二叉树。二叉树的前序遍历。二叉树中序遍历 。二叉树的后序遍历 。另一颗树的子树。 1.5 二叉树的创建和销毁 二叉树的构建及遍历。 // 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);
