数据结构-树的存储结构

树的三种存储结构

1. 双亲表示法

用线性表来表示树。
线性表每一个空间代表一个节点
下标代表节点的父亲节点
当算法中需要在树结构中频繁地查找某结点的父结点时，使用双亲表示法最合适。

双亲表示法示例

# 双亲表示法
class PTNode:
    def __init__(self,data,parent):
        self.data = data
        self.parent = parent
    # 当属性相同时，就判断别为相同
    def __eq__(self, other):
        return self.__dict__ == other.__dict__

class tree:
    def  __init__(self,data):
        self.root = PTNode(data,-1)
        self.list = [self.root]
    def addNode(self,data,parent):
        index = 0
        for item in self.list:
            if item.data ==parent:
                break
            index +=1
        self.list.append(PTNode(data,index))
        return self
    def getNodeIdx(self,Node):
        index = 0
        for item in  self.list:
            if item == Node:
                return  index
            index += 1

t = tree('R') #根节点
nodeAIdx = t.getNodeIdx(PTNode('A',-1))
t.addNode('A','R').addNode('B','R').addNode('C','R')
t.addNode('D','A').addNode('E','A')
t.addNode('F','C')
t.addNode('G','F').addNode('H','F').addNode('K','F')

2. 孩子表示法

首先把每个节点用线性表存储
然后每个节点的孩子用链表存储起来，如果节点没有孩子，则是一个空链表
使用孩子表示法，可以很方便的找到节点的孩子。

孩子表示法示例

class CTNode:
    def __init__(self,data,index):
        self.data =data
        self.index = index
        self.next = None

class tree:
    def __init__(self,l):
        index = 0
        self.list = []
        for item in l:
            self.list.append(CTNode(item,index))
            index += 1
    def getNode(self,data):
        for item in self.list:
            if item.data == data:
                return item
    def addChild(self,node,child):
        while node.next:
            node = node.next
        node.next = child



t = tree(['R','A','B','C','D','E','F','G','H','K'])
# R -> A -> B -> C
t.addChild(t.getNode('R'),t.getNode('A'))
t.addChild(t.getNode('R'),t.getNode('B'))
t.addChild(t.getNode('R'),t.getNode('C'))

# A -> D -> E
t.addChild(t.getNode('A'),t.getNode('D'))
t.addChild(t.getNode('A'),t.getNode('E'))

# C -> F
t.addChild(t.getNode('C'),t.getNode('F'))

# F -> G -> H -> K
t.addChild(t.getNode('F'),t.getNode('G'))
t.addChild(t.getNode('F'),t.getNode('H'))
t.addChild(t.getNode('F'),t.getNode('K'))

3. 孩子兄弟表示法,使用这种方法可以将树，转换成二叉树

这里只是简单的将一棵树转换成了二叉树，其右子树为空

class Node:
    def __init__(self,data,child):
        self.data = data
        self.child = child
        self.sibling = None

L = Node('L',None)
K = Node('K',None)
F = Node('F',None)
E = Node('E',[K,L])
B = Node('B',[E,F])
G = Node('G',None)
C = Node('C',[G])
M = Node('M',None)
H = Node('H',[M])
I = Node('I',None)
J = Node('J',None)
D = Node('D',[H,I,J])
A = Node('A',[B,C,D])

print(A)

# 森林转二叉树
def forestConvertBinaryTree(tree):


    stack = [tree]
    # 加线 就是记录节点的兄弟节点
    while stack: # 栈不为空
        tree =  stack.pop(0)
        if  tree.child:
            index = 0
            for node in tree.child:
                if index<len(tree.child)-1:
                    node.sibling = tree.child[index+1]
                print(node.data)
                # 兄弟节点之间加线
                index +=1
                stack.append(node)
            # 去线：对树中每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。
            tree.child = [tree.child[0]]

forestConvertBinaryTree(A)

线索二叉树

树的三种存储结构

1. 双亲表示法

2. 孩子表示法

3. 孩子兄弟表示法,使用这种方法可以将树，转换成二叉树

FEATURED TAGS