不使用指针来完成二叉树的所有操作~
使用静态二叉链表来避免指针的使用
静态二叉链表:左右指针域使用int型来进行替代,用来表示左右子树的根结点在数组中的下标。为此建立一个大小为结点上限的node型数组,所有动态生成的结点都直接使用数组中的结点,所有对指针的操作改为对数组下标的访问。
Node数组定义~
struct node{
typename data;
int lchild;
int rchild;
}Node[maxn];
结点的动态生成可以变成静态指定~
int index = 0;
int newNode(int v){
Node[index].data = v;
Node[index].lchild = -1;
Node[index].rchild = -1;
return index++;
}
二叉树的查找、插入、建立的代码~
void search(int root, int x, int newdata){
if(root == -1) return;
if(Node[root].data == x)
Node[root].data = newdata;
search(Node[root].lchild, x, newdata);
search(Node[root].rchild, x, newdata);
}
void insert(int &root, int x){
if(root == -1) return;
if(由题目给出的二叉树性质应该插在左子树)
insert(Node[root].lchild, x);
else
insert(Node[root].rchild, x);
}
int create(int data[], int n){
int root = -1;
for(int i = 0; i < n; i++){
insert(root, data[i]);
}
return root;
}
先序遍历、中序遍历、后序遍历和层序遍历~
void preorder(int root){
if(root == -1) return;
printf("%d\n", Node[root].data);
preorder(Node[root].lchild);
preorder(Node[root].rchild);
}
void inorder(int root){
if(root == -1) return;
inorder(Node[root].lchild);
printf("%d\n", Node[root].data);
inorder(Node[root].rchild);
}
void postorder(int root){
if(root == -1) return;
postorder(Node[root].lchild);
postorder(Node[root].rchild);
postorder("%d\n", Node[root].data);
}
void LayerOrder(int root){
queue<int> q;
q.push(root);
while(!q.empty()){
int now = q.front();
q.pop();
printf("%d ", Node[now].data);
if(Node[now].lchild != -1)
q.push(Node[now].lchild);
if(Node[now].rchild != -1)
q.push(Node[now].rchild);
}
}