二叉搜索樹的構(gòu)建與遍歷方法一、概述

二叉搜索樹（BinarySearchTree,BST）是一種基于節(jié)點(diǎn)值的有序二叉樹，其中每個(gè)節(jié)點(diǎn)滿足以下性質(zhì)：

-左子樹中所有節(jié)點(diǎn)的值小于該節(jié)點(diǎn)的值。

-右子樹中所有節(jié)點(diǎn)的值大于該節(jié)點(diǎn)的值。

-左右子樹均為二叉搜索樹。

二叉搜索樹支持高效的插入、刪除和查找操作，平均時(shí)間復(fù)雜度為O(logn)，但在最壞情況下（樹退化成鏈表）為O(n)。本文檔將詳細(xì)介紹二叉搜索樹的構(gòu)建方法和常見遍歷方式。

二、二叉搜索樹的構(gòu)建

構(gòu)建二叉搜索樹通常通過逐個(gè)插入節(jié)點(diǎn)實(shí)現(xiàn)。以下是構(gòu)建步驟：

（一）定義節(jié)點(diǎn)結(jié)構(gòu)

首先定義二叉搜索樹的節(jié)點(diǎn)類，包含值、左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

classTreeNode:

def__init__(self,value):

self.value=value

self.left=None

self.right=None

（二）插入節(jié)點(diǎn)

插入節(jié)點(diǎn)時(shí)，從根節(jié)點(diǎn)開始比較當(dāng)前值，若待插入值小于當(dāng)前節(jié)點(diǎn)值，則向左子樹遞歸；大于則向右子樹遞歸。若子樹為空，則創(chuàng)建新節(jié)點(diǎn)。

1.插入步驟：

(1)若樹為空，新節(jié)點(diǎn)為根節(jié)點(diǎn)。

(2)若新值小于當(dāng)前節(jié)點(diǎn)值，移動(dòng)到左子節(jié)點(diǎn)，重復(fù)比較。

(3)若新值大于當(dāng)前節(jié)點(diǎn)值，移動(dòng)到右子節(jié)點(diǎn)，重復(fù)比較。

(4)找到空位置插入新節(jié)點(diǎn)。

2.示例代碼：

definsert_node(root,value):

ifrootisNone:

returnTreeNode(value)

ifvalue<root.value:

root.left=insert_node(root.left,value)

else:

root.right=insert_node(root.right,value)

returnroot

（三）構(gòu)建示例

以序列[8,3,10,1,6,14,4,7,13]為例，構(gòu)建二叉搜索樹：

1.插入8，根節(jié)點(diǎn)為8。

2.插入3，小于8，插入左子樹。

3.插入10，大于8，插入右子樹。

4.插入1，小于8且小于3，插入3的左子樹。

5.插入6，大于3且小于8，插入3的右子樹。

6.插入14，大于8且大于10，插入10的右子樹。

7.插入4，大于3且小于6，插入6的左子樹。

8.插入7，大于6且小于8，插入6的右子樹。

9.插入13，大于10且小于14，插入14的左子樹。

三、二叉搜索樹的遍歷

遍歷二叉搜索樹有三種常見方式：前序遍歷、中序遍歷和后序遍歷。

（一）前序遍歷（根-左-右）

訪問當(dāng)前節(jié)點(diǎn)，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹。

1.步驟：

(1)訪問根節(jié)點(diǎn)。

(2)遍歷左子樹。

(3)遍歷右子樹。

2.示例序列（上述構(gòu)建的樹）：8,3,1,6,4,7,10,14,13

（二）中序遍歷（左-根-右）

遞歸遍歷左子樹，訪問當(dāng)前節(jié)點(diǎn)，最后遞歸遍歷右子樹。中序遍歷可按升序輸出節(jié)點(diǎn)值。

1.步驟：

(1)遍歷左子樹。

(2)訪問根節(jié)點(diǎn)。

(3)遍歷右子樹。

2.示例序列：1,3,4,6,7,8,10,13,14

（三）后序遍歷（左-右-根）

遞歸遍歷左子樹，遞歸遍歷右子樹，最后訪問當(dāng)前節(jié)點(diǎn)。

1.步驟：

(1)遍歷左子樹。

(2)遍歷右子樹。

(3)訪問根節(jié)點(diǎn)。

2.示例序列：1,4,7,6,3,13,14,10,8

（四）遍歷代碼示例

```python

definorder_traversal(root):

ifrootisNone:

return[]

returninorder_traversal(root.left)+[root.value]+inorder_traversal(root.right)

四、總結(jié)

二叉搜索樹通過有序結(jié)構(gòu)實(shí)現(xiàn)高效查找，其構(gòu)建和遍歷方法需嚴(yán)格遵循節(jié)點(diǎn)性質(zhì)。前序、中序、后序遍歷各有應(yīng)用場(chǎng)景，中序遍歷可輸出有序序列。實(shí)際應(yīng)用中需注意樹的平衡性，以避免性能退化。

一、概述

二叉搜索樹（BinarySearchTree,BST）是一種基于節(jié)點(diǎn)值的有序二叉樹，其中每個(gè)節(jié)點(diǎn)滿足以下性質(zhì)：

-左子樹中所有節(jié)點(diǎn)的值小于該節(jié)點(diǎn)的值。

-右子樹中所有節(jié)點(diǎn)的值大于該節(jié)點(diǎn)的值。

-左右子樹均為二叉搜索樹。

二叉搜索樹支持高效的插入、刪除和查找操作，平均時(shí)間復(fù)雜度為O(logn)，但在最壞情況下（樹退化成鏈表）為O(n)。本文檔將詳細(xì)介紹二叉搜索樹的構(gòu)建方法和常見遍歷方式。

二、二叉搜索樹的構(gòu)建

構(gòu)建二叉搜索樹通常通過逐個(gè)插入節(jié)點(diǎn)實(shí)現(xiàn)。以下是構(gòu)建步驟：

（一）定義節(jié)點(diǎn)結(jié)構(gòu)

首先定義二叉搜索樹的節(jié)點(diǎn)類，包含值、左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。節(jié)點(diǎn)結(jié)構(gòu)是二叉搜索樹的基礎(chǔ)，確保每個(gè)節(jié)點(diǎn)都能正確存儲(chǔ)和指向其子節(jié)點(diǎn)。

classTreeNode:

def__init__(self,value):

self.value=value節(jié)點(diǎn)存儲(chǔ)的值

self.left=None指向左子節(jié)點(diǎn)的引用

self.right=None指向右子節(jié)點(diǎn)的引用

（二）插入節(jié)點(diǎn)

插入節(jié)點(diǎn)時(shí)，從根節(jié)點(diǎn)開始比較當(dāng)前值，若待插入值小于當(dāng)前節(jié)點(diǎn)值，則向左子樹遞歸；大于則向右子樹遞歸。若子樹為空，則創(chuàng)建新節(jié)點(diǎn)。插入操作需確保樹的性質(zhì)不被破壞。

1.插入步驟：

(1)若樹為空（即根節(jié)點(diǎn)為None），新節(jié)點(diǎn)即為根節(jié)點(diǎn)。

(2)若待插入值小于當(dāng)前節(jié)點(diǎn)值，移動(dòng)到左子節(jié)點(diǎn)，重復(fù)比較。

(3)若待插入值大于當(dāng)前節(jié)點(diǎn)值，移動(dòng)到右子節(jié)點(diǎn)，重復(fù)比較。

(4)當(dāng)找到空子節(jié)點(diǎn)位置時(shí)，創(chuàng)建新節(jié)點(diǎn)并插入。

2.示例代碼：

```python

definsert_node(root,value):

ifrootisNone:

returnTreeNode(value)

ifvalue<root.value:

root.left=insert_node(root.left,value)

else:

root.right=insert_node(root.right,value)

returnroot

```

3.插入操作注意事項(xiàng)：

-插入時(shí)需忽略重復(fù)值，或根據(jù)需求決定是否允許重復(fù)。

-每次插入后需保持左子樹和右子樹的性質(zhì)。

（三）構(gòu)建示例

以序列[8,3,10,1,6,14,4,7,13]為例，逐步構(gòu)建二叉搜索樹：

1.插入8，根節(jié)點(diǎn)為8。樹結(jié)構(gòu)：`8`

2.插入3，小于8，插入左子樹。樹結(jié)構(gòu)：

```

8

/\

3?

```

3.插入10，大于8，插入右子樹。樹結(jié)構(gòu)：

```

8

/\

310

```

4.插入1，小于8且小于3，插入3的左子樹。樹結(jié)構(gòu)：

```

8

/\

310

/

1

```

5.插入6，大于3且小于8，插入3的右子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

```

6.插入14，大于8且大于10，插入10的右子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

\

14

```

7.插入4，大于3且小于6，插入6的左子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

/\

4

```

8.插入7，大于6且小于8，插入6的右子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

/\

47

```

9.插入13，大于10且小于14，插入14的左子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

/\

47

\

14

/

13

```

三、二叉搜索樹的遍歷

遍歷二叉搜索樹有三種常見方式：前序遍歷、中序遍歷和后序遍歷。每種遍歷方式都有其特定順序和用途，例如中序遍歷可按升序輸出節(jié)點(diǎn)值。

（一）前序遍歷（根-左-右）

訪問當(dāng)前節(jié)點(diǎn)，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹。前序遍歷常用于復(fù)制樹或刪除樹的遞歸實(shí)現(xiàn)。

1.步驟：

(1)訪問根節(jié)點(diǎn)（輸出或處理節(jié)點(diǎn)值）。

(2)遞歸遍歷左子樹。

(3)遞歸遍歷右子樹。

2.示例序列（上述構(gòu)建的樹）：8,3,1,6,4,7,10,14,13

3.示例代碼：

```python

defpreorder_traversal(root):

ifrootisNone:

return[]

return[root.value]+preorder_traversal(root.left)+preorder_traversal(root.right)

```

（二）中序遍歷（左-根-右）

遞歸遍歷左子樹，訪問當(dāng)前節(jié)點(diǎn)，最后遞歸遍歷右子樹。中序遍歷可按升序輸出節(jié)點(diǎn)值，適用于需要有序數(shù)據(jù)的場(chǎng)景。

1.步驟：

(1)遞歸遍歷左子樹。

(2)訪問根節(jié)點(diǎn)（輸出或處理節(jié)點(diǎn)值）。

(3)遞歸遍歷右子樹。

2.示例序列：1,3,4,6,7,8,10,13,14

3.示例代碼：

```python

definorder_traversal(root):

ifrootisNone:

return[]

returninorder_traversal(root.left)+[root.value]+inorder_traversal(root.right)

```

（三）后序遍歷（左-右-根）

遞歸遍歷左子樹，遞歸遍歷右子樹，最后訪問當(dāng)前節(jié)點(diǎn)。后序遍歷常用于刪除樹，因?yàn)槠湎忍幚碜庸?jié)點(diǎn)再處理父節(jié)點(diǎn)。

1.步驟：

(1)遞歸遍歷左子樹。

(2)遞歸遍歷右子樹。

(3)訪問根節(jié)點(diǎn)（輸出或處理節(jié)點(diǎn)值）。

2.示例序列：1,4,7,6,3,13,14,10,8

3.示例代碼：

```python

defpostorder_traversal(root):

ifrootisNone:

return[]

returnpostorder_traversal(root.left)+postorder_traversal(root.right)+[root.value]

```

（四）遍歷應(yīng)用場(chǎng)景

1.中序遍歷：

-輸出有序序列（如排序）。

-查找特定值（按順序遍歷）。

2.前序遍歷：

-復(fù)制樹結(jié)構(gòu)。

-刪除樹（先處理子節(jié)點(diǎn)）。

3.后序遍歷：

-刪除樹（先處理子節(jié)點(diǎn)）。

-計(jì)算表達(dá)式（先處理子節(jié)點(diǎn)）。

（五）遍歷代碼示例

完整遍歷實(shí)現(xiàn)（以中序遍歷為例）：

```python

definorder_traversal(root):

ifrootisNone:

return[]

result=[]

result+=inorder_traversal(root.left)

result.append(root.value)

result+=inorder_traversal(root.right)

returnresult

```

四、二叉搜索樹的優(yōu)化

常規(guī)二叉搜索樹在最壞情況下（如插入有序序列）會(huì)退化成鏈表，導(dǎo)致操作效率降低。以下是一些優(yōu)化方法：

（一）平衡二叉搜索樹

平衡二叉搜索樹通過旋轉(zhuǎn)操作保持樹的平衡，常用類型包括AVL樹和紅黑樹。

1.AVL樹：

-每個(gè)節(jié)點(diǎn)的左右子樹高度差不超過1。

-通過旋轉(zhuǎn)操作（單旋轉(zhuǎn)和雙旋轉(zhuǎn)）維護(hù)平衡。

2.紅黑樹：

-節(jié)點(diǎn)顏色為紅色或黑色。

-滿足特定性質(zhì)（如根節(jié)點(diǎn)為黑色、無紅色連續(xù)節(jié)點(diǎn)等）。

（二）B樹和B+樹

B樹和B+樹是多路搜索樹，通過增加節(jié)點(diǎn)子節(jié)點(diǎn)數(shù)量減少樹高度，適用于磁盤存儲(chǔ)。

1.B樹：

-每個(gè)節(jié)點(diǎn)有多個(gè)子節(jié)點(diǎn)。

-所有數(shù)據(jù)存儲(chǔ)在葉子節(jié)點(diǎn)。

2.B+樹：

-非葉子節(jié)點(diǎn)僅作為索引。

-所有數(shù)據(jù)存儲(chǔ)在葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)有序鏈接。

（三）應(yīng)用優(yōu)化

1.選擇合適的遍歷方式：

-查找最小/最大值時(shí)使用前序遍歷。

-需要有序數(shù)據(jù)時(shí)使用中序遍歷。

2.避免重復(fù)插入：

-插入前檢查節(jié)點(diǎn)值是否已存在。

3.使用緩存：

-對(duì)頻繁訪問的節(jié)點(diǎn)使用緩存提高效率。

五、總結(jié)

二叉搜索樹通過有序結(jié)構(gòu)實(shí)現(xiàn)高效查找，其構(gòu)建和遍歷方法需嚴(yán)格遵循節(jié)點(diǎn)性質(zhì)。前序、中序、后序遍歷各有應(yīng)用場(chǎng)景，中序遍歷可輸出有序序列。實(shí)際應(yīng)用中需注意樹的平衡性，以避免性能退化。通過平衡二叉搜索樹、B樹等優(yōu)化方法，可進(jìn)一步提升查找效率。

一、概述

二叉搜索樹（BinarySearchTree,BST）是一種基于節(jié)點(diǎn)值的有序二叉樹，其中每個(gè)節(jié)點(diǎn)滿足以下性質(zhì)：

-左子樹中所有節(jié)點(diǎn)的值小于該節(jié)點(diǎn)的值。

-右子樹中所有節(jié)點(diǎn)的值大于該節(jié)點(diǎn)的值。

-左右子樹均為二叉搜索樹。

二叉搜索樹支持高效的插入、刪除和查找操作，平均時(shí)間復(fù)雜度為O(logn)，但在最壞情況下（樹退化成鏈表）為O(n)。本文檔將詳細(xì)介紹二叉搜索樹的構(gòu)建方法和常見遍歷方式。

二、二叉搜索樹的構(gòu)建

構(gòu)建二叉搜索樹通常通過逐個(gè)插入節(jié)點(diǎn)實(shí)現(xiàn)。以下是構(gòu)建步驟：

（一）定義節(jié)點(diǎn)結(jié)構(gòu)

首先定義二叉搜索樹的節(jié)點(diǎn)類，包含值、左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

classTreeNode:

def__init__(self,value):

self.value=value

self.left=None

self.right=None

（二）插入節(jié)點(diǎn)

插入節(jié)點(diǎn)時(shí)，從根節(jié)點(diǎn)開始比較當(dāng)前值，若待插入值小于當(dāng)前節(jié)點(diǎn)值，則向左子樹遞歸；大于則向右子樹遞歸。若子樹為空，則創(chuàng)建新節(jié)點(diǎn)。

1.插入步驟：

(1)若樹為空，新節(jié)點(diǎn)為根節(jié)點(diǎn)。

(2)若新值小于當(dāng)前節(jié)點(diǎn)值，移動(dòng)到左子節(jié)點(diǎn)，重復(fù)比較。

(3)若新值大于當(dāng)前節(jié)點(diǎn)值，移動(dòng)到右子節(jié)點(diǎn)，重復(fù)比較。

(4)找到空位置插入新節(jié)點(diǎn)。

2.示例代碼：

definsert_node(root,value):

ifrootisNone:

returnTreeNode(value)

ifvalue<root.value:

root.left=insert_node(root.left,value)

else:

root.right=insert_node(root.right,value)

returnroot

（三）構(gòu)建示例

以序列[8,3,10,1,6,14,4,7,13]為例，構(gòu)建二叉搜索樹：

1.插入8，根節(jié)點(diǎn)為8。

2.插入3，小于8，插入左子樹。

3.插入10，大于8，插入右子樹。

4.插入1，小于8且小于3，插入3的左子樹。

5.插入6，大于3且小于8，插入3的右子樹。

6.插入14，大于8且大于10，插入10的右子樹。

7.插入4，大于3且小于6，插入6的左子樹。

8.插入7，大于6且小于8，插入6的右子樹。

9.插入13，大于10且小于14，插入14的左子樹。

三、二叉搜索樹的遍歷

遍歷二叉搜索樹有三種常見方式：前序遍歷、中序遍歷和后序遍歷。

（一）前序遍歷（根-左-右）

訪問當(dāng)前節(jié)點(diǎn)，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹。

1.步驟：

(1)訪問根節(jié)點(diǎn)。

(2)遍歷左子樹。

(3)遍歷右子樹。

2.示例序列（上述構(gòu)建的樹）：8,3,1,6,4,7,10,14,13

（二）中序遍歷（左-根-右）

遞歸遍歷左子樹，訪問當(dāng)前節(jié)點(diǎn)，最后遞歸遍歷右子樹。中序遍歷可按升序輸出節(jié)點(diǎn)值。

1.步驟：

(1)遍歷左子樹。

(2)訪問根節(jié)點(diǎn)。

(3)遍歷右子樹。

2.示例序列：1,3,4,6,7,8,10,13,14

（三）后序遍歷（左-右-根）

遞歸遍歷左子樹，遞歸遍歷右子樹，最后訪問當(dāng)前節(jié)點(diǎn)。

1.步驟：

(1)遍歷左子樹。

(2)遍歷右子樹。

(3)訪問根節(jié)點(diǎn)。

2.示例序列：1,4,7,6,3,13,14,10,8

（四）遍歷代碼示例

```python

definorder_traversal(root):

ifrootisNone:

return[]

returninorder_traversal(root.left)+[root.value]+inorder_traversal(root.right)

四、總結(jié)

二叉搜索樹通過有序結(jié)構(gòu)實(shí)現(xiàn)高效查找，其構(gòu)建和遍歷方法需嚴(yán)格遵循節(jié)點(diǎn)性質(zhì)。前序、中序、后序遍歷各有應(yīng)用場(chǎng)景，中序遍歷可輸出有序序列。實(shí)際應(yīng)用中需注意樹的平衡性，以避免性能退化。

一、概述

二叉搜索樹（BinarySearchTree,BST）是一種基于節(jié)點(diǎn)值的有序二叉樹，其中每個(gè)節(jié)點(diǎn)滿足以下性質(zhì)：

-左子樹中所有節(jié)點(diǎn)的值小于該節(jié)點(diǎn)的值。

-右子樹中所有節(jié)點(diǎn)的值大于該節(jié)點(diǎn)的值。

-左右子樹均為二叉搜索樹。

二叉搜索樹支持高效的插入、刪除和查找操作，平均時(shí)間復(fù)雜度為O(logn)，但在最壞情況下（樹退化成鏈表）為O(n)。本文檔將詳細(xì)介紹二叉搜索樹的構(gòu)建方法和常見遍歷方式。

二、二叉搜索樹的構(gòu)建

構(gòu)建二叉搜索樹通常通過逐個(gè)插入節(jié)點(diǎn)實(shí)現(xiàn)。以下是構(gòu)建步驟：

（一）定義節(jié)點(diǎn)結(jié)構(gòu)

首先定義二叉搜索樹的節(jié)點(diǎn)類，包含值、左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。節(jié)點(diǎn)結(jié)構(gòu)是二叉搜索樹的基礎(chǔ)，確保每個(gè)節(jié)點(diǎn)都能正確存儲(chǔ)和指向其子節(jié)點(diǎn)。

classTreeNode:

def__init__(self,value):

self.value=value節(jié)點(diǎn)存儲(chǔ)的值

self.left=None指向左子節(jié)點(diǎn)的引用

self.right=None指向右子節(jié)點(diǎn)的引用

（二）插入節(jié)點(diǎn)

插入節(jié)點(diǎn)時(shí)，從根節(jié)點(diǎn)開始比較當(dāng)前值，若待插入值小于當(dāng)前節(jié)點(diǎn)值，則向左子樹遞歸；大于則向右子樹遞歸。若子樹為空，則創(chuàng)建新節(jié)點(diǎn)。插入操作需確保樹的性質(zhì)不被破壞。

1.插入步驟：

(1)若樹為空（即根節(jié)點(diǎn)為None），新節(jié)點(diǎn)即為根節(jié)點(diǎn)。

(2)若待插入值小于當(dāng)前節(jié)點(diǎn)值，移動(dòng)到左子節(jié)點(diǎn)，重復(fù)比較。

(3)若待插入值大于當(dāng)前節(jié)點(diǎn)值，移動(dòng)到右子節(jié)點(diǎn)，重復(fù)比較。

(4)當(dāng)找到空子節(jié)點(diǎn)位置時(shí)，創(chuàng)建新節(jié)點(diǎn)并插入。

2.示例代碼：

```python

definsert_node(root,value):

ifrootisNone:

returnTreeNode(value)

ifvalue<root.value:

root.left=insert_node(root.left,value)

else:

root.right=insert_node(root.right,value)

returnroot

```

3.插入操作注意事項(xiàng)：

-插入時(shí)需忽略重復(fù)值，或根據(jù)需求決定是否允許重復(fù)。

-每次插入后需保持左子樹和右子樹的性質(zhì)。

（三）構(gòu)建示例

以序列[8,3,10,1,6,14,4,7,13]為例，逐步構(gòu)建二叉搜索樹：

1.插入8，根節(jié)點(diǎn)為8。樹結(jié)構(gòu)：`8`

2.插入3，小于8，插入左子樹。樹結(jié)構(gòu)：

```

8

/\

3?

```

3.插入10，大于8，插入右子樹。樹結(jié)構(gòu)：

```

8

/\

310

```

4.插入1，小于8且小于3，插入3的左子樹。樹結(jié)構(gòu)：

```

8

/\

310

/

1

```

5.插入6，大于3且小于8，插入3的右子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

```

6.插入14，大于8且大于10，插入10的右子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

\

14

```

7.插入4，大于3且小于6，插入6的左子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

/\

4

```

8.插入7，大于6且小于8，插入6的右子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

/\

47

```

9.插入13，大于10且小于14，插入14的左子樹。樹結(jié)構(gòu)：

```

8

/\

310

/\

16

/\

47

\

14

/

13

```

三、二叉搜索樹的遍歷

遍歷二叉搜索樹有三種常見方式：前序遍歷、中序遍歷和后序遍歷。每種遍歷方式都有其特定順序和用途，例如中序遍歷可按升序輸出節(jié)點(diǎn)值。

（一）前序遍歷（根-左-右）

訪問當(dāng)前節(jié)點(diǎn)，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹。前序遍歷常用于復(fù)制樹或刪除樹的遞歸實(shí)現(xiàn)。

1.步驟：

(1)訪問根節(jié)點(diǎn)（輸出或處理節(jié)點(diǎn)值）。

(2)遞歸遍歷左子樹。

(3)遞歸遍歷右子樹。

2.示例序列（上述構(gòu)建的樹）：8,3,1,6,4,7,10,14,13

3.示例代碼：

```python

defpreorder_traversal(root):

ifrootisNone:

return[]

return[root.value]+preorder_traversal(root.left)+preorder_traversal(root.right)

```

（二）中序遍歷（左-根-右）

遞歸遍歷左子樹，訪問當(dāng)前節(jié)點(diǎn)，最后遞歸遍歷右子樹。中序遍歷可按升序輸出節(jié)點(diǎn)值，適用于需要有序數(shù)據(jù)的場(chǎng)景。

1.步驟：

(1)遞歸遍歷左子樹。

(2)訪問根節(jié)點(diǎn)（輸出或處理節(jié)點(diǎn)值）。

(3)遞歸遍歷右子樹。

2.示例序列：1,3,4,6,7,8,10,13,14

3.示例代碼：

```python

definorder_traversal(root):

ifrootisNone:

return[]

returninorder_traversal(root.left)+[root.value]+inorder_traversal(root.right)

```

（三）后序遍歷（左-右-根）

遞歸遍歷左子樹，遞歸遍歷右子樹，最后訪問當(dāng)前節(jié)點(diǎn)。后序遍歷常用于刪除樹，因?yàn)槠湎忍幚碜庸?jié)點(diǎn)再處理父節(jié)點(diǎn)。

1.步驟：

(1)遞歸遍歷左子樹。

(2)遞歸遍歷右子樹。

(3)訪問根節(jié)點(diǎn)（輸出或處理節(jié)點(diǎn)值）。

2.示例序列：1,4,7,6,3,13,14,10,8

3.示例代碼：

```python

defpostorder_traversal(root):

ifrootisNo