二叉树基础

二叉树

二叉树定义

有且仅有一个根结点,除根节点外,每个结点只有一个父结点,最多含有两个子节点,子节点有左右之分。

二叉树节点

以Python举例,一个二叉树节点结构类似于下面这样,一般的面向对象的语言,定义二叉树节点都类似:

# 二叉树节点
class TreeNode(object):
    def __init__(self, data = None, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

二叉树的遍历

遍历是二叉树的一个基本操作,主要有前序、中序、后序三种遍历方式。

先序遍历:根节点->左子树->右子树

中序遍历:左子树->根节点->右子树

后序遍历:左子树->右子树->根节点

二叉树的建立

#二叉树
class BTree(object):
    def __init__(self, root = None):
        self.root = root

    def is_empty(self):
        if self.root is None:
            return True
        else:
            return False

    # 前序遍历
    def preOrder(self, treenode):
        if treenode is None:
            return
        print(treenode.data)
        self.preOrder(treenode.left)
        self.preOrder(treenode.right)

    # 中序遍历
    def inOrder(self, treenode):
        if treenode is None:
            return
        self.inOrder(treenode.left)
        print(treenode.data)
        self.inOrder(treenode.right)

    # 后序遍历
    def postOrder(self, treenode):
        if treenode is None:
            return
        self.postOrder(treenode.left)
        self.postOrder(treenode.right)
        print(treenode.data)

创建节点

n1 = TreeNode(data=1)
n2 = TreeNode(2, n1)
n3 = TreeNode(3)
n4 = TreeNode(4)
n5 = TreeNode(5, n3, n4)
n6 = TreeNode(6, n2, n5)
n7 = TreeNode(7, n6)
n8 = TreeNode(8)

建树

root = TreeNode('root', n7, n8)
bt = BTree(root)

遍历

前序遍历:

print('前序遍历......')
print(bt.preOrder(bt.root))

前序遍历......
root
7
6
2
1
5
3
4
8
None

中序遍历:

print('中序遍历......')
print(bt.inOrder(bt.root))

中序遍历......
1
2
6
3
5
4
7
root
8
None

后续遍历:

print('后续遍历.....')
print(bt.postOrder(bt.root))

后续遍历.....
1
2
3
4
5
6
7
8
root
None

Article Published in on Algorithm

Article by 付军