递归实现二叉树&java
参考资料：
今天顶着要交年终文档的压力，总算理清了递归方式实现二叉树的方法，彻底弄明白要如何建一颗二叉树了！终于了切了一桩心愿！苦苦思索近两个星期了，郁闷得快不行了。终于一见庐山真面目，真是凡事一定要坚持到底呀！
言归正传，下面讲如何创建二叉树，以及遍历二叉树。
一、 首先记录一下自己一直迷惑不解的几个问题
一颗二叉树是如何表示的呢？为什么 yanghui 说返回一个根 root 结点就行了呢？
二叉树结点的结构应该如何设置？以前都是
} 就行了，为什么
yanghui ， chexiaoyao 他们建的树是第一个孩子和第一个弟弟的结构，有层次（ int level ）等项呢？
递归怎么写？递归实现一颗树又怎么写？
创建一个树的函数（ buildTree(),insert(),create() ）应该怎么写？应该接收什么参数，返回什么？为什么 yanghui 说肯定要传一个 root 参数，并且返回一个根 root 结点呢？不传根
root 参数可以吗？返回的结点好像是每次加入的新结点呀，怎么直接 return root ，就是根 root 结点了呢？真是想不明白啊。一个研二的学生了，也不好意思去问别人，人家都是考研过来的，这些早就熟烂了。
根据网上的建议，看了递归的内容，重新了解了堆栈的概念，看了自己买的《数据结构
算法与应用 C++ 》二叉树部分，递归方法应该是掌握了，这本书中罗列了三种递归的遍历方式，清晰明了。但是偏偏我最想要的内容建立二叉树的函数，这本书里没有，有的只是根据已有的左右子树合并成一颗新树，晕，这点谁不会！郁闷啊，难怪自己一直没有理解如何建立二叉树，一则是完成
wuping 老师的程序的时候，照着她的书拷贝程序，程序调通了就万事 ok ，哪里还管其他的，二则自己的救命草就是这本书，这本书没有，自己肯定也没去思考过，更没有去找过其他的资料。
二、 在编码实践中领悟和解决上述问题
在 baidu 和 google 上搜索了众多的资料，但是搜索结果很令人失望，没讲什么内容，而且程序还不能确保正确。大部分也都是
c 或者 c++ 写的，
java 的程序很难搜索到。看了一两天这些网页上的程序，感觉思路越来越乱了！
某一天上午，突然灵光一动，上次自己搜索到的决策树的好东西都是在
google 中用全英文的关键字搜索到的，以前看过一个帖子提过 google 中如果用英文检索，会得到很多好结果。于是，在 google 中输入“ Binary Trees ”，哇，第一条的内容是斯坦福大学 CS 专业的二叉树的代码和讲解，并且有 C,C++,JAVA 三个版本的代码，以及详细的讲解，这正是我梦寐以求的资料！我知道我将有希望搞定二叉树了！
2.1 BinaryTree 类的代码如下：
http://cslibrary.stanford.edu/110/BinaryTrees.html
// BinaryTree.java
public class BinaryTree {
// Root node pointer. Will be null
for an empty tree.
private Node root ;
private static class Node {
Node left ;
Node right ;
int data ;
newData) {
left = null ;
right = null ;
data = newD
public BinaryTree() {
root = null ;
public void insert( int data) {
root = insert( root , data);
private Node insert(Node node, int data) {
if (node== null ) {
node = new
Node(data);
if (data &= node. data ) {
node. left = insert(node. left , data);
node. right = insert(node. right , data);
return (node); // in any case, return the new pointer to the
public void buildTree( int [] data){
& for ( int i=0;i length
& insert(data[i]);
public void printTree() {
& printTree(
out .println();
private void printTree(Node node) {
& if (node == null ) return ;
& // left, node itself, right
& printTree(node.
out .print(node. data + "& "
& printTree(node.
测试类代码如下：
//test.java
public class test {
public static void main(String[] args) {
BinaryTree biTree=new BinaryTree();
int[] data={2,8,7,4};
biTree.buildTree(data);
biTree.printTree();
private static class Node {
Node left ;
Node right ;
int data ;
newData) {
left = null ;
right = null ;
data = newD
2.2.1 注意它的封装性和访问控制权限。设置为 private 类以及 BinaryTree 的函数都相应有 private 和
public 方法来实现很好的封装和访问控制，这种方式以后自己要多加学习，积极运用。
2.2.2 把类设置为
static 的作用和艺术？？自己还没有理解，也还没有查资料，有待学习。。。不用
static 关键字程序也能运行。 Static 类有何用途呢？？
2.3 关键函数
private Node insert(Node node, int data) {
if (node== null ) {
node = new
Node(data);
if (data &= node. data ) {
node. left = insert(node. left , data);
node. right = insert(node. right , data);
return (node); // in any case, return the new pointer to the
自己对这个 insert() 研究了两三天，今天总算琢磨明白了！
2.3.1 为什么需要
Node node 参数？能不要这个参数吗？也就是这个函数如果是 insert(int data) 可以实现创建二叉树的功能吗？
编码实践实验：
Node node 参数去掉，写一个函数 insert(int data) 如下：
private Node insert( int data) {
if (node== null ) {
root = new
Node(data);
if (data &= root. data ) {
root. left = insert(data);
root. right = insert(data);
return (node); // in any case, return the new pointer to the
这时，程序运行会报一大堆的 stack 溢出错误。刚开始怎么也想不明白为什么会 stack 溢出。后来，自己手工用一个例子数据 {2 ，
6 ， 4} 一步一步按照上述代码走一遍，终于发现错误根源！当运行到 data ＝ 1 的时候，程序便在这里
” root. left = insert(data); ” 进入死循环了！！因为没有退出递归的条件！！
发现问题后，思索了一会，发现其实还是自己根本没有理解递归！这个程序是递归算法，递归算法的本质是要有一个不断递归的变量，比如说求
n ！阶层的递归函数中，要传一个 n 变量，并且 n 变量要每次调用都自减
1 。写一个递归函数就要先清楚要根据哪一个自变化的递归变量递归呀！！上述
insert(int data)
函数没有了递归变量 Node node ，当然就进入死循环， stack 溢出了！
所以，如果要用递归的方式实现创建二叉树的函数，那么这个根 root 结点参数肯定是要有的！
现在确定， insert 函数必须有两个参数。下面接着讨论返回值的问题。
2.3.2 为什么需要返回值？返回值为 void 可以吗？ C ＋＋版本的建树函数是可以不用返回值的。
1 ）把返回值去掉，写一个函数 void insert(Node node ， int
data) 如下：
private void insert(Node node, int data) {
if (node== null ) {
node = new
Node(data);
if (data &= node. data ) {
insert(node. left
insert(node. right
这时程序运行，没有任何的输出结果。百思不得其解呀！后来考虑到
C++ 中是传引用或者指针，而 java 中是值传递的问题，猜到可能是没有返回值的话， root 数据成员可能始终为空，因为函数的调用丝毫不能影响实参。于是加上
root 的返回值，代码如下：
private Node insert(Node node, int data) {
if (node== null ) {
node = new
Node(data);
if (data &= node. data ) {
insert(node. left
insert(node. right
此时，插入数据 int data[]={2,1,3,6,4}, 程序有输出了，但是只输出“ 2 ”，也就是只能输出 root 根结点的值。于是，把 root.left 和
root.right 的引用加上，因为猜想可能还是因为 java 是值传递的问题，使得 root.left 和
root.right 始终为空。加上后代码如下：
private Node insert(Node node, int data) {
if (node== null ) {
node = new
Node(data);
if (data &= node. data ) {
node. left = insert(node. left , data);
&&&&&&node.
right = insert(node. right , data);
return (node); // in any case, return the new pointer to the
哈，验证了自己的猜想，此时能够正确输出结果了：（中序遍历）
1& 2& 3& 4& 6
44 了，通过今晚，二叉树的困惑已经没太大问题了！这两个星期时常对它们的苦苦思索也将告终，虽然有点累了，也担心明早起不来，而且还要交文档，但心情还是挺愉快的。总算没有辜负先放弃文档的代价。
二叉树对别人来说可能是微不足道的程序，但这次对于我却至关重要，关键是信心的问题，现在又对自己充满信心了！不怕乌龟跑得慢，就怕它没能坚持一直往前冲！
最后小结一下二叉树的知识点：
1） 理解递归方法，理解要又一个自变化的递归变量作参数；
2） 理解编译原理的 stack 的概念；
3） 理解引用调用，值调用的方式；
4） 理解 root 根结点的引用；创建一颗树时，要返回一个 root 根结点的应用，这样才能根据 root 找到这颗树！
5） 进一步加深了对写一个函数关键要确定接口，即参数和返回值；
6） 理解上述 private Node insert(Node node, int data) 函数为什么每次调用得到都是
root 根结点，而不是新加入的新结点。这一点很重要。自己可以手工一步一步把代码走一遍就明白了！
7） 这次调程序的一个经验和收获：
yanghui 说的，写程序之前，自己也手工算一遍并走一遍！这点太重要了，尤其时算法类的程序！这次能够最终理解二叉树，就是靠手工一步一步走一遍，最终发现问题所在的！
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。/** 二叉树深度的递归算法 */&
int depth(BTree root)
int ldepth,
if(!root) & &&return 0;
ldepth = depth(root-&lchild);
rdepth = depth(root-&rchild);
return ldepth&rdepth?ldepth+1;rdepth+1;
/** 二叉树深度的非递归算法（在中根遍历算法的基础上修改的来）
http://blog.csdn.net/panqiaomu/archive//1612556.aspx */
int depth2(BTree root){
int top = 0;
int depth = 0,temp = 0;//temp 保存当前单分支的最大值
BTree nodePointer[MAX_TREE_DEGREE];
while(p || top & 0){
nodePointer[top] =
++ //统计单分支的深度&
p = nodePointer[top];
if(p == NULL){ //单分支结束
if(depth & temp )
Views(...) Comments()工具类服务
编辑部专用服务
作者专用服务
遍历二叉树的递归与非递归算法浅析
二叉树是数据结构中最常见的一种存储形式,而遍历二叉树又是二叉树中最重要的操作.该文分别以递归和非递归两种不同的算法来分析遍历二叉树的过程,旨在用简单明了的方法来实现二叉树的遍历,且先序、中序、后序三种遍历方式都可通过这两种算法实现.
作者单位：
新乡学院教务处,河南新乡,453003
年，卷(期)：
机标分类号：
在线出版日期：
本文读者也读过
相关检索词
万方数据知识服务平台--国家科技支撑计划资助项目（编号：2006BAH03B01）(C)北京万方数据股份有限公司
万方数据电子出版社