顺序存储

要点注意

顺序存储一定要把二叉树的节点编号与完全二叉树对应起来。(n为节点个数）

• i的左孩子为2i
• i的右孩子为2i+1
• i的父节点为i/2向下取整

如果该二叉树又是完全二叉树，那就爽了又多了几个可以用的条件

• 当i的2i<=n时它的左节点存在
• 当i的2i+1<=n时它的右节点存在
• 当i<=【（n/2）向下取整】为分支节点，反之为叶子节点

#include<stdio.h>

#define SIZE 100

typedef struct Node {
	int data;
	bool isEmpty=true;
}ListNode;

int main() {

	ListNode listNode[SIZE];
	for (int i = 1; i < 20; i++) {
		Node node = { i,false };
		listNode[i] = node;
		
	}

	printf("取节点序号为5的左右孩子\n");
	printf("左节点为:%d\n", listNode[5 * 2].data);
	printf("右节点为:%d\n", listNode[5 * 2+1].data);

	return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
 

链式存储

要点注意

n个节点的二叉链表共有n+1个空链域

#include<stdio.h>
#include<malloc.h>
#include<queue>
using namespace std;

typedef struct Node {
	int data;
	Node* leftchild;
	Node* rightchild;
}BiTNode,*BiTree ;



//广度优先初始化二叉树，图像和上面图片一样
void order(BiTree head) {
	queue<BiTree> q;
	BiTree node = (BiTree)malloc(sizeof(BiTree));
	q.push(head);
	int i = 2;
	while (i <16) {
		BiTree lnode = (BiTree)malloc(sizeof(BiTree));
		lnode->data = i;
		lnode->leftchild = NULL;
		lnode->rightchild = NULL;
		i++;
		BiTree rnode = (BiTree)malloc(sizeof(BiTree));
		rnode->data = i;
		rnode->leftchild = NULL;
		rnode->rightchild = NULL;
		i++;
		q.front()->leftchild = lnode;
		q.front()->rightchild = rnode;
		q.pop();
		q.push(lnode);
		q.push(rnode);


	}

}

//先序遍历该二叉树
void preOrder(BiTree temphead) {
	if (!temphead)
		return;
	printf("%d ", temphead->data);
	preOrder(temphead->leftchild);
	preOrder(temphead->rightchild);

}



int main() {

	BiTree head = (BiTree)malloc(sizeof(BiTNode));
	head->data = 1;
	order(head);
	

	//先序遍历试试看
	BiTree temphead = head;
	preOrder(temphead);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
 

如果你在学习python或者Java哪怕是C遇到问题都可以来给我留言，因为在学习初期新手总会走很多弯路，这个时候如果没有有个人来帮一把的话很容易就放弃了。身边很多这样的例子许多人学着学着就转了专业换了方向，不仅是自身问题还是没有正确的学习。所以作为一个过来人我希望有问题给我留言，说不上是帮助就是顺手敲几行字的事情。

文章来源: blog.csdn.net，作者：肥学，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jiahuiandxuehui/article/details/124565213