二叉树的存储结构

目录

引言：

顺序存储结构

对一般的二叉树

二叉树的链式存储结构

创建二叉树 CreateBTNode(*b,*str)

● 第七步 ： 遍历到 “ ，”

通过上面的演示  :

        下面我们开始提取规范性的步骤 , 进行程序设计

所以现在我们进行程序设计:

---

引言：

        对于二叉树的存储，我们可以采取顺序存储和链式存储结构

顺序存储结构

● 按编号次序存储节点

        • 对树中每个节点进行编号

        • 其编号从小到大的顺序就是节点在连续存储单元的先后次序。

---

 我们是从编号为1开始，为了保持数组位序和编号保持一致，所以我们从数组下标 1 开始

我们通过观察， 可以看出二叉树的编号的规律：

● 有分支节点的编号，即可求其子女的编号

         • 若编号为 i 的节点的左孩子节点的编号为 2 i ; 右孩子节点的编号为（2 i + 1）.

●有子女的节点，即可求其双亲的编号（偶数编号/2 , （奇数编号 - 1)/2 )

         •除树根节点外，若一个节点的编号为 i , 则它的双亲节点的编号为⌊ i /2 ⌋

对一般的二叉树

      

 上面我们介绍的是完全二叉树的顺序存储 ， 但是并不是所有的二叉树都是完全二叉树，所以我们就要想办法对一般二叉树进行编号，然后让其编号对应数组的位序

---

● 先用空节点补全成为完全二叉树

● 再对节点编号

● 最后确定存储

 对空节点补全，只是想象的，形式上的补全，我们补全的目的是能够把编号做下去，对于补全完全二叉树的空缺节点，对我们来说是无关紧要的

---

当我们按照完全二叉树的形状进行编号的时候 ， 我们再把其存储在数组里面，即可

对于空缺节点，我们用特殊符号代替即可

---

定义存储二叉树节点的数组

|| MaxSize 为最大编号加一，数组从0开始，编号从1开始
typedef ElemType SqBTree[MaxSize];
||树对应的字符串
SqBTree bt = "#ABD#C#E######F";

给出节点编号，求子女：

bt[2*i],bt[2*i+1]

给出节点编号，求其父母编号：
 

bt[⌊i/2⌋]
或者：
判断编号为偶数：
bt[i/2]
编号为奇数：
bt[(i-1)/2]

二叉树的链式存储结构

其中，

● data 表示值域，用于存储对应的数据元素（一般是char类型）

● lchild 和 rchild 分别表示左指针域和右指针域，用于分别存储左孩子节点和右孩子节点（即左、右子树的根节点）的存储位置。

typedef struct node
{
	ElemType data;
	struct node *lchild,*rchile;
}BTNode;

 接下来，根据图示进行构建二叉树的链式存储结构：

创建二叉树 CreateBTNode(*b,*str)

根据上面图示的例子：

我们既然要构造二叉树，输入的是字符串，所有我们把上面的二叉树用字符串来表示

例：str ------ A（ B（D ,（，G）），C (  E ，F ) ）

我们要把此字符串转换成如图所示的链式二叉树：

---

下面，我们逐个便利字符串 ， 然后利用人脑来构建二叉树，然后从中找到规范性的规律，进而进行程序化设计：

---

●第一步： 遍历到 “A” 。

        • 当我们看到 A , 就断定 A 是此树的根节点

---

 ● 第二步：遍历到 “（ ” 。

        • 当我们看到 ‘（ ’就知道，我们该到下一个层次了， 就是A的子树了。

但是，接下来的子树是A 的左孩子还是右孩子呢？

如果接下来直接出现一个元素，当然是左孩子， 如果接下来出现一个逗号，逗号后面的元素当然是右孩子

---

● 第三步 ： 遍历到“B”

        •  B 前一个元素是 “（ ” ， 也就意味着,此时出现 B , 那么 B 将作为 A 的左孩子

 

---

● 第四步 ： 遍历到“（”

        • 此时遇到 “（ ” ，说明套里有套 ， B 还有子树，所有应该先处理 B 

接下来 ，如果出现元素，就是B 的左孩子，如果出现逗号，那接下来 ，再出现元素就是B的右孩子 ，欲知后事如何，请接着遍历 

        • 此时，我们有发现一个问题 ， 我们根据图示知道 ， 遍历到 “（” ， 刚才遇到了 B ，所以接下来处理的是 B 的子树， 但是计算机怎么知道，我们是需要处理元素是 后遇到的 B呢 ？ 还是先遇到的 A 呢？

        • 我们人脑当然知道 ， 我们先遇到树根 ， 然后接着遇到树根的孩子 ，我们要接着处理 孩子的孩子 ，所以遇到“（ ”，当然是处理的是 后进来的 B 的子树 

        • 所以我们怎么让计算机 ，懂得 后进来的 ， 弹出接着处理呢 ？ 

        • 我们此时会想到先进后出 ， 后进先出 ， 这不就是栈结构吗？ 

        • 我们遇到 A , 就把 A 存起来 ， 然后接下来的元素，就是A 的子树 ； 我们后来又遇到 B， B后边有“（” ， 我们就把 B  压入栈顶 ， 然后我们接下来处理的元素 ，就是 栈顶 B  的孩子 ， 直到遇到 “）” 我们才能断定此层嵌套结束， 弹出栈顶的一个根节点。

---

● 第五步：遍历到“ D ”

        • 我们刚才已经知道，前一个元素是 “（  ” ，遇到元素的话 ， 此元素就是 栈顶元素的左孩子 ， 我们接着加入图示：

---

● 第六步 ： 遍历到 “ （ ”

        • 我们此时遍历到 “ （ ” ， 就应该知道 ， 前一个元素有孩子了， 所以我们要把前一个创建的节点 “ D ” 压入栈顶 。

 

---

● 第七步 ： 遍历到 “ ，”

        • 很抱歉 ，说明 栈顶元素 D ,其没有左孩子， 就期待是否下一个字符是否是字母，是字符 ，即是其右孩子

---

●第八步： 遍历到 “ G ”

        •  上一步我们遇到 “，”说明如果此时遇到 字母 ，其就是栈顶元素的右孩子 

        • 此时我们思考 ，我们人脑通过判断，通过 上一步遇到 “，” 可以推断出下一步遇到 字母就可以把其称作栈顶元素的右孩子的 。 但是计算机只会一步一步比较 ，它是不会前后兼顾的 

        • 所以 ，当我们在第七步 遇到 “ ，” 的时候 ，我们可以对特定变量进行赋值 ，然后计算机对其赋值进行对比 ，对比成功后，跳转到与数值对应的的符合人脑逻辑的操作 ，从而补足计算机的短板 ，形成严密逻辑 ， 进行程序化的设计 

        • 所以 ， 我们在遍历到特定字符的时候  ，我们可以对特定变量赋值 ，进而引导计算机进行相关操作

---

 第九步 ：遍历到 “ ）” ， 

我们知道 ，此时栈顶元素 “D" 已经没有节点可以构建 ，所以就需要出栈

---

第十步： 又一次遍历到 “）” ，我们接着出栈，栈顶元素

---

第 十一步 ： 遍历到“，” 此时说明 接下来如果遇到字母 ，那么这个字母就是栈顶元素的右孩子 ，但是接下来的都是未知 ， 所以 ，我们对 K 进行赋值 为 2 ， 当下一个元素是 字母时， 其申请空间 ，然后通过对比到 K = 2 时， 我们就让 K 作为栈顶元素 A  的右孩子 

        • 有些同学说 ， 如果不是字母呢 ？ 那 K 会不会影响接下来的操作呢？ 不会的 ， 当遇到 “）” 我们也可以对 K 进行赋值 ，然后操作 ， K  的值会根据遇到的字符而改变其值的

---

第十二步：

         遍历到 “ C ” ，为 C 创建空间 ，然后此时 K =2 ,所以我们让 C 成为栈顶的节点 A 的右孩子

---

第十三步:

        遍历到" ( ",说明我们需要让前一个刚创建的元素入栈 , 此节点有孩子了 , 所以我们把 C 压入栈顶 ,与此同时 , 我们也要让 k = 1 , 表示下一个创建的元素, 变成栈顶元素的左孩子

---

第十四步:

        遍历到"E" , 此时 k = 1 , 所以 我们让栈顶元素 C 的左孩子指针指向 E

---

第十五步:

        遍历到 " , " , 说明下一个元素如果是字母的话 , 就成为栈顶元素的右孩子 , 所以此时 k 赋值为 2

---

第十六步:

        遍历到 " F "  , 并且此时 k = 2 ,所以 F 成为 栈顶元素的右孩子

---

第十七步:

        遍历到 " ) " , 说明我们要把栈顶元素出栈了 ,

---

第十八步:

        遍历到 " ) " , 说明我们接着要把栈顶元素出栈.

第十九步:

        遍历到 " \0 " , 说明遍历构建结束

通过上面的演示  :

        下面我们开始提取规范性的步骤 , 进行程序设计

我们遍历字符串 , 需要一个字符来承载每次遍历的数据, 设此字符为 ch 

 ● 扫描采用括号表示法表示二叉树的字符串 , 读到的字符为 ch

 ● 使用一个栈St 保存双亲节点 , k  指定其后处理的节点是 双亲节点(保存在栈中的) 左孩子节点 (k = 1) , 还是右孩子节点 ( k = 2 ) .

 ● 分以下几种情况:

        ① 若 ch = " ( " , 则将前面刚创建的节点 ,作为双亲节点进栈 

             并置 K = 1 , 表示其后创建的节点 , 将作为这个节点的左孩子节点

        ② 若 ch = " , "  表示其后创建的节点 , 作为栈顶节点的右孩子节点

        ③ 若 ch  = " ) " , 表示栈顶节点左右孩子处理完毕 , 退栈

        ④ 其他情况 :

                当 k = 1 时 , 表示这个节点作为栈顶节点的左孩子节点

                当 k = 2 时 , 表示这个节点作为栈顶节点的右孩子节点

   如此循环直到 str 处理完毕

所以现在我们进行程序设计:

传入要构建的二叉树 , 要构建的二叉树字符串数组

void CreateBTNode(BTNode *&b,char* str)
{

先构建存放双亲的栈 , 栈顶 top 指向 -1

BTNode *St[MaxSize];
int top = -1;

定义构建新节点的指针

BTNode *p = NULL;

定义遍历二叉树字符串的变量 ch 

char ch;
||ch 初始指向二叉树字符串数组的第一个元素
int j = 0;
ch = str[j];

开始构建前 , 把要构建的二叉树先置空 , 避免错乱

b = NULL;

定义我们上面所说的变量 k , 指导程序进行相关操作

int k = 0;

接下来开始遍历 , 构建二叉树链表:

while(ch !='/0')
{
    switch(ch)
    {
    || 左括号, 把之前创建节点入栈,将 k = 1,标识后面的元素为栈顶节点的左孩子
     case '(':
        top++;
        St[top] = p;
        k = 1;
        break;
    || 遇到右括号,表示栈顶节点左右孩子处理完毕,退栈
     case ')':
        top--;
        break;
    || 遇到逗号 , 标识下个字母为栈顶节点的右孩子
     case ',':
        k = 2;
        break;
    || 以上都不是 ,说明就是字母,我们就为其创造空间
    default:
    p = (BTNode*)malloc(sizeof(BTNode));
    || 节点数据区赋值为 ch
    p->data = ch;
    || 新创建的节点左右孩子置空
    p->lchild = p->rchild = NULL;
    || 此时有一个特殊情况,我们要先确定二叉树的根节点,在其基础上,进行构建
    ||当 b 为空时,那第一个创建的节点就是根节点
    if(b == NULL)
    {
        b = p;
    }
    else
    {
     || 根据 k 的值 , 进而跳转相应的操作, 为 1 ,则作为栈顶节点左孩子,为2 作为栈顶节点右孩子
        switch(k)
        {
        case 1:
               St[top]->lchild = p;
                break;
        case 2:
               St[top]->rchild = p;
                break;
        }
    }
    || 遍历下一个字符
    j++;
    ch = str[j];        
    }
}