树

递归=传递+回归，即任务的下放和结果的回收。这个需要自己慢慢体会，其实所有递归算法实质上都是一样的，理解了就万变不离其宗了。create（node*root）{root=newnode；写上关于root的信息//初始化root节点if(root满足自定义的条件)//自定义一个递归的条件，即传递和回归的界限，这是必须的。{create(root->lchild);//建左子树create(root->rchild);//建右子树}}总体上来看，建一颗树，每一次调用creat（）都是只创建一个节点，把剩下的任务下放给create（root->lchild)和create(root->rchild)，而这两个也会重复第一个create（root）的做法，实质体现的是任务的不断下放，当达到最后的回归的界限的，结果又将不断回收，对应的是函数的不断返回，实质是退栈的过程。这个过程其实经历了一个不断进栈和不断出栈的过程，对应的是任务的不断下放和不断提交，最后栈空，即告全部任务完成！

bitree是二叉树的结点，类型为node，lchild是左子节点，rchild是右子节点，两个子节点又同时拥有它们的子节点（就是和他们的父节点一样）。和递归函数中的局部变量一样，lchild和rchild也可理解为“二叉树定义中的局部变量”，所以那并不是指向本身。

树的定义　　树（tree）是包含n（n>0）个结点的有穷集合，其中：　　（1）每个元素称为结点（node）；　　（2）有一个特定的结点被称为根结点或树根（root）。　　（3）除根结点之外的其余数据元素被分为m（m≥0）个互不相交的结合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。　　树也可以这样定义：树是有根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。　　我们可以形式地给出树的递归定义如下:　　单个结点是一棵树，树根就是该结点本身。　　设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称n1,n2,..,nk为结点n的子树。　　空集合也是树，称为空树。空树中没有结点

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个结点最多只能有两棵子树，且有左右之分。二叉树的类型1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

树的后序遍历是指先依次后序遍历每棵子树，然后访问根结点。当树用二叉树表示法(也叫孩子兄弟表示法)存储时，可以找到唯一的一棵二叉树与之对应，我们称这棵二叉树为该树对应的二叉树。那么根据这个法则可知，树的后序遍历序列等同于该树对应的二叉树的中序遍历。从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上。⑴访问结点本身（N），⑵遍历该结点的左子树（L），⑶遍历该结点的右子树（R）。以上三种操作有六种执行次序：NLR、LNR、LRN、NRL、RNL、RLN。注意：前三种次序与后三种次序对称，故只讨论先左后右的前三种次序。从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上。扩展资料：二叉树前序访问如下：从根结点出发，则第一次到达结点A，故输出A;继续向左访问，第一次访问结点B，故输出B；按照同样规则，输出D，输出H；当到达叶子结点H，返回到D，此时已经是第二次到达D，故不在输出D，进而向D右子树访问，D右子树不为空，则访问至I，第一次到达I，则输出I；I为叶子结点，则返回到D，D左右子树已经访问完毕，则返回到B，进而到B右子树，第一次到达E，故输出E；向E左子树，故输出J；按照同样的访问规则，继续输出C、F、G。二叉树中序访问如下：从根结点出发，则第一次到达结点A，不输出A，继续向左访问，第一次访问结点B，不输出B；继续到达D，H；到达H，H左子树为空，则返回到H，此时第二次访问H，故输出H；H右子树为空，则返回至D，此时第二次到达D，故输出D；由D返回至B，第二次到达B，故输出B；按照同样规则继续访问，输出J、E、A、F、C、G。参考资料来源：百度百科-二叉树参考资料来源：百度百科-二叉树遍历