聊城建设工程质量信息网站,北京建设教育协会的网站,给人家做的网站想改怎么改,编程培训机构找极客时间本章将会详细讲解二叉树遍历的四种方式#xff0c;分别为前序遍历、中序遍历、后续遍历和层序遍历。在学习遍历之前#xff0c;会先带大家回顾一下二叉树的基本概念。学习二叉树的基本操作前#xff0c;需要先创建一颗二叉树#xff0c;然后才能学习其相关的基本操作#…本章将会详细讲解二叉树遍历的四种方式分别为前序遍历、中序遍历、后续遍历和层序遍历。在学习遍历之前会先带大家回顾一下二叉树的基本概念。学习二叉树的基本操作前需要先创建一颗二叉树然后才能学习其相关的基本操作考虑到我们刚刚接触二叉树为了能够先易后难地进行讲解我们将暂时手动创建一颗简单的二叉树用来方便大家学习。等二叉树结构了解的差不多后后期我们会带大家研究二叉树地真正的创建方式。1.二叉树概念复习链接比特数据结构与算法第四章_上树和二叉树和堆的概念及结构_GR C的博客-CSDN博客 二叉树是什么① 空树 ② 非空根节点、根节点的左子树与根节点的又子树组成的。解读从概念中我们不难看出二叉树的定义是递归式的。因此后续基本操作中我们基本都是按照该概念来实现的我们可以来看一下我们不去看 A我们来看 A 的左子树把 B 看作为根节点又是颗二叉树。所以我们可以通过采用递归的手法来实现二叉树。2.二叉树定义#define _CRT_SECURE_NO_WARNINGS 1#includestdio.htypedef int BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left; // 记录左节点struct BinaryTreeNode* right; // 记录右节点BTDataType data; // 存储数据
} BTNode;//创建新节点
BTNode* CreateNode(BTDataType x)
{BTNode* new_node (BTNode*)malloc(sizeof(BTNode));if (new_node NULL){printf(malloc failed!\n);exit(-1);}new_node-data x;new_node-left new_node-right NULL;return new_node;
}//手动创建二叉树
BTNode* CreateBinaryTree()
{BTNode* nodeA CreateNode(A);BTNode* nodeB CreateNode(B);BTNode* nodeC CreateNode(C);BTNode* nodeD CreateNode(D);BTNode* nodeE CreateNode(E);BTNode* nodeF CreateNode(F);nodeA-left nodeB; // AnodeA-right nodeC; // B CnodeB-left nodeD; // D E FnodeC-left nodeE; nodeC-right nodeF; return nodeA;
}int main(void)
{BTNode* root CreateBinaryTree();
}3.二叉树深度优先遍历学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历就是按照某种特定的规则一次对二叉树中的节点进行相应的操作并且每个节点只操作一次。 访问节点所做的操作要看具体的应用问题。遍历是二叉树上最重要的运算之一也是二叉树上进行其他运算的基础。二叉树遍历Traversal沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问。 按照规则二叉树的遍历有前序 / 中序 / 后序 的递归结构遍历。除了前序、中序和后续遍历外我们还可以对二叉树进行层序遍历。比如二叉树的中序遍历3.1二叉树前序遍历前序遍历Preorder Traversal访问根节点的操作发生在遍历其右子树之前。即首先访问根结点然后遍历左子树最后遍历右子树。代码实现前序遍历//二叉树前序遍历
void PreOrder(BTNode* root)
{//首先判断根是否为空为空就返回if (root NULL){printf(NULL ); // 暂时打印出来便于观察 return;}//走到这里说明不为空根据前序遍历先访问根节点printf(%c , root-data);//然后遍历左子树利用递归PreOrder(root-left);//最后遍历右子树利用递归PreOrder(root-right);// A// B C// D E F 前序根 左 右//执行输出 A B D NULL NULL NULL C E NULL NULL F NULL NULL
}① 首先判断根是否为空如果根为空则返回。这里为了表示我们把空节点以 Ø 打印出来。② 如果跟不为空这说明有数据。由于是前序遍历Preorder前序遍历是先访问根节点然后遍历左子树最后再遍历右子树。所以我们这里先要访问的是根节点我们把根节点的数据打印出来。③ 然后我们需要遍历左子树这时我们利用递归就可以实现。将根节点 root 的左数 left 传入 PreOrder 函数将其左树看作根一直递归下去直到碰到 root NULL 则返回。④ 最后遍历完左子树后遍历右子树。利用递归方法同上。3.2二叉树中序遍历递归的中序和后序和前序差不多 顺序换一下就行//二叉树中序遍历
void InOrder(BTNode* root)
{if (root NULL) {printf(NULL ); return;}InOrder(root-left);printf(%c , root-data);InOrder(root-right);// A// B C// D E F 中序左 根 右//执行输出NULL D NULL B NULL A NULL E NULL C NULL F NULL
}3.3二叉树后序遍历void PostOrder(BTNode* root)
{if (root NULL) {printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%c , root-data);// A// B C// D E F 后序左 右 根//执行输出NULL NULL D NULL B NULL NULL E NULL NULL F C A
}3.4二叉树深度优先遍历完整代码#define _CRT_SECURE_NO_WARNINGS 1#includestdio.htypedef int BTDataType;typedef struct BinaryTreeNode
{struct BinaryTreeNode* left; // 记录左节点struct BinaryTreeNode* right; // 记录右节点BTDataType data; // 存储数据
} BTNode;//创建新节点
BTNode* CreateNode(BTDataType x)
{BTNode* new_node (BTNode*)malloc(sizeof(BTNode));if (new_node NULL){printf(malloc failed!\n);exit(-1);}new_node-data x;new_node-left new_node-right NULL;return new_node;
}//手动创建二叉树
BTNode* CreateBinaryTree()
{BTNode* nodeA CreateNode(A);BTNode* nodeB CreateNode(B);BTNode* nodeC CreateNode(C);BTNode* nodeD CreateNode(D);BTNode* nodeE CreateNode(E);BTNode* nodeF CreateNode(F);nodeA-left nodeB; // AnodeA-right nodeC; // B CnodeB-left nodeD; // D E FnodeC-left nodeE; nodeC-right nodeF; return nodeA;
}
//二叉树前序遍历
void PreOrder(BTNode* root)
{//首先判断根是否为空为空就返回if (root NULL){printf(NULL ); // 暂时打印出来便于观察 return;}//走到这里说明不为空根据前序遍历先访问根节点printf(%c , root-data);//然后遍历左子树利用递归PreOrder(root-left);//最后遍历右子树利用递归PreOrder(root-right);// A// B C// D E F 前序 根 左 右//执行输出 A B D NULL NULL NULL C E NULL NULL F NULL NULL
}//二叉树中序遍历
void InOrder(BTNode* root)
{if (root NULL) {printf(NULL ); return;}InOrder(root-left);printf(%c , root-data);InOrder(root-right);// A// B C// D E F 中序左 根 右//执行输出NULL D NULL B NULL A NULL E NULL C NULL F NULL
}//二叉树后序遍历
void PostOrder(BTNode* root)
{if (root NULL) {printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%c , root-data);// A// B C// D E F 后序左 右 根//执行输出NULL NULL D NULL B NULL NULL E NULL NULL F C A
}
int main()
{BTNode* root CreateBinaryTree();PreOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);
}4.二叉树广度优先遍历4.1层序遍历层序遍历Level Traversal设二叉树的根节点所在的层数为1的情况下从二叉树的根节点出发首先访问第1层的树根节点然后再从左到右访问第2层上的节点。接着是第3层的节点……以此类推自上而下、从左向右地逐层访问树的节点。该如何实现层序遍历呢 我们可以利用队列的性质来实现我们之前再讲过队列这里你可以选择自己实现一个队列。如果不想实现就直接复制即可因为我们这里重点要学的是层序遍历链接比特数据结构与算法第三章_下队列的概念和实现力扣225232622_GR C的博客-CSDN博客本篇完。下一篇写写二叉树的OJ题二叉树就暂时结束了
