算法笔记——树篇

二叉树的存储结构与基本操作

结点的存储结构

struct node{
	typename data; //数据域
    node* lchild; //指向左子树根结点的指针
    node* rchild; //指向右子树根结点的指针
}

node* root = NULL; //根结点的初始化

新建结点

node* newNode(int v){
    node* Node = new node;
    Node->data = v;
    Node->lchild = Node->rchild = NULL;
    return Node; //返回新建结点的地址
}

二叉树结点的查找和修改

void search(node* root, int x, int newdata){
	if(root == NULL){
        return; //空树，死胡同（递归边界）
    }
    if(root->data == x){ //找到数据域为 x 的结点，把它修改成 newdata
        root->data = newdata;
    }
    search(root->lchild, x, newdata); //往左子树搜索 x (递归式)
    search(root->rchild, x, newdata); //往右子树搜索 x (递归式)
}

二叉树结点的插入

//insert 函数将在二叉树中插入一个数据域为 x 的新结点
//注意根结点指针 root 要使用引用，否则插入不会成功
void insert(node* &root, int x){
	if(root == NULL){
        root = newNode(x); //空树，说明查找失败，也即插入位置（递归边界）
        return;
    }
    if(由二叉树的性质，x 应插在左子树){
        insert(root->lchild, x); //往左子树搜索(递归式)
    } else{
        insert(root->rchild, x); //往右子树搜索(递归式)
    }
}

二叉树的创建

//二叉树的建立
node* Create(int data[], int n){
    node* root = NULL; //新建空根结点 root
    for(int i = 0; i < n; i++){
        insert(root, data[i]); //将 data[0]~data[n-1]插入二叉树中
    }
    return root; //返回根结点
}