二叉树的存储方式

矫情吗；* 2022-06-02 03:51 109阅读 0赞

\#\#\#\#一、树的表示方法：

树的基础知识请参考以下博客：

http://blog.csdn.net/dai\_wen/article/details/78929433

**1，图形表示法：**

![format_png][]

![format_png 1][]  
**2，广义表表示法：**

![format_png 2][]

![这里写图片描述][format_png 3]  
**3，孩子兄弟表示法**  
![format_png 4][]

在日常生活中，常常听到长兄如父的说法，这里的孩子兄弟表示法是否也如此呢？

对于如下所示的树：（一棵普通的树）  
![format_png 5][]

将其第一个孩子结点保留，其余孩子结点与其原有的双亲结点断开，并将其连接到第一个孩子结点上，则有：  
![format_png 6][]

整理得出：  
![format_png 7][]

其实，采用这种方式表示，可以将一颗普通的树转为一颗二叉树；那么，为什么要将数转为二叉树呢？

这就像计算机实现进制之间的转换一样，先将最简单，最基础的二进制运算实现，再将其它进制转为二进制，最后实现，那么，数直接存储不好实现，现实现二叉树，再在二叉树的基础上来操作，就显得容易的多；

![format_png 8][]  
\#\#\#\#二，二叉树的存储方式：

首先：对于一颗树：可以采取顺序的存储方式，也可采用链式方式进行存储；

**1，顺序存储：**  
规定：从上到下，从左至右依次保存树中的结点  
![format_png 9][]

（A，B，D，C，E，F）

缺陷：若给定一个序列，无法知道一个结点是某节点的左，右孩子还是后继，

//如上述序列，C到底是B的右孩子，还是D的左孩子，还是其他，无法确认，也就是说，如果已知存储序列，很难将其复原成一颗树；

解决方案: 为了能找到某一结点的上下左右关系，也必须仿照完全二叉树的方式来存储，遇到空树，在顺序表中应该将该位置空出来。  
（如下将空树用＃表示）  
![format_png 10][]

缺陷：采用这种方式，内存空间浪费太多；

**2，链式存储：**

由一个前驱指针和N个后继指针构成，那么后继指针到底有多少个？是给成指定等长还是不定长？  
（１）两个指针域：  
![format_png 11][]

//二叉树结点类型定义
    typedef struct node* tree_pointer;
    	typedef struct node
    	{
    		int data;
    		tree_pointer lchild,rchild;	
    	}node;

如下所示：  
![format_png 12][]  
（２）三个指针域：  
![format_png 13][]

//三叉链表
    	typedef struct TirTNode
    	{
    		int data;
    		struct TriTNode * lchild,*rchild;//指向孩子结点
    		struct TriTNode *parent;//指向双亲结点
    	}TriTNode,*TriTree;

![format_png 14][]  
（３），双亲表示法：

//双亲链表
    #define MAX_TREE_SIZE 100
    	typedef struct BPTNode
    	{
    		int data;
    		int *parent;//指向双亲结点
    		char LRTag;//左右孩子标记
    
    	}BPTNode;

如下所示：  
![format_png 15][]

![format_png 16][]

![format_png 17][]

总结来说：树的存储方式有孩子表示法，双亲表示法，孩子兄弟法，孩子双亲法，我们最常用的是孩子双亲法。

二叉树的具体性质，请参考  
http://blog.csdn.net/dai\_wen/article/details/78929433

[format_png]: /images/20220602/eee78bd131264cb8889747951fbbaacb.png
[format_png 1]: /images/20220602/a1d64a50cda341479e98382fb9bf1f9f.png
[format_png 2]: /images/20220602/854b8e06064945849865f3a3963daaf8.png
[format_png 3]: /images/20220602/d36fef3fb2ca407e994249b5bd8d0744.png
[format_png 4]: /images/20220602/f7fc4483565d4b4aa8c99fe5fe263e1b.png
[format_png 5]: /images/20220602/0a68fe49845d4929ac0af9adf363abb0.png
[format_png 6]: /images/20220602/4ae8e585a29d4a2ebd3182bb94ed5b58.png
[format_png 7]: /images/20220602/33ffe2c867b6472c81b12d6c30f9612b.png
[format_png 8]: /images/20220602/17b55d00b3ed47649a7a11b81b0b5470.png
[format_png 9]: /images/20220602/9ba5ba545eca41ad8f8f25af1615301d.png
[format_png 10]: /images/20220602/b47eb31090a641c58eb09bf3a30aafec.png
[format_png 11]: /images/20220602/b1ba32000dd449c38717d04397fcfde6.png
[format_png 12]: /images/20220602/f8254bf4ca584aebb375057f4bdb7b02.png
[format_png 13]: /images/20220602/9e5eade93f33442f9a4c2ef69b99071a.png
[format_png 14]: /images/20220602/b3e85e9e48ff446f818f7d86ae206b8c.png
[format_png 15]: /images/20220602/f93de7b2bfcf4f918d7f58f5ac6277cf.png
[format_png 16]: /images/20220602/36e2cd1806f74752aad51bcfcc880775.png
[format_png 17]: /images/20220602/2e3b68cdd5804f76aa0c1acb64dacc0c.png