如果需要新建结点（例如往二叉树里面插入结点时，可使用下面的函数（返回类型是一个指向node的指针） node* newNode(int v) { nodeNode = new node; //申请一个node类型变量的地址空间 Node->data = v; //结点权值为v Node->lchild = Node->rchild = NULL; //初始状态下无左右孩子 return Node; //返回新节点的地址 } 1 2 3 4 5 6 查找操作是指在给定的数据域内，在二叉树里面找到所有数据域（对多个结点实行操作）为给定数据域的结点，并且对查找到的结点修改为给定的数据域 void search(noderoot,int x, int newdata){ if (root == NULL) return; //考虑为空节点的可能性 if (root->data == x) { root->data = newdata; //找到数据域为x的结点，把它修改为newdata } search(root->lchild, x, newdata);//往左子树搜索 search(root->rchild, x, newdata);//往右子树搜索 } 1 2 3 4 5 6 7 8 3.实现二叉树结点的插入 关于二叉树结点的插入，由于在没有给出插入条件的问题中，很难给出插入的具体方法。因此这里以在一棵二叉搜索树中插入为例。 插入过程的核心思想，是按照给定的插入条件（例中为二叉查找树）找到树里面的边界（死胡同），此处就是查找失败的地方，也是结点需要插入的地方 void insert(node*& root, int x) { //注意 传入的是结点指针的引用 if (root == NULL) { //空树，即查找失败，插入结点（递归边界） root = newNode(x); return; } if (root->data > x) { //往左子树搜索 insert(root->lchild, x); } else insert(root->rchild, x); //往右子树搜索 } 1 2 3 4 5 6 7 8 9 10 在上述代码中，一个关键的点就是根节点指针root使用了引用&，这样在函数中可以直接修改原变量。这么做的原因是，在insert函数中新建了一个新结点，并且把新节点的地址赋给了当层的root。如果不采用引用，root = new node 这个语句对root 的修改就无法作用到原变量，也就无法将节点加到二叉树上面。 那为什么前面的search 函数不需要加引用呢？因为search 函数修改的是指针root指向的内容，而不是root本身，对结点指向的内容的修改是不需要加引用的。