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次，因为可能存在一条只有左或者右的数）