树 (图论)

树
	包括ほうかつ6个顶点てん，5条じょう边的树
顶点	v
边	v - 1
色いろ数すう	2
	查; 论; 编;

在ざい图论中なか，树（英語えいご：tree）是ぜ一いち種しゅ無む向むこう圖ず（英語えいご：undirected graph），其中任意にんい两个顶点间存在そんざい唯一ゆいいつ一いち條じょう路みち径みち。或ある者もの说，只ただ要よう没ぼつ有ゆう環たまき的てき连通图就是树。森林しんりん是ぜ指ゆび互相不ふ交并树的集合しゅうごう。树广泛应用よう于计算机つくえ科学かがく的てき数かず据すえ结构中なか，比ひ如二叉查找树，堆うずたか，Trie树以及用よう於数かず据すえ压缩的てき霍夫曼树等ひとし等ひとし。

定てい义[编辑]

如果一个无向简单图 G 满足以下いか相互そうご等とう价的条件じょうけん之の一いち，那な么 G 是ぜ一いち棵树：

G 是ぜ没ぼつ有ゆう環たまき的てき连通图。
G 没ぼつ有ゆう環たまき，但ただし是ぜ在ざい G 内うち添加てんか任意にんい一いち条じょう边，就会形成けいせい一いち个環。
G 连通，但ただし是ぜ如果去さ掉任意にんい一いち条じょう边，就不再さい连通。
G 中ちゅう任意にんい两顶点てん間あいだ存在そんざい唯一ゆいいつ路みち径みち。

如果无向简单图 G 有ゆう有限ゆうげん个顶点てん（设为 n 个顶点てん），那な么 G 是ぜ一いち棵树还等价于：

G 连通，有ゆう n − 1 条じょう边，并且 G 中ちゅう没ぼつ有ゆう環たまき。

如果一个无向简单图 G 中ちゅう没ぼつ有ゆう環たまき，那な么 G 是これ森林しんりん。

性せい质[编辑]

一棵树中任两个顶点之これ间都有ゆう且只有ゆう一いち条じょう路ろ径みち（指ゆび没ぼつ有ゆう重じゅう复边的てき路ろ径みち）。一いち棵有 n 个顶点てん的てき树有 n − 1 条じょう边，其為具有ぐゆう n 个点连通图的所しょ需的最少さいしょう边数。所以ゆえん如果去さ掉树中ちゅう的てき一いち条じょう边，树就会かい不ふ连通。

如果在ざい一棵树中加入任意的一条边，就会得えとく到いた有ゆう且只有ゆう一いち个环的てき图。这是因いん为这条じょう边连接せっ的てき两个点てん（或ある是ぜ一いち个点）中有ちゅうう且只有ゆう一いち条じょう路ろ径みち，这条路ろ径みち和わ新しん加か的てき边连在ざい一起就是一个环。如果把わ一个连通图中的多余边全部删除，所しょ构成的てき树叫做这个图的てき生成せいせい树。

如果要よう在ざい树中加入かにゅう一いち个点，就要加入かにゅう一条这个点和原有的点相连的边。这条边不会かい给这棵树增加ぞうか一个环或者多余的路径。所以ゆえん每次まいじ这样加入かにゅう一いち个点，就可以构成なり一いち棵树。

一棵树既可以是有向ゆうこう的てき也可以是无向的てき。显然，树是连通图，但ただし不ふ会かい是ぜ双そう连通图（对于无向图）或ある者もの强つよ连通图（对于有向ゆうこう图）。树可以算是ぜ稀まれ疏图。

显然树中也没有ゆう自じ环和重かずえ复边。

有ゆう根ね树[编辑]

在ざい一棵树中可以指定一个特殊的节点：根ね。一個有根的树叫做有ゆう根ね树。

有ゆう根ね树中的てき节点可か以根据すえ到いた根ね的てき距离分ぶん层。一颗有根树的层数叫做这棵树的高度こうど。节点最多さいた的てき那な一层的节点数叫做这棵树的宽度。对于有ゆう根ね树，每まい条じょう边都有ゆう一いち个特殊こと的てき方向ほうこう：指向しこう根ね节点的てき方向ほうこう，或ある者もの说上一いち层的方向ほうこう（或ある者もの相反あいはん的てき，指向しこう叶かのう节点的てき方向ほうこう，下した一いち层的方向ほうこう）。一条边的两个端点中，靠もたれ近きん根ね的てき那な个节点てん叫さけべ做另一いち个节点てん的てき父ちち节点（也叫父ちち亲、双そう亲、双そう亲节点てん），相反あいはん的てき，距离根ね比ひ较远的てき那な个节点てん叫さけべ做另一いち个节点てん的てき子こ节点（也可以叫孩子，儿子，子女しじょ等ひとし）。父ちち亲方向ほうこう的てき所有しょゆう节点都と叫さけべ做这个节点てん的てき祖先そせん，儿子方向ほうこう的てき所有しょゆう节点都と叫さけべ做这个节点てん的てき子こ孙。没ぼつ有子ゆうこ节点的てき子こ节点叫さけべ做叶かのう节点（或ある者もの叶かのう子こ节点）。由よし于到根ね的てき路ろ径みち只ただ有ゆう一いち条じょう，根ね节点以外いがい的てき节点的てき父ちち节点永なが远只有ゆう一いち个，祖先そせん就是这个点てん到いた根ね的てき路ろ径みち上じょう的てき所有しょゆう节点（包括ほうかつ根ね，不ふ包括ほうかつ这个节点本身ほんみ）。另外，以一个节点为根的树是指包括这个节点和其所有子孙，并以这个节点为根的てき树。由よし于一般不需要这以外的子树，每ごと一个节点也可以对应到一个以其为根的树，一个节点的子树通常也是指以这个节点的子节点为根的树。

如果一颗有根树每个节点的子树最多有n个，同どう时每个节点在てんざい其父节点中なか都と有ゆう固定こてい的てき可能かのう可か以留空そら的てき位置いち，这棵树叫做n叉また树。其中每ごと个节点てん都と可か以有两个固定こてい位置いち的てき子こ树的有ゆう根ね树叫做二に叉また树，二叉树中每个节点的两个子树分别叫做左ひだり子こ树和わ右子ゆうこ树，由ゆかり于位置いち固定こてい，没ぼつ有ゆう左ひだり子こ树的时候也是可か以有右子ゆうこ树的。而“多た叉また树”通常つうじょう并不指ゆびn为任意にんい值的n叉また树，只ただ是ぜ在ざい和わn叉また树作比ひ较的时候表示ひょうじ普通ふつう的てき有ゆう根ね树。

对于随ずい机つくえ的てき树，高度こうど的てき平均へいきん复杂度ど是ぜO(logn)，但ただし是ぜ没ぼつ有限ゆうげん制せい而且不随ふずい机つくえ的てき树高度ど也可以达到O(n)，也就是ぜ除じょ了りょう叶かのう节点都と只ただ有ゆう一いち个子树，或ある者もの常数じょうすう个分支ささえ的てき情じょう况。所以ゆえん树作为数据すえ结构时通常つうじょう需要じゅよう另外进行平衡へいこう。

存そん储[编辑]

对于普通ふつう的てき树，可か以像图一样为每一个点存储一个边表（通常つうじょう按顺序じょ存そん和わ每ごと一个點的关系的叫做邻接矩のり阵，存そん具体ぐたい的てき边的叫さけべ做邻接表ひょう），或ある者もの直接ちょくせつ存そん储所有しょゆう边的边表等ひとし。由よし于树是ぜ稀まれ疏图，所以ゆえん一般不用邻接矩阵存储。对于有ゆう根ね树，如果用よう为每一个点储存一个边表的方法，由よし于每一棵树都只有一个父节点，所以ゆえん通常つうじょう指向しこう父ちち节点的てき边不存在そんざい这个表ひょう中ちゅう。同どう时如果はて子こ节点是ぜ没ぼつ有ゆう顺序的てき，也是因いん为一个节点的子节点不会同时是其他节点的子节点，也可以把子こ节点直接ちょくせつ当とう成なり存そん边的链表的てき节点，这时候こう每ごと个节点てん只ただ需要じゅよう储存两个指ゆび针，所以ゆえん这种存そん储方法ほう有ゆう时候也会被ひ叫さけべ做多叉また树转二に叉また树。

对于子こ节点是ぜ有ゆう顺序的てき有ゆう根ね树，每まい条じょう边都可か以以固定こてい的てき位置いち分ぶん别储存そん。对于完全かんぜん二に叉また树甚至能のう直接ちょくせつ用よう一个数组访问所有节点，不ふ另外储存边的信しん息いき。有ゆう的てき树可以被设计成なり固定こてい的てき从根节点开始访问，这时候こう可か以不储存父ちち节点。同どう样的，有ゆう的てき树也可か以省略しょうりゃく子こ节点，例れい如并查集しゅう。

树的遍へん历[编辑]

对于一般いっぱん的てき树，可か以用和わ普通ふつう的てき图一样的方法ほうほう遍あまね历，比ひ如深度しんど优先搜索そうさく和わ宽度优先搜索そうさく。如果和わ树的每ごと个节点てん相しょう邻的点てん有ゆう固定こてい的てき顺序，深度しんど优先搜索そうさく可か以不储存当とう前まえ点てん以外いがい的てき任にん何なん信しん息いき，而且不用ふよう判ばん重じゅう。而在有ゆう根ね树中更さら方便ほうべん，所以ゆえん有ゆう根ね树中很少使用しよう宽度优先搜索そうさく。

对于有ゆう根ね树的从根开始的てき深度しんど优先搜索そうさく遍あまね历，有ゆう三さん种特定とくてい的てき顺序：

前ぜん序じょ遍へん历: 先さき访问根ね节点，然しか后きさき再さい访问所有しょゆう的てき子こ树；
后きさき序じょ遍へん历: 先さき访问子こ树，然しか后きさき再さい访问根ね节点；
中ちゅう序じょ遍へん历: 二に叉また树专用よう，先さき访问左ひだり子こ树，然しか后きさき是ぜ根ね节点，最さい后きさき是ぜ右子ゆうこ树。

注意ちゅうい对于每ごと一いち种遍历，事こと实上都と得とく先さき访问根ね节点，这里的てき遍へん历顺序じょ是ぜ指ゆび处理节点中ちゅう的てき数すう据すえ的てき顺序。已やめ知ち中ちゅう序じょ遍へん历和任にん一其他遍历的情况下，可か以还原ばら一いち个二に叉また树。一いち个直观的方法ほうほう是ぜ按前序じょ或ある者もの反はん转的后きさき序じょ插入そうにゅう一个按中序排序的搜索树。已やめ知し前ぜん序じょ和わ中ちゅう序じょ也可以还原ばら一いち棵树，但ただし是ぜ不能ふのう知道ともみち二叉树中一个节点唯一的子树是在左边还是右边。

事こと实上也可以把左右さゆう的てき顺序反はん过来。这些由よし根ね开始的てき遍へん历方法ほう也适用よう于特定とくてい的てき一いち个子树。

森林しんりん[编辑]

森林しんりん比ひ树少一いち个条件じょうけん，指ゆび没ぼつ有ゆう回路かいろ的てき图。也就是ぜ说，森林しんりん可能かのう是ぜ不ふ连通的てき，边数可能かのう比ひ树还少しょう，就是说小于顶点数てんすう。

森林しんりん也可以看成なり是ぜ好こう多た棵互不ふ相あい连的非ひ空そら的てき树，只ただ有ゆう一棵树也可以算是森林。不ふ过森林りん不ふ一定いってい是ぜ一いち棵树。

森林しんりん也可以是有ゆう根ね的てき，这时候こう森林しんりん中ちゅう的てき每ごと一棵树都有一个根。

一棵树去掉若干条边也会成为森林，这时候こう可か以看成なり一棵树分成了好多棵树。森林しんりん中ちゅう的てき两棵树之间加一いち条じょう边，也可以把这两棵树合あい在ざい一起かずき，最さい终合成ごうせい一いち棵树。

很多地方ちほう用よう森林しんりん，都みやこ是ただし用よう来らい表示ひょうじ很多棵树，包括ほうかつ作さく为逻辑结构、数かず据すえ结构的てき时候等とう。有ゆう一种重要的数据结构并查集しゅう就是一いち个有根ね的てき森林しんりん，可か以很快かい的てき判断はんだん两个元素げんそ是ぜ不ふ是ぜ属ぞく于同一いち个互相しょう独立どくりつ的てき集合しゅうごう，以及合あい并两个集合しゅうごう等とう。

逻辑结构[编辑]

树也通常つうじょう会かい用よう来らい表示ひょうじ逻辑结构，例れい如搜索そうさく树。表示ひょうじ逻辑结构的てき树一般是有根树。这种结构类似于有拓つぶせ扑序的てき图，每まい个节点てん是ぜ其之前まえ的てき节点的てき后きさき继、分ぶん支ささえ、子こ节点等とう。树的结构中ちゅう，每まい个节点てん之の前まえ的てき节点是ぜ唯一ゆいいつ的てき（就是说有唯一ゆいいつ的てき前ぜん驱、上うえ层容器き、父ちち节点等とう），另外每ごと一个节点及其后面的部分也都是一棵树。

作さく为数据すえ结构[编辑]

树也是ぜ一类重要的数据结构，同どう时也有ゆう逻辑结构的てき性せい质，通常つうじょう也是有ゆう根ね树。主要しゅよう有ゆう搜索そうさく树和わ堆うずたか两种，前者ぜんしゃ的てき内容ないよう是ぜ按中序じょ遍へん历的顺序排はい序じょ的てき，后きさき者しゃ每ごと个节点てん的てき关键字じ都と比ひ它的子こ节点大だい（或ある者もの小しょう）。复杂度ど一般いっぱん在ざい树的高度こうど，也就是ぜO(nlogn)以内いない。

搜索そうさく树可か以快速そく的てき查找有ゆう序じょ的てき内容ないよう或ある者もの新しん内容ないよう在ざい已やめ有ゆう内容ないよう中ちゅう的てき位置いち，也可以进行ぎょう一些和按这个顺序的范围有关的统计。

堆うずたか (数かず据すえ结构)是ぜ一いち种优先队列，比ひ搜索そうさく树功能のう少しょう，通常つうじょう只ただ能のう很方便びん的てき求もとめ堆うずたか中なか关键字じ最小さいしょう（最大さいだい）的てき数すう据すえ，不能ふのう查找。（当然とうぜん有ゆう的てき时候求もとめ次じ小和おわ第だい三小也是很方便的）

很多这类数すう据すえ结构会かい给每个点或ある者もの边加上じょう一いち些别的てき参さん数すう。有ゆう些数据すえ结构还会破やぶ坏本来ほんらい的てき树的结构，但ただし是ぜ基本きほん还是用よう的てき树的模も式しき，一般还是叫做“树”。

树的类型[编辑]