如何創建二分查找樹？

假設我有一個數組說如何創建二分查找樹？

1 5 4 6 8 9 10 22 17 7 9 3

我想從這個數組創建一個二叉搜索樹。我需要算法來理解這一點。

我已閱讀有關BST像inorder traversalpreorderpostorder，tree walk，剩下其他的事情insertion deletion等

書沒有提供如何創建BST。需要幫助這裏

來源

2014-02-23 Nitesh

嘗試平衡二叉樹，http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree之前排序。 – aquemini

我想你是在學習樹的開始，現在不在乎平衡。 –

@GökhanÇoban：對。剛開始學習樹木。書中有些東西不清楚。所以在這裏張貼 – Nitesh

，如果你不關心的樹被平衡很簡單：

把樹的第一個元素的頭。
遍歷數組。如果一個元素比節點大一個左邊（對左邊的孩子重複該步驟），否則右邊（對右邊的孩子重複該步驟）。
如果左/右子元素爲null，則在那裏插入新值。

保證產生二叉搜索樹 - 只是不平衡。

來源

2014-02-23 08:50:45 WeaselFox

thanx的答案，但如何有平衡樹？ – Nitesh

看這裏：http://en.wikipedia.org/wiki/Red%E2%80%93black_tree - 維基鏈接完成僞代碼。祝你好運 – WeaselFox

但假設第一個元素是'1'，那麼它不會創建任何樹 – Nitesh

首先，你應該爲你的BST選擇一個根節點。一旦你選擇了一個根節點，考慮到以下事實構建BST已經很簡單：左邊的子節點小於父節點，所有正確的子節點大於父節點。

private Node root; 

public void insert(int val) { 
    if (root == null) { 
     root = new Node(val); 
    } else { 
     insertHelper(root, val); 
    } 
} 

private void insertHelper(Node node, int val) { 
    if (val < node.val) { 
     if (node.left == null) { 
      node.left = new Node(val); 
     } else { 
      insertHelper(node.left, val); 
     } 
    } else if (node.val < val) { 
     if (node.right == null) { 
      node.right = new Node(val); 
     } else { 
      insertHelper(node.right, val); 
     } 
    } 
}

來源

2014-02-23 08:53:50

如何選擇根節點。 – Nitesh

這取決於你。你可以根據情況選擇你想要的任何根節點。當然，樹的結構取決於你選擇的根節點。 –

如果給定的數組進行排序，你可以做到以下幾點：

以數組的中間元素，使之樹
根以左子數組並使其成爲遞歸的根的左子樹
取右邊的子數組並使其成爲遞歸的根的右子樹

否則，你總是可以在陣列應用程序

 struct node* construct(int arr[], int start, int end) 
{ 
    if(start>end) 
     return; 
    else if (start==end) 
    { 
    /*assuming we have a function newNode(int) which creates a new BST Node*/ 
     node* Node = newNode(arr[start]); 
     return Node; 
    } 
    int mid = (start+end)/2; 
    node* root = newNode(arr[mid]); 
    root->left = construct(arr,start,mid-1); 
    root->right = construct(arr,mid+1,end); 
    return root; 
}

來源

2014-03-19 05:34:43 AgentX

如何創建二分查找樹？

回答

相關問題