二叉排列樹，二叉搜索樹

這個數聽見得比較多，含義是：左邊<=中間<=右邊，換句話來說使用中序遍歷最后得到結果就是一個有序得序列。

建立一顆二叉排列樹

class BinTNode:def __init__(self,data=None,left =None,right =None):self.data =dataself.left =leftself.right =rightdef buildTree(arr,pointer,N):# 遞歸出口，當越界時就沒有必要創建節點了直接return，開始回退# 當值為-1時，也沒有必要創建結點if pointer > N or arr[pointer] == -1:return NonecurNode = BinTNode(arr[pointer])curNode.left = buildTree(arr,2*pointer+1,N)curNode.right = buildTree(arr,2*pointer+2,N)return curNodedef inorder(root):if not root:returnelse:inorder(root.left)print(root.data,end=' ')inorder(root.right)arr = [6,2,8,0,4,7,9,-1,-1,3,5] root = buildTree(arr,0,len(arr)-1) inorder(root)runfile('D:/share/test/backtracking/Binary_Search_Tree.py', wdir='D:/share/test/backtracking') 0 2 3 4 5 6 7 8 9

二叉排列樹搜索，他可以天然的使用二叉搜索，通過比較要么在左子樹，要么在右子樹，要么在當前結點

def inorder(root):if not root:returnelse:inorder(root.left)print(root.data,end=' ')inorder(root.right)def searchInBinaryTree(root,node_key):if not root:return Falseif root.data == node_key:return Trueelif root.data < node_key:return searchInBinaryTree(root.right,node_key) else:return searchInBinaryTree(root.left,node_key)

二叉樹的共同祖先，二叉樹的祖先有4種情況，第一種：全部都在一個子樹，第二種：每一顆子樹一個，第三種：當前結點就是祖先，第四種：就是沒有祖先的情況，由于二叉排列樹的性質，可以直接區分這四種情況：

class Solution:def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode data:type q: TreeNode data:rtype: TreeNode"""if not root or root.data == p or root.data == q:return rootif root.data < p and root.data < q:return self.lowestCommonAncestor(root.right, p, q)elif root.data > p and root.data > q:return self.lowestCommonAncestor(root.left, p, q) # 一邊一個的情況else:return root # 化簡修改后如下 ，這里面實際上假設2個結點都存在 class Solution:def lowestCommonAncestor(self, root, p, q):""":type root: TreeNode:type p: TreeNode data:type q: TreeNode data:rtype: TreeNode""" if root.data < p and root.data < q:return self.lowestCommonAncestor(root.right, p, q)elif root.data > p and root.data > q:return self.lowestCommonAncestor(root.left, p, q) # 實際上這個包含多種請款：# not root or root.data == p or root.data == q 和 root.data在p,q之間else:return root # 這里是樹形指針的一種用方法，是把遞歸轉化為迭代的一種常用方法def lowestCommonAncestorRecursion(self, root, p, q):pointer = rootwhile pointer:if pointer.data < p and pointer.data < q:pointer = pointer.rightelif pointer.data > p and pointer.data > q:pointer = pointer.left else:return pointer

運行結果：

arr = [6,2,8,0,4,7,9,-1,-1,3,5] root = buildTree(arr,0,len(arr)-1) inorder(root) print(searchInBinaryTree(root,9)) t = Solution().lowestCommonAncestorRecursion(root,3,5) print(t.data if t else t)runfile('D:/share/test/backtracking/Binary_Search_Tree.py', wdir='D:/share/test/backtracking') 0 2 3 4 5 6 7 8 9 True 4

總結

以上是生活随笔為你收集整理的树形结构：二叉排列树，二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。