【数据结构】二叉树是怎么来的？

特殊时期

专心在家学习最为稳妥

——————————————下面是正文———————————————

一.在讲述二叉树前，首先需要知道的是普通树必须知道的一些定义：

        1.子树之间是不可相交的，如以下这样的就不是树：

    2.有N个结点的树一般有N-1个结点，如以下的树有8个结点，那么就有7条边：

二.了解完补充的知识之后，我们来看一下这颗树：

       如果想要用代码来实现以上那颗树，该怎样进行一个代码的实现呢?这里有个简单的方法，就是使用结构体+链表的方式进行实现：  

        这样的设定会给在遍历的时候带来困难，我们并不知道该结点共有多少个指针指向，所以在程序处理时会带来不必要的麻烦，而如果将每个结点都设定为三个指针，没有用到的指针设定为NONE ，那么所出现的将是以下的情况：

       如果每个结点都有三个指针，那么就共有3N个指针，而所使用到的指针只有N-1个，那么就有2N+1个结点是浪费的，所以在内存分配中是不合理的。而使用“儿子-兄弟表示法”则可以最大限度的节省空间，该方法所有结点都由两个指针组成，一个指针指向其子结点（儿子），另一个指针指向其兄弟结点：

        而使用“儿子-兄弟表示法”则像图下所示：         以上的树因为每个结点有两个指针域，所有共有2N个指针域，而有N-1个结点是用到的，所以有N+1个结点是浪费的，比上面使用结构体+链表的方法节约很多空间，而将其旋转45°左右即可得：

          每个结点都有两个子结点组成，俗称“二叉树”