树的三种表示方法

缘起

学习树, 就要知道树的四种表示方法

  1. 双亲表示法
  2. 孩子表示法
  3. 孩子双亲表示法
  4. 长子兄弟法（又叫做二叉树表示法, 因为该方法将多叉树（包括二叉树）转换为了二叉树）

其中，3是值得推荐的. 因为我们将1和2都转换为3

分析

  1. 双亲表示法就是一个数组, 数组上每个元素代表一个节点, 其拥有一个域指向其父元素的索引.根节点的父节点索引是-1, 缺点是要找一个节点的孩子列表比较麻烦.
  2. 孩子表示法就是一个数组，数组上每个元素代表一个节点, 其拥有一个指针域，指向其孩子节点（即数组上挂链表）, 缺点是要找一个节点的父节点比较麻烦.
  3. 综合1和2的优点，我们在孩子表示法的每个节点中增加一个parent域, 指向其父节点的索引. 这样虽然增加了空间复杂度，但是可以很方便的找到每个节点的父节点和孩子列表.
  4. 左孩子，右兄弟. 即每个节点有两个指针域，左孩子指针指向自己的长子节点，右孩子指针指向自己的兄弟节点. 则将任何多叉树（亦包含二叉树）转换为了二叉树. 鉴于计算机中开辟一块连续内存的不易, 长子兄弟法应该是大部分多叉树实现的物理模型. 因为 1 2 3皆基于数组.

注意，下面的代码，我们将孩子表示法和孩子双亲表示法合二为一了. 因为就是加一个parent域的事儿嘛~

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
58
59
60
61
62
#include "stdafx.h"
#include <iostream>
#pragma warning(disable:4996) // 防止scanf 等不带_s的api报错

const int MAX_TREENODE_NUM = 100; // 树节点最多100个
//#define LOCAL
using namespace std;

// #################双亲表示法 开始#################

struct { // 双亲表示法的树
    struct PTreeNode // 双亲表示法的树节点(其实就是数组上的元素)
    {
        char data; // 数值
        int parent; // 父节点索引, 根节点的此值为-1
    };
	PTreeNode nodes[MAX_TREENODE_NUM]; // 节点数组
	int root,n; // 根节点在数组中的索引, 树节点的实际个数
} PTree;


// #################双亲表示法 结束#################

// #################孩子双亲表示法 开始#################

struct {  // 孩子双亲表示法的树
    struct CTBox // 数组上的元素
    {
        struct CTreeNode // 孩子表示法的树节点
        {
            char data;
            CTreeNode *next;
        };
        int parent; // 双亲域
        char data;
        CTreeNode *first;
    };
	CTBox nodes[MAX_TREENODE_NUM];
	int root, n;
} CTree;

// #################孩子双亲表示法 结束#################


// #################长子兄弟表示法 开始#################
struct EldestSonSiblingTreeNode
{
	char data;
	EldestSonSiblingTreeNode *eldestson, *sibling;
}*EldestSonSiblingTree;

// #################长子兄弟表示法 结束#################



int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	return 0;
}

ps: 最后一种因为将多叉树（包括二叉树）转化为了二叉树，所以也叫作二叉树表示法. 它尤为重要. 因为实现了一定程度的统一.