二叉树的链式存储结构
使用二叉链表储存二叉树
二叉链表示意图
二叉链表的存储结构
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
typedef struct BiNode {
int data;//数据域
struct BiNode *lchild, *rchild; //左孩子指针和右孩子指针
} BiNode, *BiTree;
signed main () {
return 0;
}
二叉树链式存储示意图
两个指针域如果没有该方向没有孩子就设置为NULL,否则指向下一个结点
空指针域和结点的关系
可以从边上来看(蓝色的箭头),因为根结点是没有双亲的使用只有n-1个结点右向上的蓝色箭头.因为n个结点有2n个指针域,所以由上面的规律可以看出有n-1个指针域不为空..所以2n-(n-1)为n+1所以有n+1个空指针域
三叉链表
除了有指向左孩子和右孩子的指针还有一个指向双亲的指针,便于从当前结点找到双亲结点
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cstring>
#include <unordered_set>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <sstream>
#include <queue>
#define int long long
#define yes cout<<"YES"<<'\n'
#define no cout<<"NO"<<'\n'
using namespace std;
//typedef struct BiNode {
// int data;//数据域
// struct BiNode *lchild, *rchild; //左孩子指针和右孩子指针
//
//} BiNode, *BiTree;
typedef struct TriNode {
int data;
struct TriNode *lchild, *rchild, *parent; //左孩子指针,右孩子指针和双亲指针
} TriNode, *TirTree;
signed main () {
return 0;
}