网页设计psd源文件,济南网站优化排名,城阳 网站建设,怎么给wordpress切图目录 二叉树基础知识
概念 :
根节点的五个形态 :
特殊的二叉树
满二叉树 : 完全二叉树 :
二叉搜索树 :
平衡二叉搜索树 :
二叉树的性质 :
二叉树的存储结构
二叉树的顺序存储结构
二叉树的链式存储结构 二叉树的遍历方式 :
基础概念
前中后遍历 层序遍历 :…目录 二叉树基础知识
概念 :
根节点的五个形态 :
特殊的二叉树
满二叉树 : 完全二叉树 :
二叉搜索树 :
平衡二叉搜索树 :
二叉树的性质 :
二叉树的存储结构
二叉树的顺序存储结构
二叉树的链式存储结构 二叉树的遍历方式 :
基础概念
前中后遍历 层序遍历 : 二叉树基础知识
概念 :
二叉树binary tree是指树中节点的度不大于2的有序树它是一种最简单且最重要的树。二叉树的递归定义为二叉树是一棵空树或者是一棵由一个根节点和两棵互不相交的分别称作根的左子树和右子树组成的非空树左子树和右子树又同样都是二叉树。
根节点的五个形态 : 空二叉树 只有一个根结点 根结点只有左子树 根结点只有右子树 根结点既有左子树又有右子树
特殊的二叉树
满二叉树 :
概念 :
如果一棵二叉树只有度为0的结点和度为2的结点并且度为0的结点在同一层上则这棵二叉树为满二叉树。
图例 : 完全二叉树 :
概念 : 在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层h从1开始则该层包含 1~ 2^(h-1) 个节点。
图例 : 而 这个就不是一颗完全二叉树!
二叉搜索树 :
前面介绍的树都没有数值的而二叉搜索树是有数值的了二叉搜索树是一个有序树。
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树
下面的就是一颗二叉搜索树; 二叉搜索树最大的特点就是左父右 ;
平衡二叉搜索树 :
又被称为AVLAdelson-Velsky and Landis树且具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。
其中c中的map、set、multimapmultiset的底层实现都是平衡二叉搜索树所以map、set的增删操作时间时间复杂度是logn , 而unordered_map、unordered_setunordered_map、unordered_set底层实现是哈希表。
二叉树的性质 : 二叉树的第i层上至多有2 ^ (i-1)i≥1个节点。 深度为h的二叉树中至多含有2^h-1个节点 若在任意一棵二叉树中有 n0 个叶子节点有 n2 个度为2的节点则必有n0 n2 1 具有n个节点的完全二叉树深为log2(x) 1其中x表示不大于n的最大整数 若对一棵有n个节点的完全二叉树进行顺序编号1in那么对于编号为ii1的节点: ⑴i 1 时该节点为根它无双亲节点 。 ⑵ i 1 时该节点的双亲节点的编号为i/2 。 ⑶2i n则有编号为2i的左节点否则没有左节点 。 ⑷2i1n 则有编号为2i1的右节点否则没有右节点 。
二叉树的存储结构
二叉树可以顺序存储也可以链式存储 ;
二叉树的顺序存储结构
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点并且结点的存储位置也就是数组的下标要能体现结点之间的逻辑关系比如双亲与孩子的关系左右兄弟的关系等。
如以下这颗完全二叉树 : 可以采用以下线性表来存储:
下标12345678910数据ABCDEFGHIJ 如果父节点的数组下标是 i那么它的左孩子就是 i * 2 1右孩子就是 i * 2 2。 二叉树的链式存储结构
在链式结构中一个二叉树的结点包含左孩子指针数据右孩子指针 ; 链式存储效果如图 : 二叉链表的结构体定义 : typedef struct BiTNode
{TElemType data; //数据域struct BiTNode *lchild,*rchild; //指针域
}BiTNode*BiTree; 二叉树的遍历方式 :
基础概念
首先主要的两种遍历方式为 :
深度优先遍历先往深走遇到叶子节点再往回走。广度优先遍历一层一层的去遍历。
这两种遍历方法又可以细分 :
深度优先遍历 前序遍历递归法迭代法中序遍历递归法迭代法后序遍历递归法迭代法广度优先遍历 层次遍历迭代法
前中后遍历
其中前中后三种结点的遍历顺序 如下 :
前序遍历中左右中序遍历左中右后序遍历左右中
图例 : 层序遍历 :
从树的第一层开始访问从上而下逐层遍历在同一层中按从左到右的顺序对结点逐个访问 ;
如下图 : 层序遍历的结果为 :
ABCDEFGHI 参考 : 《大话数据结构》 《数据结构》C语言版清华严蔚敏考研版 【数据结构与算法】二叉树 代码随想录
