【数据结构】树-二叉树的存储结构（大篇幅图解、c++、java）_二叉树的顺序存储结构图怎么画

GitHub同步更新（已分类）：Data_Structure_And_Algorithm-Review

公众号：URLeisure 的复习仓库
公众号二维码见文末

以下是本篇文章正文内容，下面案例可供参考。

---

二叉树的存储

顺序存储

• 二叉树也可以采用顺序存储，按照完全二叉树的节点层次编号，依次存放二叉树中的数据元素。

• 完全二叉树很适合顺序存储方式，下图所示的完全二叉树的顺序存储结构如图所示。

• 而普通二叉树在顺序存储时需要补充为完全二叉树，在对应完全二叉树没有孩子的位置补0，如下图。

• 显然，普通二叉树不适合顺序存储方式，因为有可能在补充为完全二叉树过程中，补充太多的0，而浪费大量空间，因此不同二叉树一般使用链式存储。

链式存储

• 二叉树最多有两个“叉”，即最多有两棵子树。

• 二叉树采用链式存储方式：

• 每个节点包含一个数据域，存储节点信息；还包含两个指针域，指向左右两个孩子。

• 于是，普通的二叉树就可以存储为二叉链表的形式，如图。

• 一般情况下，二叉树采用二叉链表存储即可，但是在实际问题中，如果经常需要访问双亲节点，二叉链表存储则必须从根出发查找其双亲节点，这样做非常麻烦。

• 这时可以采用，三叉链表。

• 再画个图。

二叉树的创建

• 从二叉树的定义可以看出，它是递归定义的（除了根之外，左、右子树也是一棵二叉树），因此可以用递归来创建二叉树。

• 递归创建二叉树有两种方法，分别是询问法和补空法。

• 询问法是为了更好的理解二叉树创建的过程，要是直接复制代码去做题，hh。

询问法

1. 每次输入节点信息后，询问是否创建该节点的左子树。
   如果是，则递归创建其左子树，否则左子树为空。

2. 询问是否创建该节点的右子树。
   如果是，则递归创建其右子树，否则其右子为空

算法步骤

1. 输入节点信息，创建一个节点T。
2. 询问是否创建T的左子树，如果是，则递归创建其左子树，否则其左子树为NULL。
3. 询问是否创建T的右子树，如果是，则递归创建其右子树，否则其右子树为NULL。

例如，输入下图二叉树。

• 输入为：(java中要换行输入)
  $$AYBYDNNYENNYCYFNYGNNN$$

1). 图解

1. 请输入节点信息：A
   输入后创建节点A，如图。（谁强迫症，来领死。我就弄一根长一根短）
   
2. 是否添加A的左孩子?(Y/N) Y
3. 请输入节点信息：B
   输入后创建节点B，作为A的左孩子，如图。(这图难受吗？)

4. 是否添加B的左孩子？(Y/N) Y

5. 请输入节点信息：D
   输入后创建节点D，作为B的左孩子，如图。
   

6. 是否添加D的左孩子？(Y/N) N

7. 是否添加D的右孩子？(Y/N) N
   输入后D的左右孩子均为空，如图。
   

8. 是否添加B的右孩子？(Y/N) Y

9. 请输入节点信息：E
   输入后创建节点E，作为B的右孩子，如图。
   

10. 是否添加E的左孩子？(Y/N) N

11. 是否添加E的右孩子？(Y/N) N
    输入后E的左右孩子均为空，如图。
    

12. 是否添加A的右孩子？(Y/N) Y

13. 请输入节点信息：C
    输入后创建节点C，作为A的右孩子，如图。
    

14. 是否添加C的左孩子？(Y/N) Y

15. 请输入节点信息：F
    输入后创建节点F，作为C的左孩子，如图。
    

16. 是否添加F的左孩子？(Y/N) N
    即F的左孩子为空，如图。
    

17. 是否添加F的右孩子？(Y/N) Y

18. 请输入节点信息：G
    输入后创建节点G，作为F的左孩子，如图。
    

19. 是否添加G的左孩子？(Y/N) N

20. 是否添加G的右孩子？(Y/N) N
    输入后G的左右孩子均为空，如图。

21. 是否添加C的右孩子？(Y/N) N
    输入后C的右孩子均为空，如图。
    
22. 二叉树创建完毕。（真累）

2). 代码

• 递归实现只用几行。

先创建一个结构体（内部类），包含数据域，和两个孩子指针域。

c++代码如下（示例）：

typedef struct BNode{
    char data;
    BNode *lchild,*rchild;
}*Btree;
1
2
3
4

java代码如下（示例）：

public static class BNode{
    String data;
    BNode lchild,rchild;
}
1
2
3
4

创建树

c++代码如下（示例）：

void CreateTree(Btree &T){
    char ch;
    cout<<"请输入节点信息："<<endl;
    T = new BNode;
    cin>>T->data;

    cout<<"是否添加【"<<T->data<<"】的左孩子?(Y/N)"<<endl;
    cin>>ch;
    if(ch == 'Y'){
        CreateTree(T->lchild);
    }else{
        T->lchild = NULL;
    }

    cout<<"是否添加【"<<T->data<<"】的右孩子?(Y/N)"<<endl;
    cin>>ch;
    if(ch == 'Y'){
        CreateTree(T->rchild);
    }else{
        T->rchild = NULL;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

java代码如下（示例）：

public BNode createTree(BNode T){
    String ch;
    Scanner sc = new Scanner(System.in);
    System.out.println("请输入节点信息：");
    T = new BNode();
    T.data= sc.nextLine();//用Scanner.nextLine()的时候一定要注意，换行输入
    System.out.println("是否添加【"+T.data+"】的左孩子?(Y/N)");
    ch = sc.nextLine();
    if(ch.equals("Y")){
        T.lchild = createTree(T.lchild);//跟c++的递归不太一样，注意java的递归“陷阱”
    }else{
        T.lchild = null;
    }

    System.out.println("是否添加【"+T.data+"】的右孩子?(Y/N)");
    ch = sc.nextLine();
    if(ch.equals("Y")){
        T.rchild = createTree(T.rchild);//跟c++的递归不太一样，注意java的递归“陷阱”
    }else{
        T.rchild = null;
    }
    return T;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

补空法

• 补空法时值如果左子树或右子树为空时，则用特殊字符补空，如 “#”，然后按照根、左子树、右子树的顺序，得到先序遍历序列，根据该序列递归创建二叉树。

算法步骤

1. 输入补空后的二叉树先序遍历序列。
2. 如果输入ch == “#”，T = NULL；否则创建一个新节点T，令T.data = ch；递归创建T的左子树；递归创建T的右子树。

例如，输入下图二叉树。

输入为：(java中要换行输入)
$$ABD\#\#E\#\#CF\#G\#\#\#$$

1). 图解

1. 读取第1个字符A，创建一个新节点，如图。然后递归创建A的左子树。

2. 读取第2个字符B，创建一个新节点，作为A的左子树，如图。然后递归创建B的左子树。

3. 读取第3个字符D，创建一个新节点，作为B的左子树，如图。然后递归创建B的左子树。

4. 读取第4个字符#，说明D的左子树为空。然后递归创建D的右子树。

5. 读取第5个字符#，说明D的右子树为空，如图。然后递归创建B的右子树。
   

6. 读取第6个字符E，创建一个新节点，作为B的右子树，如图。然后递归创建E的左子树。
   

7. 读取第7个字符#，说明E的左子树为空。然后递归创建E的右子树。

8. 读取第8个字符#，说明E的右子树为空，如图。然后递归创建A的右子树。
   

9. 读取第9个字符C，创建一个新节点，作为A的右子树，如图。然后递归创建C的左子树。

10. 读取第10个字符F，创建一个新节点，作为C的左子树，如图。然后递归创建F的左子树。
    
11. 读取第11个字符#，说明F的左子树为空。如图，然后递归创建F的右子树。

12. 读取第12个字符G，创建一个新节点，作为F的右子树，如图。然后递归创建G的左子树。

13. 读取第13个字符#，说明G的左子树为空。然后递归创建G的右子树。
14. 读取第14个字符#，说明G的右子树为空，如图。然后递归创建C的右子树。

15. 读取第15个字符#，说明C的右子树为空，如图。
    

• 序列读取完毕，二叉树创建成功。

2). 代码

先创建一个结构体（内部类），包含数据域，和两个孩子指针域。(不能说跟上面很像，只能说跟上面一模一样)

c++代码如下（示例）：

typedef struct BNode{
    char data;
    BNode *lchild,*rchild;
}*Btree;
1
2
3
4

java代码如下（示例）：

public static class BNode{
    String data;
    BNode lchild,rchild;
}
1
2
3
4

创建树

c++代码如下（示例）：

void CreateTree(Btree &T){
    char ch;
    cin>>ch;
    if(ch != '#'){
        T = new BNode;
        T->data = ch;
        CreateTree(T->lchild);
        CreateTree(T->rchild);
    }else{
        T = NULL;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

java代码如下（示例）：

public BNode createTree(BNode T){
    Scanner sc = new Scanner(System.in);
    String ch = sc.nextLine();
    if(ch.equals("#")){
        T = null;
    }else{
        T = new BNode();
        T.data = ch;
        T.lchild = createTree(T.lchild);
        T.rchild = createTree(T.rchild);
    }
    return T;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

关注公众号，感受不同的阅读体验

下期预告：二叉树的遍历

明天最后一篇，放假！！！2月7号再更新。