树的逻辑结构和存储结构

树的逻辑结构

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

树的存储结构

1.第一种表示方法

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

为了查找兄弟节点而增加了firstChild和right

在这里插入图片描述

第二种表示方法

指针域的个数由树的度决定

在这里插入图片描述

在这里插入图片描述

解决多出来的指针域浪费空间的办法 有几个孩子就分配几个指针域，这样可以避免指针域占据空间

在这里插入图片描述

这样每一个节点的指针域个数都可能因为孩子的数量而产生区别，那么就无法用一个节点结构体表示所有节点，造成编程困难

在这里插入图片描述

第三种表示方法

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

孩子兄弟表示法

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

如何查找兄弟节点？ 通过兄弟指针查找 如何查找孩子节点? 通过孩子指针查找到左孩子节点，再查找左孩子的所有右兄弟节点