数据结构-树形结构_数据结构树组成

1.概念

1.1 树

树（Tree）是一种非线性的数据结构，由n个节点组成，其中每个节点都有零个或多个子节点。树结构中包括一个根节点，该节点没有父节点，以及其他节点，每个节点最多只有一个父节点。

1.1.1 节点命名

• 根节点：第一个延伸出去的节点称为根节点，根节点没有父节点，整棵树从根节点开始。
• 父节点：节点的上一个节点称为父节点。
• 子节点：与父节点相反，节点的下一个节点称为子节点。
• 叶子节点：节点向下延伸，直到没有子节点的节点称为叶子节点。比如上图的G、D、E、F。
• 兄弟节点：拥有同一个父节点的节点之间称为兄弟节点，比如上图的A、B节点。
• 祖先节点：节点之前的节点都称为祖先节点，比如根节点和A、C都是G的祖先节点。

1.1.1 名词解释

• 度： 节点下面子节点的数量称为节点的度（分支的数量），所有节点的度中最大的度称为树的度。
• 子树： 每个节点下面延伸出去的节点都可以称为子树，比如上面的A、C、D就是一颗子树。
• 层次： 根节点层次为1，每向下一层，层次就加1，例如上面的A、B节点就是第2层，C、D、E、F节点是第三层。
• 高度： 节点的高度是该节点到叶子节点的最长路径，比如A节点的高度是2，因为A到最远的叶子节点G的距离为2，树的高度是最远的叶子结点到根节点的距离，上面的树的高度为3。
• 深度： 从根节点到该节点的距离称为节点的深度。比如A的深度是1，因为A到根节点距离为1。树的深度是根节点到最远的叶子结点的距离，上面的树的深度为3。

1.2 森林

由多个树组成，这些树之间没有任何联系。每棵树都是独立的，具有其自身的根节点和子节点。

上图就是一个包含3棵树的森林，森林常见概念：

• 森林中每个节点的度数（Degree）是其子节点的个数。
• 森林的高度（Height）是所有树的高度中的最大值。

1.3 二叉树

二叉树是一种特殊的树，二叉树中每个节点的度都不能大于2，就是说每个节点最多只能有左右两个子节点。

• 满二叉树：所有叶子节点都在同一层且除了叶子节点以外其他节点都有左右子节点的二叉树叫做满二叉树。比如上图的A节点以下的子树就是一个满二叉树。
  

• 完全二叉树：除去最后一层叶子节点之后是满二叉树，并且最后一层按照从左往右顺序排列的二叉树叫做完全二叉树。（满二叉树一定是完全二叉树）

1.3.1 二叉树、树、森林的转换

1.3.1.1 树转换为二叉树

转换规则：（从左往右）每个节点的第一个子节点作为左孩子（左边的子节点），左孩子右边相邻的兄弟节点作为左孩子的右孩子（右边的子节点），以此类推。言语表述不是很准确，下面给出完整的转换过程：

我们要将上面的树转换成二叉树，经历如下步骤：（顺序是从左往右，从上往下）

• 1）A节点第一个节点是B，A的右边没有兄弟节点，所以根据上面的转换规则，B作为A的左孩子，A的右孩子是空节点（没有）
  

• 2）B节点的第一个节点是E，所以E是B的左孩子；B节点的右边兄弟节点是C，根据上面的规则，C作为B的右孩子
  

• 3）C的第一个子节点是G，所以G是C的左孩子；C的右边相邻的兄弟节点是D，所以D是C的右孩子
  

• 4）D的第一个子节点是H，所以H是D的左孩子；D的右边没有相邻的兄弟节点，所以D的右孩子是空节点
  

• 5）最后是叶子节点，因为叶子结点没有子节点，所以左孩子为空，E右边的兄弟节点是F，所以F是E的右孩子；F、G、I没有子节点，右边也没有兄弟节点，所以F、G、I没有左/右孩子；H只有一个右边的兄弟节点I，所以I是H的右孩子。
  
  最终的二叉树转换就如上图。

除了上面的方法外，还可以使用连线法进行二叉树的转换：

• 1）将所有节点的兄弟节点连接起来，如下图中的绿色虚线所示
  
• 2）去掉原来的除了第一个子节点之外的所有连线，如下图中的虚线所示，都是需要去掉的连线
  
  去掉之后长这样：
  
• 3）拉伸之后就跟我们上面第一种方法结果相同了，转换成了二叉树
  

二叉树转换成树这里就不再赘述了，反向操作就行了。

1.3.1.2 森林转换成二叉树

森林转换成二叉树跟树转换成二叉树类似：

• 1）将每棵树先转换成二叉树
• 2）然后将每棵树的右边相邻的树作为当前树根节点的右子树
  示例：
  
  
  

1.3.2 二叉树的数学性质

以下性质仅针对非空二叉树有效

• 二叉树的深度（或高度）为k时，二叉树的最大节点数为2^k-1，最小节点数为k。
• 二叉树的第i层最多有2^i-1个节点。
• 二叉树中，若度数为0、1、2的节点数量分别为n₀、n₁、n₂，则n₀=n₂+1。
• 一个拥有n个节点的完全二叉树的深度k = log₂n + 1（log₂n向下取整）
• 一个拥有n个节点的完全二叉树，从下往上，从左往右编号j，满足以下性质：
  • 左孩子编号 = 2j
  • 右孩子的编号 = 2j + 1
  • 如果2j > n，则没有左孩子
  • 如果2j + 1>n，则没有右孩子
    

1.3.3 二叉树的代码实现

下面我们将用代码实现下图中的二叉树：

• C语言实现：

#include <stdio.h>
#include <stdlib.h>

typedef char Item;

typedef struct BinaryTreeNode {
    Item item;
    struct BinaryTreeNode *left;
    struct BinaryTreeNode *right;
} *Node;

// 分配节点内存
Node newNode(Item data) {
    Node node = (Node) malloc(sizeof(struct BinaryTreeNode));
    if (node == NULL) {
        printf("内存不足！\n");
        return NULL;
    } else {
        node->item = data;
        node->left = NULL;
        node->right = NULL;
        return node;
    }
}

Node newTree() {
    Node a = newNode('A');
    Node b = newNode('B');
    Node c = newNode('C');
    Node d = newNode('D');
    Node e = newNode('E');
    Node f = newNode('F');
    Node g = newNode('G');
    a->left = b;
    a->right = c;
    b->left = d;
    b->right = e;
    c->left = f;
    c->right = g;
    return a;
}

int main() {
    Node tree = newTree();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

• python实现：

class BinaryTreeNode:
    def __init__(self, data):
        self.item = data
        self.left = None
        self.right = None


class BinaryTree:
    def __init__(self):
        a = BinaryTreeNode('A')
        b = BinaryTreeNode('B')
        c = BinaryTreeNode('C')
        d = BinaryTreeNode('D')
        e = BinaryTreeNode('E')
        f = BinaryTreeNode('F')
        g = BinaryTreeNode('G')
        a.left = b
        a.right = c
        b.left = d
        b.right = e
        c.left = f
        c.right = g
        self.__head = a
        

if __name__ == '__main__':
    tree = BinaryTree()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
'
运行
运行

1.3.4 二叉树的遍历

下面二叉树遍历都以上面的二叉树作为例子
叶子节点可以看做左右子节点为空的树

1.3.4.1 前序遍历

遍历规则：

• 1.访问根节点
• 2.遍历左子树
• 3.遍历右子树

图解：

按照遍历规则，先访问根节点A（当前遍历结果：A），然后遍历左子树B，按照相同的规则，先访问根节点B（当前遍历结果：AB），继续遍历B下面的左子树D，D子树的左右子树都为空，于是访问根节点D（当前遍历结果：ABD），对于B子树来说，左子树已经遍历完成，接下来按照同样的规则遍历右子树E,先访问根节点E（当前遍历结果：ABDE），E的左右子树都为空，遍历结束，到此A的左子树B遍历完成，接下来就该遍历A的右子树C，跟上面相同，右子树C遍历结果就是CFG，结合前面的遍历结果，最终遍历结果为：ABDECFG

代码实现：

• 递归实现：以下代码是C语言进行前序遍历的递归实现

void preOrder(Node node) {
    if (node == NULL)return;
    printf("%c ", node->item);
    preOrder(node->left);
    preOrder(node->right);
}
1
2
3
4
5
6

• 栈实现：以下代码是Python的列表作为栈容器进行实现

前序遍历的栈实现不太好理解，下面详细讲解一下：

• 1.首先得有个栈容器存放我们的节点，不然遍历到下一个节点时，上一个节点已经找不到了，就没法遍历了。
• 2.按照先遍历左子树再遍历右子树的规则，将每个左子节点都遍历后放入栈容器，现在栈容器里面的节点是ABD。
• 3.当前节点为空时，从栈顶取出节点，将当前节点指向右子树。
• 4.当前节点为空且栈也为空时，说明已经遍历完所有节点，这时候就退出循环。

    def preorder(self):
        """前序遍历

        :return:
        """
        stack = []
        node = self.__head
        while node or stack:
            while node:
                print(node.item, end=" ")
                stack.append(node)
                node = node.left
            else:
                node = stack.pop()
                node = node.right
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
'
运行
运行

1.3.4.2 中序遍历

遍历规则：

• 1.遍历左子树
• 2.访问根节点
• 3.遍历右子树

图解：先找到最左边的节点，依次往回推

按照规则，先遍历左子树A->B->D，D左子树为空，对于D子树来说，左子树遍历完成，接下来访问根节点D（当前遍历结果：D），然后遍历D的右子树，D的右子树也为空，那么B的左子树遍历完成，访问根节点B（当前遍历结果：DB），然后遍历右子树E，得到结果DBE；到此A的左子树遍历完成，访问根节点A（当前遍历结果：DBEA），按照相同规则遍历右子树C，得到结果FCG，结合之前的结果，中序遍历结果为：DBEAFCG

代码实现：

• C语言：

void inOrder(Node node) {
    if (node == NULL) {
        return;
    }
    inOrder(node->left);  // 遍历左子树
    printf("%c ", node->item); // 访问根节点
    inOrder(node->right); // 遍历右子树
}
1
2
3
4
5
6
7
8

• Python：

    def inorder(self):
        """中序遍历
        :return:
        """
        node = self.__head
        self.__inorder(node)

    def __inorder(self, node: BinaryTreeNode):
        """中序遍历递归实现

        :param node: 当前节点
        :return:
        """
        if node is None:
            return
        self.__inorder(node.left)
        print(node.item, end=" ")
        self.__inorder(node.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.3.4.3 后序遍历

遍历规则：

• 1.遍历左子树
• 2.遍历右子树
• 3.访问根节点

图解：

按照规则，可以把树拆解成ABC、BDE、CFG三个子树，B子树是BDE、C子树是CFG，按照规则应该先遍历A的左子树B，就是先遍历BDE子树，BDE子树的后序遍历结果是DEB，A的左子树遍历完成，接下来遍历A的右子树C，也就是遍历CFG，遍历结果为FGC，然后A的右子树也遍历完成，按照左->右->根顺序，这颗二叉树的后序比遍历结果就是：DEBFGCA

代码实现：

• C语言：

void postOrder(Node node) {
    if (node == NULL) {
        return;
    }
    postOrder(node->left);  // 遍历左子树
    postOrder(node->right); // 遍历右子树
    printf("%c ", node->item); // 访问根节点
}
1
2
3
4
5
6
7
8

• Python：

    def postorder(self):
        """后序遍历
        :return:
        """
        node = self.__head
        self.__postorder(node)

    def __postorder(self, node: BinaryTreeNode):
        """后序遍历递归实现

        :param node: 当前节点
        :return:
        """
        if node is None:
            return
        self.__postorder(node.left)
        self.__postorder(node.right)
        print(node.item, end=" ")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.3.4.4 层序遍历

遍历规则：从根节点开始，按照从上到下、从左到右的顺序逐层访问节点
图解：

层序遍历是最容易理解的，就是一层一层的按照从左到右的顺序遍历，此处不再赘述。

代码实现：

思路：层序遍历是最好理解的，但是用代码实现的话使用前面的递归就很难处理了，最简单的处理方式是借助队列进行遍历。首先将根节点放入队列作队列初始化，循环判断队列是否为空，当队列不为空时，取出队首元素，判断当前的节点左右子节点是否为空，不为空时放入队列。

• C语言实现：由于C语言没有内置队列结构，所以我们需要自定义一个队列

struct ListQueue {
    Node *array;
    int capacity;
    int front; // 队头指针
    int rear; // 队尾指针
};

typedef struct ListQueue *Queue;

bool initQueue(Queue queue, int capacity) {
    queue->array = (Node *) malloc(sizeof(Node) * (capacity + 1));
    if (queue->array == NULL) {
        printf("内存不足，队列初始化失败！");
        return false;
    }
    queue->capacity = capacity + 1;
    queue->front = queue->rear = 0;
    return true;
}

bool isEmptyQueue(Queue queue) {
    if (queue->front == queue->rear) {
        return true;
    }
    return false;
}

bool putQueue(Queue queue, Node item) {
    if ((queue->rear + 1) % queue->capacity == queue->front) {
        return false;
    }
    queue->array[queue->rear] = item;
    queue->rear = (queue->rear + 1) % queue->capacity;
    return true;
}

Node getQueue(Queue queue) {
    if (isEmptyQueue(queue)) return NULL;
    Node item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    return item;
}

void breadthFirstSearch(Node root){
    if (!root)return;
    struct ListQueue queue; // 初始化一个队列，用来存放遍历节点
    Queue q = &queue;
    initQueue(q, 20);
    putQueue(q, root);
    while (!isEmptyQueue(q)){ // 当队列不为空时循环遍历
        Node node = getQueue(q);
        printf("%c ",node->item);
        if (node->left) putQueue(q, node->left); // 如果有左孩子就添加进队列
        if (node->right) putQueue(q, node->right); // 如果有右孩子就添加进队列
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

• Python实现：

    def breadthFirstSearch(self):
        """层序遍历(宽度优先搜索)

        :return:
        """
        q = queue.Queue()
        q.put(self.__head)
        while not q.empty():
            node = q.get()
            print(node.item, end=" ")
            if node.left:
                q.put(node.left)
            if node.right:
                q.put(node.right)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
'
运行
运行