厦门国外网站建设公司排名,合肥建设工程网,番禺电商网站建设,平台网站建设哪家有一、基本概念
1.二叉树是n(n0)个结点的有限集合: ① 或者为空二叉树#xff0c;即n0。
②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点#xff1a; ①每个结点至多只有两棵子树。
②左右子树不能颠倒0)个结点的有限集合: ① 或者为空二叉树即n0。
②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点 ①每个结点至多只有两棵子树。
②左右子树不能颠倒二叉树是有序树
二叉树是递归定义的二叉树 五种状态
1.空二叉树 2.只有左子树 3.只有右子树 4.只有根节点 5.左右子树都有 二、几种特殊的二叉树
1.满二叉树以可高度为h且还有2^h-1个结点的二叉树。
特点①只有最后一层有叶子结点
②不存在度为1的结点
③按层序从1开始编号结点i的左孩子为2i右孩子为2i1;结点i的父节点为[i/2](如果有的话,向下取整)--可以用顺序存储来实现。
2.完全二叉树当且仅当其每个结点都与高度为h满二叉树中编号为1~n的结点一一对应时称为完全二叉树
特点①只有最后两层可能有叶子结点 ②)最多只有一个度为1的结点 ③同上③ ④i|n/2]为分支结点i|n/2]为叶子结点
对于完全二叉树来说如果某一个结点只有一个孩子必然是左孩子。) 3.二叉排序树 一棵二叉树或者是空二叉树或者是具有如下性质的二叉树:
左子树上所有结点的关键字均小于根结点的关键字;
右子树上所有结点的关键字均大于根结点的关键字。
左子树和右子树又各是一棵二叉排序树。可用于元素的排序、搜索 4.平衡二叉树树上任一结点的左子树和右子树的深度之差不超过1.有更高的搜素效率
-----左边相比于右边查找相同的数字遍历的结点要少很多。 总结
