☰

» »

Predstavitev dvojiškega drevesa z seznamom

Predstavitev dvojiškega drevesa z seznamom

ktka ::

Živjo!
Zanima me naslednje: kako bi v Pythonu napisala razred, kjer bi predstavila dvojiško drevo z seznamom.
Teorijo poznam:)
oče(i) = i%2,
leviSin(i) = 2*i
desniSIn(i) = 2*i+1
A je kej v tem smislu?
class DDseznam:

    def __init__(self):
        self.seznam = []
        
      

    def koren(self):
        try:
            return self.seznam[1]
        except:
            raise Exception('Prazno drevo nima desnega poddrevesa')
        

    def oče(self):
        try:
            for i in range(len(self.seznam)):
                oče = i%2
            return oče
        except:
       
            raise Exception('Prazno drevo nima desnega poddrevesa')
        
            

    def desniSin(self):
        try:
            for i in range(len(self.seznam)):
                desniSin = (koren*2) + 1
            return desniSin
        except:
            raise Exception('Prazno drevo nima desnega poddrevesa')
        

    def leviSin(self):
        try:
            for i in range(len(self.seznam)):
                leviSin = koren*2
            return leviSin
        except:
            raise Exception('Prazno drevo nima desnega poddrevesa')

Randomness ::

Ne vem točno, kaj želiš doseči, ampak spodnje dvojiško drevo se da v Pythonu predstaviti z naslednjim "vgnezdenim" seznamom:

[1,[2,[3,4]]]

     O
    / \
   1   O
      / \
     2   O
        / \
       3   4

Zgodovina sprememb…

ktka ::

Ubistvu mam jst to v mislih, da vozlišča v seznama dodajaš po nivojih, v tvojem primeru(0 so vozlišča):
seznam = [0,1,0,2,0,3,4]
Če pa daš da 0 niso vozlišča, to ni dvojiško drevo. Def: dd je sestavljen in posebnega vozlišča koren in iz levega in desnega poddrevesa.

krneki0001 ::

Dvojiško drevo v pythonu: http://www.laurentluce.com/posts/binary...

recimo razred:
class BinaryTree():

    def __init__(self,rootid):
      self.left = None
      self.right = None
      self.rootid = rootid

    def getLeftChild(self):
        return self.left
    def getRightChild(self):
        return self.right
    def setNodeValue(self,value):
        self.rootid = value
    def getNodeValue(self):
        return self.rootid

    def insertRight(self,newNode):
        if self.right == None:
            self.right = BinaryTree(newNode)
        else:
            tree = BinaryTree(newNode)
            tree.right = self.right
            self.right = tree

    def insertLeft(self,newNode):
        if self.left == None:
            self.left = BinaryTree(newNode)
        else:
            tree = BinaryTree(newNode)
            self.left = tree
            tree.left = self.left


def printTree(tree):
        if tree != None:
            printTree(tree.getLeftChild())
            print(tree.getNodeValue())
            printTree(tree.getRightChild())


Pa še za test tega razreda

def testTree():
    myTree = BinaryTree("1")
    myTree.insertLeft("4")
    myTree.insertRight("8")
    myTree.insertRight("3")
    printTree(myTree)
Asrock X99 Extreme 4 | Intel E5-2683V4 ES | 64GB DDR4 2400MHz ECC |
Samsung 250GB M.2 | Asus 1070 TI | 850W Antec | LC Tank Buster

Zgodovina sprememb…

Spura ::

Binarno drevo se da predstavit z eno-dimenzionalnim arrayem.
Teorijo poznam:)
You sure about that?

oče(i) = i%2 je narobe, in implementacija kaze da ne razumes sploh.

public class BinaryTree<T> {

	int idx = 1;
	private final ArrayList<T> nodes;

	public BinaryTree(final ArrayList<T> nodes) {
		this.nodes = nodes;
	}

	private BinaryTree(final ArrayList<T> nodes, final int idx) {
		this.nodes = nodes;
		this.idx = idx;
	}

	private BinaryTree<T> getNodeAt(final int idx) {
		if (idx >= nodes.size()) {
			return null;
		}
		final T node = nodes.get(idx);
		return node == null ? null : new BinaryTree<T>(nodes, idx);
	}

	public BinaryTree<T> left() {
		return getNodeAt(idx * 2);
	}

	public BinaryTree<T> parent() {
		return getNodeAt(idx / 2);
	}

	public BinaryTree<T> right() {
		return getNodeAt(idx * 2 + 1);
	}

	public BinaryTree<T> root() {
		return getNodeAt(1);
	}
}

Simply implementacija read-only drevesa prednalozenega iz seznama.

ktka ::

ja pomota. oče(i) = i//2

Spura ::

kako bi v Pythonu napisala razred, kjer bi predstavila dvojiško drevo z seznamom

krneki0001 je izjavil:

Dvojiško drevo v pythonu: http://www.laurentluce.com/posts/binary...

recimo razred:
A je tvoje drevo predstavljeno s seznamom? Ljudje so vedno bolj nepismeni.

ktka ::

žal so me na faksu navadli samo python:) tko da druge kode težko berem.
Je vsaj malo podobno kodi kot pri Spura.
class DDseznam:

    def __init__(self):
        self.seznam = []
        self.indeks = 1

    def vrni(self,indeks):
        if indeks >= len(seznam):
            return None
        for indeks in range(len(seznam)):
            nov = DDseznam(seznam[indeks:],indeks)
        
    def koren(self):
        return self.seznam[1]

    def oče(self):
        return vrni(indeks//2)
            

    def desniSin(self):
        return vrni(indeks*2+1)

    def leviSin(self):
        return vrni(indeks*2)

krneki0001 ::

Spura je izjavil:

kako bi v Pythonu napisala razred, kjer bi predstavila dvojiško drevo z seznamom

krneki0001 je izjavil:

Dvojiško drevo v pythonu: http://www.laurentluce.com/posts/binary...

recimo razred:
A je tvoje drevo predstavljeno s seznamom? Ljudje so vedno bolj nepismeni.

Spregledal seznam, sorry se opravičujem.

Potem pa tole:
http://interactivepython.org/runestone/...
Asrock X99 Extreme 4 | Intel E5-2683V4 ES | 64GB DDR4 2400MHz ECC |
Samsung 250GB M.2 | Asus 1070 TI | 850W Antec | LC Tank Buster

ragezor ::

am zakaj ne bi vrnil preprosto noda ven, zakaj se vraca nov objekt drevesa z nastavljenim indeksom?

darkkk ::

en mali "komentar" je, da se verjetno da elegantno predstaviti le polno n-tiško drevo in je vse skup samo še preračunavanje indeksov (in je drevo shranjeno po nivojih).

ktka ::

Da se tudi če je nepolno, tam kjer vozlišča ni, more bit v seznamu prazen prostor. Je pa res da za nepolno drevo ta predstavitev ni najboljša, je boljša predstavitev s kazalci.

lebdim ::

+Ktka, si prepričana, da res poznaš teorijo dreves? iz zgornjega posta tvojega tega zagotovo ne morem trditi ...

Spura ::

ragezor je izjavil:

am zakaj ne bi vrnil preprosto noda ven, zakaj se vraca nov objekt drevesa z nastavljenim indeksom?

Zato ker sm zgleda nesrecno poimenoval seznam nodes. Ubistvu so to payloads. Ce vrnes vrednost iz seznama si vrnil samo vrednost in ne mores naprej. In vsako vozlisce je spet polnopravno drevo samo zase z vsemi funcionalnostmi. Pa pozabu sm getValue funkcijo in to je verjetno zmedlo. Ta class predstavlja node v drevesu.

Pri izrojenem drevesu je ogromno praznih mest v seznamu tko da se v praksi to ne uporablja za random drevesa, se pa to uporablja za heap strukturo.

Heap (data structure) @ Wikipedia

Zgodovina sprememb…

  • spremenil: Spura ()

ktka ::

Hvala za vaš trud in in odgovore. Zgleda, da nisem na vašem nivoju in da se ne morem pogovarjati z vami.
Lep deževen dan

Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

python-rabim pomoč

Oddelek: Programiranje		162787 (1017) rnla1973
»

Python - težava s slovarji - vnos

Oddelek: Programiranje		51303 (1125) RatedR
»

Python - pomoč (strani: 1 2 3 )

Oddelek: Programiranje		10318125 (8873) black ice
»

[Python]Naloga z razredi in dedovanjem

Oddelek: Programiranje		101150 (902) ktka
»

Naloga v C-ju pomoč

Oddelek: Programiranje		112457 (2057) keworkian

Več podobnih tem