树形结构及其算法

1. 满二叉树 full binary tree
   如果二叉树的高度为 h，书的节点数为 2^h-1，h>=0，就称此树为满二叉树。
2. 完全二叉树 complete binary tree
   如果二叉树的高度为 h，书的节点数小于 2^h-1，编号从上到下、从左到右一一对应。如果有N个节点，那么此二叉树的层数h为log(N+1)」。
3. 斜二叉树 skewed binary tree
   完全没有右节点，左斜二叉树。
   完全没有做节点，右斜二叉树。
4. 严格二叉树 strictly binary tree
   二叉树中每一个非终端节点均有非空的左右子树。

用数组实现二叉树

使用有序的一维数组表示二叉树，首先可将此二叉树想成满二叉树，且第k层具有2^(k-1)个节点，按序放在一维数组中。

1. 左子树索引值是父节点索引值*2
2. 右子树索引值是父节点索引值*2+1

二叉查找树的特点：

1. 可以是空集合，若不是空集合，则节点上一定要有一个键值。
2. 每一个树根的值需大于左子树的值
3. 每一个树根的值需小于右子树的值
4. 左右子树也是二叉查找树
5. 树的每个节点值都不相同

# 按序输入一颗二叉树节点的数据，分别是0，6，3，5，4，7，8，9，2，并建立一颗查找树，最后输出存储此二叉树的一维数组。
def btree_create(btree, data, length):
    for i in range(1, length):
        level = 1
        while btree[level] != 0:  # 0不参与争斗，用来补位
            if data[i] > btree[level]:  # 如果原始数组内的值大于树根，则往右子树比较
                level = level * 2 + 1
            else:  # 小于等于树根，则往左子树比较
                level = level * 2
        btree[level] = data[i]  # 把数组值放进二叉树


length = 9
data = [0, 6, 3, 5, 4, 7, 8, 9, 2]
btree = [0] * 16
print("原始数组内容为：")
for i in range(length):
    print("[%2d] " % data[i], end='')
print('')
btree_create(btree, data, length)
print("二叉树内容为：")
for i in range(1, 16):
    print("[%2d] " % btree[i], end='')
print()

用链表实现二叉树

对于节点的添加与删除容易，但是难找到父节点，除非在每一个节点增加一个父字段

• 二叉树类声明

class Tree:
    def __init__(self):
        self.data = 0
        self.left = None
        self.right = None

• 以链表建立二叉树：

def create_tree(root, val):
    newnode = Tree()
    newnode.data = val
    newnode.left = None
    newnode.right = None
    if root == None:
        root = newnode
        return root
    else:
        current = root  # 父节点
        # 判断左右子树走向
        while current != None:
            backup = current  # 尾节点
            if current.data > val:
                current = current.left
            else:
                current = current.right
        # 把尾节点和当前节点值比较，把节点放进链表
        if backup.data > val:
            backup.left = newnode
        else:
            backup.right = newnode
        return root

data = [5, 6, 24, 8, 12, 3, 17, 1, 9]
ptr = None
root = None
for i in range(9):
    ptr = create_tree(ptr, data[i])
print("左边：")
root = ptr.left
while root != None:
    print("%d" %root.data)
    root = root.left or root.right
print('-----')
print("右边：")
root = ptr.right
while root != None:
    print("%d" %root.data)
    root = root.right or root.left
print()

左边：
3
1
-----
右边：
6
24
8
12
17

二叉树遍历

• 中序遍历（Inorder）：左子树-树根-右子树

def inorder(ptr):
    if ptr != None:
        inorder(ptr.left)
        print("[%2d] " % ptr.data, end='')
        inorder(ptr.right)

前序遍历（Preorder）：树根-左子树-右子树

def preorder(ptr):
    if ptr != None:
        print("[%2d] " % ptr.data, end='')
        preorder(ptr.left)
        preorder(ptr.right)

后序遍历（Postorder）：左子树-右子树-树根

def postorder(ptr):
    if ptr != None:
        postorder(ptr.left)
        postorder(ptr.right)
        print("[2d] " % ptr.data, end='')

二叉树节点的查找

def search(ptr, val):
    while True:
        if ptr == None:
            return None
        if ptr.data == val:
            return ptr
        elif ptr.data > val:
            ptr = ptr.left
        else:
            ptr = ptr.right

二叉树节点的插入

if search(ptr, data) != None:
    print("二叉树中有此节点了")
else:
    ptr = create_tree(ptr, data)
    inorder(ptr)

二叉树节点的删除

删除的节点为树叶，只要将其相连的父节点指向None即可
删除的节点只有一棵子树
删除的节点有两棵子树

• 中序立即先行者（inorder immediate predecessor）：将欲删除节点的左子树中最大者向上提。简单来说，就是在该节点的左子树，往右寻找，知道右指针为None，这个节点就是中序立即先行者。

• 中序立即后继者（inorder immediate successor）：把要删除节点的右子树中最小者向上提。简单来说，就是在该节点的右子树，往左寻找，知道左指针为None，这个节点就是中序立即后继者。

  堆积树（heap tree）排序算法

  选择排序的改进。堆积树是一种特殊的二叉树，可分为最大堆积树和最小堆积树。
• 最大堆积树满足：
  它是一个完全二叉树。
  所有节点的值都大于或等于它左右子节点的值。
  树根是堆积树中最大的。
• 最小堆积树满足：
  它是一个完全二叉树。
  所有节点的值都小于或等于它左右子节点的值。
  树根是堆积树中最小的。

def heap(data, size):
    for i in range(int(size/2), 0, -1):  # 建立堆积树节点
        ad_heap(data, i, size - 1)
    print("堆积的内容：", end='')
    for i in range(1, size):
        print("[%2d ]" % data[i], end='')
    print("\n")
    for i in range(size-2, 0, -1):  # 堆积排序
        data[i+1], data[1] = data[1], data[i+1]  # 头尾节点交换
        ad_heap(data, 1, i)  # 处理剩余节点
        print("处理过程：", end='')
        for j in range(1, size):
            print("[%2d ]" % data[j], end='')
        print()


def ad_heap(data, i, size):
    j = 2 * i
    tmp = data[i]
    post = 0
    while j <= size and post == 0:
        if j < size:
            if data[j] < data[j + 1]:  # 找出最大节点
                j += 1
        if tmp >= data[j]:  # 若树根较大，则继续比较
            post = 1
        else:              # 若树根较小，则继续比较
            data[int(j/2)] = data[j]
            j = 2 * j
    data[int(j/2)] = tmp  # 指定树根为父节点

树形结构及其算法

原文：https://www.cnblogs.com/catyuang/p/11760502.html