這篇文章主要講解了“怎么使用Java遞歸推出給定節(jié)點(diǎn)數(shù)的所有形狀二叉搜索樹”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“怎么使用Java遞歸推出給定節(jié)點(diǎn)數(shù)的所有形狀二叉搜索樹”吧！

樂都網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、自適應(yīng)網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)建站從2013年創(chuàng)立到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)建站。

題目：給定節(jié)點(diǎn)，比如3，三個(gè)節(jié)點(diǎn)；返回一個(gè)隊(duì)列，包括所有形狀二叉搜索樹（Binary Search Trees)。具體如下圖。

給出三個(gè)點(diǎn)，返回三個(gè)節(jié)點(diǎn)組成不同形狀的樹。我當(dāng)時(shí)看的時(shí)候沒有注意到是二叉搜索樹（BST)，以為是任意二叉樹，走了彎路。

這里先說下二叉搜索樹，，所謂二叉搜索樹，其實(shí)就是對(duì)于一棵二叉樹，不存在重復(fù)值節(jié)點(diǎn)，任意節(jié)點(diǎn)的左節(jié)點(diǎn)的值小于父節(jié)點(diǎn)，右節(jié)點(diǎn)大于其父節(jié)點(diǎn)。主要為了搜索方便，這樣就可以通過大小對(duì)比，只有sqrt(n)的速度搜索到某個(gè)給定值的節(jié)點(diǎn)。使用中序遍歷二叉搜索樹，可以得到一個(gè)順序數(shù)列。

因?yàn)橐婚_始沒有注意到是二叉搜索樹，所以就簡(jiǎn)單用普通二叉樹的思路。

- 使用遞歸，求n個(gè)節(jié)點(diǎn)的形狀隊(duì)列，是把n-1個(gè)節(jié)點(diǎn)形狀隊(duì)列的每個(gè)樹，可能增加的地方，增加一個(gè)節(jié)點(diǎn)，

- 可能存在增加后，圖形相同的樹，這時(shí)候使用序列化，把樹存儲(chǔ)一個(gè)字符串，并替換節(jié)點(diǎn)值為1；如果字符串相同，就是相同圖形的樹；這里使用字典來存儲(chǔ)，把序列化的字符串作為key鍵值；因?yàn)樽值涞膋ey鍵值是唯一，可以用來過濾重復(fù)樹。

- 這個(gè)時(shí)候提交代碼，發(fā)現(xiàn)不通過，才發(fā)現(xiàn)要二叉搜索樹，不想改思路了，就定義一個(gè)方法，中序遍歷那些已經(jīng)算出來的樹隊(duì)列，按照中序遍歷順序賦值。

- 提交通過，不過效率太低了。學(xué)習(xí)了下，使用動(dòng)態(tài)規(guī)劃（Dynamical Plan) 才是明路，后面會(huì)再寫一個(gè)DP方法的。

代碼如下，也算是一個(gè)反面教材。

另外這個(gè)地方還有一個(gè)注意點(diǎn)，就是深度拷貝，因?yàn)槊總€(gè)唯一圖形樹都要保存，所以保存時(shí)候用深度拷貝。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
import copy
class Solution:
    cacheDict = {1:[TreeNode('x')]}
    def buildNewTree(self, Tree):
        nodelist = [Tree]
        NewTreeDict = {}
        while nodelist != []:
            templist = []
            for node in nodelist:
                if node.left != None:
                    templist.append(node.left)
                else:
                    node.left = TreeNode('x')
                    NewTreeDict[self.buildKey(Tree)] = (copy.deepcopy(Tree))
                    node.left = None
                if node.right != None:
                    templist.append(node.right)
                else:
                    node.right = TreeNode('x')
                    NewTreeDict[self.buildKey(Tree)] = (copy.deepcopy(Tree))
                    node.right = None
            nodelist = templist
        return NewTreeDict
    
    def buildKey(self,Tree):
        Treekey = ''
        nodelist = [Tree]
        while nodelist !=[]:
            templist = []
            for node in nodelist:
                if node.left != None:
                    templist.append(node.left)
                    Treekey =  Treekey + '1'
                else:
                    Treekey = Treekey + '0'
                if node.right != None:
                    templist.append(node.right)
                    Treekey =  Treekey + '1'
                else:
                    Treekey = Treekey + '0'
            nodelist = templist
        return Treekey
    
 
    def generateXTrees(self, n):
        if n in self.cacheDict.keys():
            return self.cacheDict[n]
        else:
            TreeListDict = {}
            for Tree in self.generateXTrees(n-1):
                TreeListDict.update(self.buildNewTree(Tree))
            self.cacheDict[n] = TreeListDict.values()
            return self.cacheDict[n]
       
    def generateTrees(self, n: int):
        sortTree = []
        if n != 0:
            TreeList = self.generateXTrees(n)
            for tree in TreeList:
                sortTree.append(SortTheTree(copy.deepcopy(tree)))
        return sortTree
def SortTheTree(Tree):
    sortNum = 1
    Treelist = [Tree]
    nodePoint = Tree
    while Treelist !=[] or nodePoint.val == 'x':
        if nodePoint.left != None and nodePoint.left.val == 'x':
            nodePoint = nodePoint.left
            Treelist.append(nodePoint)
        elif nodePoint.right != None and nodePoint.right.val == 'x':
            if nodePoint.val == 'x':
                nodePoint.val = sortNum
                sortNum = sortNum + 1
            nodePoint = nodePoint.right
            Treelist.append(nodePoint)
        else:
            if nodePoint.val == 'x':
                nodePoint.val = sortNum
                sortNum = sortNum + 1
            if Treelist != []:
                nodePoint = Treelist.pop()
    return Tree

感謝各位的閱讀，以上就是“怎么使用Java遞歸推出給定節(jié)點(diǎn)數(shù)的所有形狀二叉搜索樹”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對(duì)怎么使用Java遞歸推出給定節(jié)點(diǎn)數(shù)的所有形狀二叉搜索樹這一問題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是創(chuàng)新互聯(lián)，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！

文章名稱：怎么使用Java遞歸推出給定節(jié)點(diǎn)數(shù)的所有形狀二叉搜索樹
分享地址：http://vcdvsql.cn/article8/pehgip.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站策劃、品牌網(wǎng)站設(shè)計(jì)、服務(wù)器托管、App開發(fā)、手機(jī)網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)