Closed 1c7 closed 8 years ago
只是写写笔记, 不是专门写教程 所以会缺一些东西,比如叶节点是什么 一边学一边写 现在还没写完全
最小的树:
一颗普通的树:
不要关注数字是多少,关注这种层级结构。
树: 树里的每个节点只有一条路线, 和其他节点相连 图: 图里的至少一个节点有1个以上的路线连接到其他节点
下面是一棵树
下面是一个图
注意数字 13 这里,这里构成了一个回路,所以就不算是树了
这样也算是图
跟线路的层次无关(13 连的是第二层的 18 还是第三层的 60 根本不重要) 只要某个节点有两条路出去,就算是图了。
允许只有左子节点或者只有右子节点, 并不是说除了叶节点之外其他节点都要有2个子节点才算
这是一颗二叉树
这也是一颗二叉树
不是二叉树(有3个子节点)
满二叉树例子1
满二叉树例子2
满二叉树例子3
完全二叉树例子1
完全二叉树例子2
完全二叉树例子3
另外: 堆是一种特殊的完全二叉树 当一颗完全二叉树, 上级节点都比子节点小的时候, 叫做最小堆 当一颗完全二叉树, 上级节点都比子节点大的时候, 叫做最大堆
树(数据结构)的维基百科 https://en.wikipedia.org/wiki/Tree_(data_structure) 二叉树的维基百科 https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91
占位
只是写写笔记, 不是专门写教程 所以会缺一些东西,比如叶节点是什么
一边学一边写 现在还没写完全
树的定义
最小的树:![image](https://cloud.githubusercontent.com/assets/1804755/10268120/52db77ea-6ae1-11e5-94d1-89eaba9b1ada.png)
一颗普通的树:![image](https://cloud.githubusercontent.com/assets/1804755/10268135/db2074ac-6ae1-11e5-94e9-cfab113cd524.png)
不要关注数字是多少,关注这种层级结构。
树和图的区别:
树: 树里的每个节点只有一条路线, 和其他节点相连
图: 图里的至少一个节点有1个以上的路线连接到其他节点
下面是一棵树
![image](https://cloud.githubusercontent.com/assets/1804755/10268172/36454f0a-6ae3-11e5-8074-c14ab5488597.png)
下面是一个图
注意数字 13 这里,这里构成了一个回路,所以就不算是树了![image](https://cloud.githubusercontent.com/assets/1804755/10268141/311f1c46-6ae2-11e5-886f-dee9e7a57a57.png)
这样也算是图![image](https://cloud.githubusercontent.com/assets/1804755/10268156/6a1b4d4e-6ae2-11e5-9ac2-b04da2bf3104.png)
跟线路的层次无关(13 连的是第二层的 18 还是第三层的 60 根本不重要) 只要某个节点有两条路出去,就算是图了。
树的分类
1.1. 完全二叉树
1.2. 满二叉树
1. 二叉树 = 每个节点最多2个子节点.
允许只有左子节点或者只有右子节点, 并不是说除了叶节点之外其他节点都要有2个子节点才算
这是一颗二叉树![image](https://cloud.githubusercontent.com/assets/1804755/10268192/cba98980-6ae3-11e5-9117-62f00cca02dd.png)
这也是一颗二叉树![image](https://cloud.githubusercontent.com/assets/1804755/10268235/d8a142a8-6ae4-11e5-983f-5eabdc739697.png)
这也是一颗二叉树![image](https://cloud.githubusercontent.com/assets/1804755/10268207/3de2a950-6ae4-11e5-8880-2a546ccff958.png)
这也是一颗二叉树![image](https://cloud.githubusercontent.com/assets/1804755/10268210/4eeffb94-6ae4-11e5-9646-b5743acbf134.png)
不是二叉树(有3个子节点)![image](https://cloud.githubusercontent.com/assets/1804755/10268216/7b6ba0f6-6ae4-11e5-89b0-dd376af68f9c.png)
1.1 满二叉树 = 全都有2个子节点, 深度一致
满二叉树例子1
满二叉树例子2
满二叉树例子3
1.2 完全二叉树 = 全都有2个子节点, 深度不一致
完全二叉树例子1
完全二叉树例子2
完全二叉树例子3
另外: 堆是一种特殊的完全二叉树
当一颗完全二叉树, 上级节点都比子节点小的时候, 叫做最小堆
当一颗完全二叉树, 上级节点都比子节点大的时候, 叫做最大堆
资料来源
树(数据结构)的维基百科 https://en.wikipedia.org/wiki/Tree_(data_structure)
二叉树的维基百科 https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91
有错请留言,谢谢