1珊佣、定義方式
struct node {
typename data; //數(shù)據(jù)域
node* lchild; //左孩子
node* rchild; //右孩子
};
2、新建節(jié)點
node* newNode(int v) {
node* Node = new node; //申請一個node型變量的地址空間
Node->data = v; //節(jié)點權值為V
Node->lchild = Node->rchild = NULL; //初始狀態(tài)下沒有左右孩子
return Node;
}
3锄开、查找與修改
先中后
void search(node* root, int x, int newdata) {
if (root == NULL) {
return;
}
if (root->data == x) {
root->data = newdata;
}
search(root->left, x, newdata);
search(root->right, x, newdata);
}
4、插入
isnert必須使用引用（因為修改了指針）称诗，而插入修改不用萍悴，則是因為改的是指針指向的內容，所以不用
總結就是如果需要新建節(jié)點寓免，（就是對原有二叉樹結構作出修改癣诱，就要引用）
如果只是修改節(jié)點內容，或僅僅遍歷二叉樹袜香，就不用
void insert(node* &root, int x) { //注意是星引用撕予，因為要修改這個指針的
if (root == NULL) {
root = new node(x);
return;
}
if(二叉樹的的性質，x應該插在左邊){
insert(root->left, x);
}else{
insert(root->right, x);
}
}
5蜈首、二叉樹的創(chuàng)建
node* create(int data[], int n) {
node* root = NULL;
for (int i = 0;i < n;i++) {
insert(root, data[i]);
}
return root;
}
6实抡、完全二叉樹的存儲結構
2的k次大小數(shù)組，k是最大高度
左孩子編號為2x欢策，右孩子為2x+1
(根節(jié)點從1開始吆寨，不從0開始）
事實上，二叉樹也可以定義為這樣踩寇，不空間消耗巨大（K個節(jié)點就需要2的K次啄清，因為可能存在一條只有左或者右的數(shù)）