- 浏览: 722946 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (1043)
- 数据结构 (36)
- UML与设计模式 (42)
- c++ (87)
- rust (36)
- Qt (41)
- boost模板元编程 (43)
- Linux (77)
- 汇编 (4)
- 其它 (2)
- 烹饪 (3)
- unix c / socket (73)
- 软件工程 (4)
- shell (52)
- Python (37)
- c++ primer 5th(c++11) (22)
- 数据库/MySQL (27)
- 数据存储 (4)
- lisp (7)
- git (4)
- Utility (3)
- CDN与DNS (54)
- Http (53)
- php (7)
- nginx/lua/openresty (41)
- redis (11)
- TCP/IP (16)
- 互联网 (6)
- kernel (2)
- go (34)
- 区块链 (43)
- 比特股 (13)
- 以太坊 (23)
- 比特币 (23)
- 密码学 (10)
- EOS (53)
- DAG (1)
- docker (1)
- filecoin (7)
- solidity (64)
- ipfs (8)
- 零知识证明 (1)
- openzeppelin (3)
- java (1)
- defi (7)
最新评论
一棵二叉树的结点的一个有限集合:该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的,互不相交的二叉树组成。
相关性质:
1.在二叉树的第i(i>=1)层最多有2的i-1次方个结点。
2.深度为k(k>=0)的二叉树最少有k个结点,最多有2的k次方-1个结点。
3.叶结点数等于度为2的非叶结点数加1:N0=N2+1
4.满二叉树:深度为k的满二叉树有2的k次方-1个结点
5.完全二叉树:每个结点都与高度为k的满二叉树中编号1~n的结点一一对应
6.具有n个结点的完全二叉树的深度为log2(n+1)向上取整
抽象数据类型:
相关性质:
1.在二叉树的第i(i>=1)层最多有2的i-1次方个结点。
2.深度为k(k>=0)的二叉树最少有k个结点,最多有2的k次方-1个结点。
3.叶结点数等于度为2的非叶结点数加1:N0=N2+1
4.满二叉树:深度为k的满二叉树有2的k次方-1个结点
5.完全二叉树:每个结点都与高度为k的满二叉树中编号1~n的结点一一对应
6.具有n个结点的完全二叉树的深度为log2(n+1)向上取整
抽象数据类型:
#ifndef BINARYTREE_H #define BINARYTREE_H template<typename T> class BinaryTree{ public: BinaryTree(); //item为根,lch,rch为左右子树 BinaryTree(BinTreeNode<T>* lch,BinTreeNode<T>* rch,T item); int Height(); int Size();//结点个数 bool IsEmpty(); BinTreeNode<T> *Parent(BinTreeNode<T>* current); BinTreeNode<T> *LeftChild(BinTreeNode<T>* current); BinTreeNode<T> *RightChild(BinTreeNode<T>* current); bool Insert(T item); bool Remove(T item); bool Find(const T& item)const; bool getData(const T& item)const; BinTreeNode<T>* getRoot()const; void preOrder(void(*visit)(BinTreeNode<T>*p));//前序 void inOrder(void(*visit)(BinTreeNode<T>*p));//中序 void postOrder(void(*visit)(BinTreeNode<T>*p));//后序 void levelOrder(void(*visit)(BinTreeNode<T>*p));//层次 }; #endif // BINARYTREE_H
发表评论
-
时间复杂度推导
2012-06-05 22:57 9111.用常数1取代运行时间中的所有加法常数 2.在修改后的运行次 ... -
数据结构概论2
2012-06-04 22:19 766数据元素:组成数据的,有一定意义的基本单位,在计算机中通常作为 ... -
排序概念
2011-06-24 14:51 755数据表:待排序数据元素的有很集合 排序码:通常数据元素有多个 ... -
图的基本概念
2011-06-20 16:18 726完全图:n个顶点,n*(n-1)/2个边的无向图,就是无向完全 ... -
红黑树
2011-06-16 14:29 480红黑树: 1.根结点和所有的叶结点都是黑色 2.从根结点到叶结 ... -
链表反转
2011-06-12 18:03 1062template<typename T> v ... -
散列表(哈希表)
2011-06-09 09:55 1023散列表(hash table):是表示集合和字典的另一种有效方 ... -
跳 表
2011-06-08 11:12 771#ifndef SKIPLIST_H #define S ... -
字 典
2011-06-08 10:06 887字典:以集合为基础,并支持支持Member,Insert和Re ... -
LinkedSet
2011-06-07 13:08 890改了很久的bug #ifndef LINKEDSET_H ... -
bitset
2011-06-06 12:27 848bitSet.h #ifndef BITSET_H #d ... -
Huffman树
2011-06-02 11:06 859Huffman树,又称最优二叉树,是一类加权路径长度最短的二叉 ... -
堆
2011-06-02 09:19 921在优先级队列的各种实现中,堆是最高效的一种数据结构 关键码: ... -
森 林
2011-06-01 11:09 560森林与二叉树互转,主要是子结点转左子树,兄弟结点转右子树 深 ... -
二叉树的链式实现
2011-05-31 11:24 1241binaryTree.h #ifndef LINKEDBI ... -
树基本概念
2011-05-30 09:28 862结点(node):包含数据项及指向其他结点的分支。 结点的度( ... -
广义表
2011-05-27 10:57 896广义表的定义是递归的,因为在表的描述中又用到了表,允许表中有表 ... -
矩阵相关
2011-05-26 10:22 889矩阵:是一个具有m行n列的二维数组。 上三角矩阵:只存储对角 ... -
优先级队列
2011-05-21 11:24 575PQueue.h #ifndef PQUEUE_H #d ... -
链式队列
2011-05-20 12:05 802LinkedQueue.h #ifndef LINKEDQ ...
相关推荐
玩转二叉树
第1关树和二叉树基本概念 第2关二叉树的顺序存储及基本操作 在计算机科学中,二叉树是每个节点最多只有两个分支的树结构,即每个节点的分支度不大于2。通常分支被称作左子树和右子树,同时二叉树的分支具有左右次序...
实验四 二叉树基本操作的实现 二叉树概念及其存储结构 二叉链储存结构的二叉树基本操作 举例说明什么样的二叉树采用顺序存储,什么样的二叉树采用二叉链存储
数据结构课件:第6章 树和二叉树1基本概念和二叉树.pptx
18923 二叉树的直径
c++数据结构 二叉树和树基本概念-特性-存储.ppt 详细描述二叉树的基本特性
二、基本概念 o2.1 结点 o2.2 二叉树 2.2.1 二叉树的深度 o2.3 满二叉树 o2.4 完全二叉树 2.4.1 完全二叉树的线性存储 2.4.2 完全二叉树的创建与遍历 一、背景 二叉树是数据结构中的重点,也是难点。二叉树...
1、 熟练掌握树的基本概念、结构特点并且熟悉各种存储结构的特性。 2、 重点掌握二叉树的生成、遍历及求深度等算法。 3、 掌握赫夫曼树的含义及其应用。 二、 实验要求 1、 从终端读入要编码的字符串,对所输入的...
通过阅读本文,读者将能够全面理解二叉树的基本概念和原理,并掌握其在实际问题中的应用。 二叉树是一种特殊的树形结构,它满足以下特性: 每个节点最多有两个子节点。 子节点之间没有顺序关系,即左子节点和右子...
1、掌握二叉树的基本概念,链表描述方法;遍历方法。 二、实验内容 1、 创建二叉树类。二叉树的存储结构使用链表。 2、 提供操作:前序遍历、中序遍历、后序遍历、层次遍历、计算二叉树结点数目、计算二叉树高度。 3...
数据结构(C++)上课笔记——树和二叉树的基本概念(2020-5-6),详细记录上课内容,并附有可调试成功的代码,很好的复习、编程参考资料
漫话数据结构
1、简要介绍一些关于树的基本术语; 2、讲解二叉树的节点信息并演示插入和遍历二叉树的方法;
主要知识点 树的基本概念和存储结构 二叉树的基本概念 二叉树的性质 二叉树的操作实现 二叉树的遍历 线索二叉树的概念和设计方法 哈夫曼树的概念和设计方法 树与二叉树的转换方法
本学年论文介绍了二叉树的定义,二叉树的存储结构,二叉树的相关术语,以此引入二叉树这一概念,为展开二叉树的基本操作做好理论铺垫。二叉树的基本操作主要包含以下几个模块:二叉树的遍历方法,计算二叉树的结点个...
一、树的基本概念 二、二叉树 三、二叉树的遍历 三、线索二叉树 四、树和森林 六、哈夫曼树 定义:是一种常非线性结构树是n(n≥0)个结点的有限集合。若n=0,则称为空树;否则,有且仅有一个特定的结点被称为...
在学习遍历之前,会先带大家回顾一下二叉树的基本概念。学习二叉树的基本操作前,需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,为了能够先易后难地进行讲解,我们将暂时手动创建...
数据结构》(C语言版)的第1章综述数据、数据结构和抽象数据类型等基本概念;第2章至第7章从抽象数据类型的角度,分别讨论线性表、栈、队列、串、数组、广义表、树和二叉树以及图等基本类型的数据结构及其应用;第8...
源码实现了二叉树的基本操作,包括节点的创建、插入、删除、遍历等。代码结构清晰,注释详细,实现了标准的二叉树操作接口。 源码通过C语言实现,采用二叉树的数据结构。实现了二叉树的主要操作,如插入、删除、前序、...