一、二叉树的递归定义

1、要么二叉树没有根结点，是一颗空树。 2、要么二叉树由根结点、左子树、右子树组成，且左子树和右子树都为二叉树。

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

1、二叉树的存储结构：        一般来说，二叉树使用链表来定义。和普通链表的区别是，由于二叉树每个结点有两条出边，因此指针域变成了两个-------分别是指向左子树的根结点地址和右子树的根结点地址。如果某个子树不存在，则指向NULL，其他地方和普通链表完全相同，因此又把这种链表叫做二叉链表，其定义方式如下： struct node{ typename data; //数据域 node* lchild; //指向左子树根结点的指针 node* rchild; //指向右子树根结点的指针 }; 由于二叉树建树前根结点不存在，因此其地址一般设为NULL: node* root = NULL; 如果需要新建结点（例如往二叉树中插入结点的时候），就可以使用下面的函数： node* newNode(int v){ node* Node = new node; //申请一个node类型变量的地址空间 Node->data = v; //结点权值为v Node->lchild = Node->rchild = NULL; //初始状态下没有左右孩子 return Node; //返回新建结点地址 } 2、二叉树的查找、修改：        查找操作是指给定数据域的条件下，在二叉树中找到所有数据域为给定数据域的结点，并将它们的数据域修改为给定的数据域。 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（递归式） } 3、二叉树结点的插入： void insert(node* &root, int x){ if(root == NULL){ root = newNode(x); return; } if(由二叉树的性质,x应该插在左子树){ insert(root->lchild, x); } else{ insert(root->rchild, x); } } 4、二叉树的创建： node* create(int data[], int n){ node* root = NULL; for(int i = 0; i < n; i++){ insert(root, data[i]); } return root; }