整合營銷服務商
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
電腦端+手機端+微信端=數據同步管理
免費咨詢熱線：
ML 文檔形成了一種樹結構，它從"根部"開始，然后擴展到"枝葉"。
一個 XML 文檔實例
XML 文檔使用簡單的具有自我描述性的語法：
<?xmlversion="1.0"encoding="UTF-8"?><note><to>Tove</to><from>Jani</from><heading>Reminder</heading><body>Don't forget me this weekend!</body></note>
第一行是 XML 聲明。它定義 XML 的版本（1.0）和所使用的編碼（UTF-8 : 萬國碼, 可顯示各種語言）。
下一行描述文檔的根元素（像在說："本文檔是一個便簽"）：
<note>
接下來 4 行描述根的 4 個子元素（to, from, heading 以及 body）：
<to>Tove</to><from>Jani</from><heading>Reminder</heading><body>Don't forget me this weekend!</body>
最后一行定義根元素的結尾：
</note>
您可以假設，從這個實例中，XML 文檔包含了一張 Jani 寫給 Tove 的便簽。
XML 具有出色的自我描述性，您同意嗎？
XML 文檔形成一種樹結構
XML 文檔必須包含根元素。該元素是所有其他元素的父元素。
XML 文檔中的元素形成了一棵文檔樹。這棵樹從根部開始，并擴展到樹的最底端。
所有的元素都可以有子元素：
<root><child><subchild>.....</subchild></child></root>
父、子以及同胞等術語用于描述元素之間的關系。父元素擁有子元素。相同層級上的子元素成為同胞（兄弟或姐妹）。
所有的元素都可以有文本內容和屬性（類似 HTML 中）。
實例：
上圖表示下面的 XML 中的一本書：
XML 文檔實例
<bookstore><bookcategory="COOKING"><titlelang="en">Everyday Italian</title><author>Giada De Laurentiis</author><year>2005</year><price>30.00</price></book><bookcategory="CHILDREN"><titlelang="en">Harry Potter</title><author>J K. Rowling</author><year>2005</year><price>29.99</price></book><bookcategory="WEB"><titlelang="en">Learning XML</title><author>Erik T. Ray</author><year>2003</year><price>39.95</price></book></bookstore>
實例中的根元素是 <bookstore>。文檔中的所有 <book> 元素都被包含在 <bookstore> 中。
<book> 元素有 4 個子元素：<title>、<author>、<year>、<price>。
是一種抽象的數據結構，乍一聽，就給人一種晦澀難懂的感覺，也確實如此，因為它的表現形式不像線性表那樣那么直觀。但是樹結構太重要了，生活中常見的：文件的目錄，族譜都是基于樹結構；編程中常見的，數據庫的索引，數據的快速定位等也是基于樹結構，而且也有超級多的有關樹結構的面試題。下面進入主題
前幾篇分享的都是線性表數據結構，特點就是所有的項都有一個前驅，并且除了最后一項，每個數據也都擁有一個后繼項。而在樹結構中，前驅和后繼項的概念也存在，只不過改個名，叫做父節點和子節點。
我們可以想象一下現實中的大樹，每棵樹都有樹干，樹枝，樹葉等結構，新的樹枝，樹葉永遠都是從已經存在的樹枝，樹葉中生長而來。我們可以想象，從樹根到每一片樹葉都有固定且唯一的一條路徑，而路徑上可能會呈現出不同的數據特點，路徑還包含著層級的關系，我們根據這種特點，將路徑上的數據抽象成自己所要的特點，樹的結構就誕生了
說到這，對于剛接觸的朋友們來說，肯定還是蒙的，所以我們先介紹下術語。
樹是由節點（Node）和邊（Edge）組成的，將一個父節點連接到其子節點的線，從（樹的結構）上往下看，針對這條邊，上面的節點是這個邊的出邊，下面的節點是這個邊的入邊
一個節點是其所有出邊所連接節點的父節點，一個節點只能有一個父節點
入邊均來自于同一個節點的若干節點，稱之為這個節點的子節點
具有同一個父節點的節點之間稱之為兄弟節點
沒有子節點的節點稱之為葉節點
一個節點的深度或者層級數等于將其連接到根節點的路徑的長度，根節點深度為0
樹中的最長的路徑的長度（葉子節點的最大層級數）。最大層數即為樹的高度，根節點的高度為0
由邊依次連接在一起的節點可以看成是一個有序的列表
一個節點的子節點，以及其子節點的子節點，以此類推
<!-- html包含body和head兩大塊，body又包含其他，呈樹形呈現 -->
<!DOCTYPE html>
<html>
<head>
<title></title>
</head>
<body>
<h1>hello,world</h1>
</body>
</html>樹結構一般性特征說到這就差不多了，接下來介紹樹結構中最重要的一種：二叉樹。
一棵樹， 如果每個節點最多有兩個子樹，就稱之為二叉樹。
二叉樹是n個節點的有限集合：該集合可以為空集（稱為空二叉樹），也可以由一個根節點和兩棵互不相交的，分別稱為根節點的 左子樹和右子樹組成
除了最后一個層級，其他的每一層都包含了完整的節點(每個節點都有兩個子節點)
二叉樹的這些特點都是后面理解二叉樹應用的關鍵，接下來分享二叉樹的實現(基于python)，基于列表和鏈表
還是那句話：二叉樹是一種邏輯結構，物理結構怎樣實現取決于操作者，先分享數組實現的二叉樹，不推薦數組，比較麻煩，且占用內存大。
# r為根節點，另外兩個空列表分別代表左子節點盒右子結點
def binary_tree(r):
return [r, [], []]
#
def insert_left(root, new_branch):
# 先定位左子節點
t = root.pop(1)
# 已經存在左子節點
if len(t) > 1:
root.insert(1, [new_branch, t, []])
else:
# 不存在左子節點
root.insert(1,[new_branch, [], []])
return root
def insert_right(root, new_branch):
t = root.pop(2)
if len(t) > 1:
root.insert(2, [new_branch, [], [t]])
else:
root.insert(2,[new_branch, [], []])
return root
def get_root(root):
return root[0]
def set_root(root, data):
root[0] = data
def get_left_child(root):
return root[1]
def get_right_child(root):
return root[2]
# 測試都是往根節點插入
r = binary_tree(3)
insert_left(r,4)
insert_left(r,5)
insert_right(r,6)
insert_right(r,7)
l = get_left_child(r)
print(r)鏈表的實現要優于數組實現，更推薦，我們來看下如何實現
# 用鏈表實現的二叉樹
class BinaryTree(object):
def __init__(self, root):
self.key = root
self.left_child = None
self.right_child = None
def insert_left(self, data):
if self.left_child == None:
self.left_child = BinaryTree(data)
else:
t = BinaryTree(data)
t.left_child = self.left_child
self.left_child = t
def insert_right(self, data):
if self.right_child == None:
self.right_child = BinaryTree(data)
else:
t = BinaryTree(data)
t.right_child = self.right_child
self.right_child = t
def get_right_child(self):
return self.right_child
def get_left_child(self):
return self.left_child
# 取出當前結點的數據
def get_root(self):
return self.key
# 設置當前結點的值
def set_root(self, value):
self.key = value
# 前序遍歷，這里只是為了展示結果用
def pre_order(tree):
if tree:
print(tree.get_root())
pre_order(tree.get_left_child())
pre_order(tree.get_right_child())
# 生成二叉樹的結構
tree = BinaryTree(0)
tree.insert_left(3)
tree.insert_left(1)
tree.get_left_child().insert_right(4)
tree.insert_right(6)
tree.insert_right(2)
pre_order(tree)本篇主要介紹了樹結構的一般特性，二叉樹的幾種變體以及二叉樹的基于python的實現。希望你對樹結構能有一個初步的了解，當然，樹結構還沒有說完，比如樹的幾種遍歷模式，樹的一些經典應用等等，這些會放到下篇文章分享。
我是一名奮戰在編程界的pythoner，工作中既要和數據打交道，也要和erp系統，web網站保持友好的溝通……時不時的會分享一些提高效率的編程小技巧，在實際應用中遇到的問題以及解決方案，或者源碼的閱讀等等，歡迎大家一起來討論！如果覺得寫得還不錯，歡迎關注點贊，謝謝
*請認真填寫需求信息，我們會在24小時內與您取得聯系。
