树 二叉树
教程导读
学研发网的这篇信息学奥赛技术教程文章主要介绍了树 二叉树,现在分享给大家,供学习和参考。文章包含5252字,纯文字阅读大概需要14分钟。
教程信息
一、什么是二叉树
(一)二叉树
二叉树是一种特殊的树结构,其中每个节点最多有两个子节点(树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2),分别称为左子节点和右子节点。
因此,二叉树的结点有5中基本形态:
(二)满二叉树和完全二叉树
1、满二叉树:
深度为k且有2k–1个结点的二叉树,即每层结点数都是最大结点数(每个非叶子结点2个孩子)
2、完全二叉树:
可以对满二叉树的结点进行连续编号,约定编号从根结点起,自上而下,从左到右有n个结点的二叉树,当其每一个结点都与深度为k的满二叉树编号对应时,称为完全二叉树(最后一层要么是满的,要么在右边缺少连续若干节点)
三、二叉树的存储
(一)顺序存储
1、完全二叉树:
从根节点开始,按照层次依次将树中节点存储到数组
2、普通二叉树:
给二叉树额外添加一些节点,将其"拼凑"成完全二叉树,然后根据完全二叉树存储
3、访问方法:
对于任意结点i,右孩子编号为2*i+1,左孩子编号为2*i,父节点为i/24、缺点有可能对存储空间造成极大的浪费,在最坏的情况下,一棵深度为k且退化为链表的树,它只有k个结点,却需要2k-1个结点存储空间。这显然是对存储空间的严重浪费,所以顺序存储结构一般只用于完全二叉树或满二叉树。
(二)链式存储
1、孩子表示法
每个节点有三个域——数据域data
和左孩子域left
、右孩子域right
。适用于通过父节点查找孩子结点,不适用于查找某结点的父结点。
struct TreeNode { int data; int left, right; }; TreeNode tree[10];
2、双亲表示法
每个节点都有两个域——数据域data
和双亲域parent
。当算法中需要在树结构中频繁地查找某结点的父结点时,使用双亲表示法最合适。当频繁地访问结点的孩子结点时,双亲表示法就很麻烦。
struct TreeNode { int data; int parent; }; TreeNode tree[10];
结点tree[i]的父节点可以用tree[tree[i].parent]表示。
3、孩子双亲表示法
每个节点有四个域——数据域data
,左孩子域left
、右孩子域right
和双亲域parent
。是孩子表示法与双亲表示法的综合,可以顺利访问每个结点的父节点和孩子结点,缺点是增加了存储空间。
struct TreeNode { int data; int parent; int left, right; }; TreeNode tree[10];
结点tree[i]的左右孩子分别可以用tree[tree[i].left]和tree[tree[i].right]表示,父节点可以用tree[tree[i].parent]表示
四、二叉树的遍历
二叉树的遍历指按一定的规律和次序访问树中的各个结点,而且每个结点仅被访问一次
(一)遍历方法
1、先序遍历:
先访问根节点,再访问左子树,最后访问右子树。
2、后序遍历:
先左子树,再右子树,最后根节点。
3、中序遍历:
先左子树,再根节点,最后右子树。
4、层次遍历:
每一层从左到右访问每一个节点。
其中前三种都可以通过深度优先搜索实现,最后一种使用广度优先搜索实现。
(二)不同遍历之间的关系:
(1)已知前序序列和中序序列可以确定出二叉树
(2)已知中序序列和后序序列也可以确定出二叉树
(3)已知前序序列和后序序列却不可以确定出二叉树
(三)二叉树遍历的实现
下列二叉树用孩子表示法存储在数组中,编写四个函数实现不同的遍历顺序:
struct TreeNode { | void preorderTraversal(int root) {// 先序遍历 |
int main() { | void postorderTraversal(int root) {// 后序遍历 |
void inorderTraversal(int root) {// 中序遍历 | |
// 层次遍历 |
实现代码:
#include<iostream> #include <algorithm> #include <queue> using namespace std; struct TreeNode { int data; int leftChild; int rightChild; }; TreeNode nodes[10]; void preorderTraversal(int root) { // 先序遍历 if (root == -1) return; cout << nodes[root].data << " "; preorderTraversal(nodes[root].leftChild); preorderTraversal(nodes[root].rightChild); } void postorderTraversal(int root) { // 后序遍历 if (root == -1) return; postorderTraversal(nodes[root].leftChild); postorderTraversal(nodes[root].rightChild); cout << nodes[root].data << " "; } void inorderTraversal(int root) { // 中序遍历 if (root == -1) return; inorderTraversal(nodes[root].leftChild); cout << nodes[root].data << " "; inorderTraversal(nodes[root].rightChild); } // 层次遍历 void levelOrderTraversal(int root) { if (root == -1) return; queue < int > q; q.push(root); while (!q.empty()) { int current = q.front(); q.pop(); cout << nodes[current].data << " "; if (nodes[current].leftChild != -1) q.push(nodes[current].leftChild); if (nodes[current].rightChild != -1) q.push(nodes[current].rightChild); } } int main() { // 构建二叉树 nodes[0] = { 1, 1, 2 }; nodes[1] = { 2, 3, 4 }; nodes[2] = { 3, 5, -1 }; nodes[3] = { 4, -1, 6 }; nodes[4] = { 5, 7, -1 }; nodes[5] = { 6, -1, -1 }; nodes[6] = { 7, -1, -1 }; nodes[7] = { 8, -1, -1 }; nodes[8] = { 9, -1, -1 }; nodes[9] = { 10, -1, -1 }; cout << "Preorder traversal: "; preorderTraversal(0); cout << endl; cout << "Postorder traversal: "; postorderTraversal(0); cout << endl; cout << "Inorder traversal: "; inorderTraversal(0); cout << endl; cout << "Level order traversal: "; levelOrderTraversal(0); cout << endl; return 0; }
执行结果:
教程咨询
如果章节内容看不懂,可以联系作者。
教程总结
以上是学研发网为您提供树 二叉树的全部内容,希望教程文章能够帮你了解学习树 二叉树,解决所遇到的问题。 如果觉得学研发网信息学奥赛教程内容还不错,欢迎将学研发网网站推荐给身边需要的人。
教程备注
版权声明:教程内容为学研发网整理和编写,如需转载请联系站长并附上文章原始链接和原始作者信息。
手机阅读
扫描二维码推送至手机访问。
本文链接:http://www.xueyanfa.com/xinaojiaocheng/xinaogaoji-295.html