树的存储结构及实现 #

1. 一般树到二叉树
2. 树节点的构造
3. 二叉树编程的实现

一般树到二叉树 #

对于一棵一般树，我们可以用如下的方法将它转化为二叉树:
1、将树的根节点直接作为二叉树的根节点
2、将树的根节点的第一个子节点作为根节点的左儿子，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右儿子
3、将树中的剩余节点按照上一步的方式，依序添加到二叉树中，直到树中所有的节点都在二叉树中
观察图1到图2到图3。图1为原普通树，图2是由图 1 经过孩子兄弟表示法转化而来的一棵树，确切地说图3是一棵二叉树。因此可以得出这样一个结论，即通过孩子兄弟表示法，任意一棵普通树都可以相应转化为一棵二叉树，它们是一 一对应的

二叉树节点的构造 #

从上一小节的课程中我们可以看到任何树都可以通过孩子兄弟表示法转化为二叉树，因此这里主要编程实现二叉树。
对于任意一个二叉树节点，除了存储本节点的数据外，还需要存储指向左子树和右子树的指针，二叉树节点初始化如下：

class TreeNode:
    def __init__(self, rootObj):
        self.data = rootObj
        self.leftChild = None
        self.rightChild = None

二叉树的编程实现 #

下面实现了一个简单的二叉树，具有添加和获取左子树、右子树，设置和获取根结点的基本功能：

class TreeNode:
    def __init__(self, rootObj):
        self.data = rootObj
        self.leftChild = None
        self.rightChild = None

    # 添加左子树，没有左子树就直接添加，有就把新节点指向左子树，再将根节点的leftChild指向新节点
    def insertLeft(self, newNode):
        if self.leftChild is None:
            self.leftChild = TreeNode(newNode)
        else:
            t = TreeNode(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t
    # 添加右子树，没有右子树就直接添加，有就把新节点指向右子树，再将根节点的rightChild指向新节点
    def insertRight(self, newNode):
        if self.rightChild is None:
            self.rightChild = TreeNode(newNode)
        else:
            t = TreeNode(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

    def getRightChild(self):
        return self.rightChild

    def getLeftChild(self):
        return self.leftChild

    def setRootVal(self, obj):
        self.data = obj

    def getRootVal(self):
        return self.data

小结 #

• • • • 掌握一般树到二叉树的转换方法
      • 能够使用python程序将图形树使用孩子兄弟法表示出来

习题 #