数据结构系列 二叉树的遍历（顺序存储） |
您所在的位置：网站首页 › 二叉树按层遍历算法实现时采用了数据结构 › 数据结构系列 二叉树的遍历（顺序存储） |
数据结构系列 二叉树的遍历（顺序存储）
|
https://blog.csdn.net/lin20044140410/article/details/89436835 二叉树链式存储 数据结构-树 树是一种一对多的数据结构，是n(n>=0)个结点的有限集。N=0时为空树。在任意一棵非空树中：1，有且只有一个特定的称为根root的结点，2，当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1,T2,,,,Tm，其中每一个集合本身又是一棵树，并且称为根的子树。
一些概念： 结点拥有的子树数称为阶段的度，度为0的结点称为叶结点Leaf，度不为0的结点称为分支结点。树的度是树内个结点的度的最大值。结点的层次，从根开始，根为第一层，根的孩子为第二层，树中结点的最大层次称为树的深度，或者高度。
二叉树 二叉树是一种特殊结构的树，是n个结点的有限集合，或者为空树，或者由一个根结点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。 二叉树的特点： 每个结点最多两棵子树，左子树、右子树是有顺序的，次序不能颠倒，即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
特殊的二叉树 斜树，所有的结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树。斜树，其实就是线性表结构。
满二叉树，在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。 满二叉树特点： 叶子只能出现在最下一层，非叶子结点的度一定是2在同样深度的二叉树中，满二叉树的结点个数最多，叶子最多。
完全二叉树 对一棵具有n个结点的二叉树按层序编号，如果编号为i(1=1. 以上两点都可以通过数据归纳法来得出结论。 任意一棵二叉树，如果终端结点数为n0，度为2的结点数为n2，则n0 = n2 +1，具有n个结点的完全二叉树的深度为log2n +1如果对一棵有n个结点的完全二叉树（深度为log2n +1）的结点，按层序编号（从第1层到第log2n +1 层，每层从左到右），对于任一结点i(1n，则结点i无左孩子，结点i为叶子结点；否则其左孩子是结点2i。
如果2i + 1 > n，则结点i无右孩子，否则其右孩子是结点2i + 1。
依据以上性质，来定义二叉树的存储结构，先说顺序存储。 二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，结点的存储位置，就是数组的下标，相应位置不存在的结点设置为null。这种存储结构，适用于完全二叉树，因为对于极端的右斜树，它有k个结点，却要分配2k -1个存储空间，这是对存储空间的浪费。
二叉树的链式存储结构，每个结点最多两个孩子，所以这种存储结构，一个数据域，两个指针域，两个指针域存放指向左孩子和右孩子的指针，称这样的存储结构为二叉链表。
二叉树的遍历 对二叉树的遍历，就是把树中的结点变成某种意义的线性序列。 遍历算法就是递归。 前序遍历，若二叉树为null，则空操作返回，否则先访问根结点，然后前序遍历左子树，在前序遍历右子树。中序遍历，若树为null，则空操作返回，否则从根结点开始，中序遍历左子树，然后访问根结点，最后中序遍历右子树。后序遍历，若树为null，则空操作返回，否则从左到右，先叶子后结点的方式，先遍历访问左子树，再同样从左到右，先叶子后结点的方式，遍历右子树，最后访问根结点。层序遍历，若树为null，则空操作返回，否则从树的第一层根结点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
从遍历操作可以得出， 已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树； 已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树； 这两种情况都可以确定根结点，并且可以确定左子树或者右子树。 但是，已知前序和后序序列，是不能确定一棵二叉树的，因为虽然根结点可以确定，但是无法确定那个结点是左子树，那个结点是右子树。 二叉树顺序存储代码实现： #ifndef DATA_STRUCTURE_BINARY_TREE_CLASS_H #define DATA_STRUCTURE_BINARY_TREE_CLASS_H #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 100 //存储空间初始分配量 #define MAX_TREE_SIZE 100 //二叉树最大结点树 typedef int Status; //表示函数结果的状态码 typedef int TElemType; //树节点的数据类型，暂定int typedef TElemType SqBiTree[MAX_TREE_SIZE]; //顺序存储结构数组 typedef struct { int level;//节点的层 int order;//本层的序号，按满二叉树计算 }Position; TElemType Nil = 0; //表示空元素 #endif#include "binaryTree.h" #include "iostream" #include "cstdlib" #include "cmath" using namespace std; Status visit(TElemType c) { cout |
【本文地址】
今日新闻 |
推荐新闻 |