树的增删查改

1、定义方式

struct node {
    typename data;  //数据域
    node* lchild;   //左孩子
    node* rchild;   //右孩子
};

2、新建节点

node* newNode(int v) {
    node* Node = new node;  //申请一个node型变量的地址空间
    Node->data = v;         //节点权值为V
    Node->lchild = Node->rchild = NULL;     //初始状态下没有左右孩子
    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必须使用引用（因为修改了指针），而插入修改不用，则是因为改的是指针指向的内容，所以不用

总结就是如果需要新建节点，（就是对原有二叉树结构作出修改，就要引用）
如果只是修改节点内容，或仅仅遍历二叉树，就不用

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、二叉树的创建

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次大小数组，k是最大高度
左孩子编号为2x，右孩子为2x+1
(根节点从1开始，不从0开始）
事实上，二叉树也可以定义为这样，不空间消耗巨大（K个节点就需要2的K次，因为可能存在一条只有左或者右的数）