数据结构与算法5:树的表示法

1. 多叉树表示法

1.1 双亲表示法

• 表格表示
  

• 参考代码

struct Node{
   char data;
   int parent; 
};


Node nodes[n];

• 优缺点
  比较容易找到双亲，但是不容易找到孩子。

2.2 孩子表示法

• 表格表示
  

• 参考代码

struct Node{
   char data;
   vector<int> children; 
};

Node nodes[n];

• 优缺点
  比较容易找到孩子，但是不容易找到双亲。

优化：双亲孩子表示法

• 表格表示
  

参考代码

struct Node{
   char data;
   int parent; 
   vector<int> children; 
};

Node nodes[n];

• 优缺点
  双亲孩子都比较容易找到。

1.3 孩子兄弟表示法

• 表格表示

• 参考代码

struct Node{
   char data;
   int firstchild;
   int rightsib; 
};

Node nodes[n];

• 优缺点
  比较容易找到孩子和兄弟，但是不容易找到双亲。
  孩子兄弟表示法主要用来把多叉树转化成二叉树。

2 二叉树表示法

2.1 顺序存储方式

将二叉树存储在一个数组中，通过存储元素的下标反映元素之间的父子关系。用一组连续地址的存储空间依次自上而下、自左到右存储二叉树上的节点。

• 一棵深度为的二叉树通常需要个节点空间存储。

• 节点之间的关系根据二叉树的性质5确定。
  

• 通常使用0表示空节点。
  

结点个数已知的完全二叉树或接近完全二叉树的二叉树，通常使用这种方式。最坏情况为深度为k且只有k个节点的单支数。

2.2 链式存储方式

因为顺序存储存在的局限性，二叉树比较常见的是链式存储方式。由于二叉树结构简单，通常使用孩子表示法，或者孩子双亲表示法。

• 孩子表示法

struct Node{
  char data;
  struct Node* right_child;
  struct Node*left_child;
};

Node* head;

• 孩子双亲表示法

struct Node{
  char data;
  struct Node* right_child;
  struct Node* left_child;
  struct Node* parent;
};

Node* head;