黑马程序员技术交流社区

标题: 遍历二叉树深度! [打印本页]
作者: lantian    时间: 2012-7-8 20:11
标题: 遍历二叉树深度!
遍历二叉树深度。java代码具体怎么实现？ 有木有代码？？
作者: 蒋映辉    时间: 2012-7-8 20:17
本帖最后由 蒋映辉 于 2012-7-8 20:28 编辑

这个 百度来的
**
* 二叉树测试二叉树顺序存储在treeLine中，递归前序创建二叉树。另外还有能
* 够前序、中序、后序、按层遍历二叉树的方法以及一个返回遍历结果asString的
* 方法。
*/

public class BitTree {
public static Node2 root;
public static String asString;

//事先存入的数组,符号#表示二叉树结束。
public static final char[] treeLine = {'a','b','c','d','e','f','g',' ',' ','j',' ',' ','i','#'};

//用于标志二叉树节点在数组中的存储位置，以便在创建二叉树时能够找到节点对应的数据。
static int index;

//构造函数
public BitTree() {
System.out.print("测试二叉树的顺序表示为：");
System.out.println(treeLine);
this.index = 0;
root = this.setup(root);
}

//创建二叉树的递归程序
private Node2 setup(Node2 current) {
if (index >= treeLine.length) return current;
if (treeLine[index] == '#') return current;
if (treeLine[index] == ' ') return current;
current = new Node2(treeLine[index]);
index = index * 2 + 1;
current.left = setup(current.left);
index ++;
current.right = setup(current.right);
index = index / 2 - 1;
return current;
}

//二叉树是否为空。
public boolean isEmpty() {
if (root == null) return true;
return false;
}

//返回遍历二叉树所得到的字符串。
public String toString(int type) {
if (type == 0) {
asString = "前序遍历：\t";
this.front(root);
}
if (type == 1) {
asString = "中序遍历：\t";
this.middle(root);
}
if (type == 2) {
asString = "后序遍历：\t";
this.rear(root);
}
if (type == 3) {
asString = "按层遍历：\t";
this.level(root);
}
return asString;
}

//前序遍历二叉树的循环算法，每到一个结点先输出，再压栈，然后访问它的左子树，
//出栈，访问其右子树，然后该次循环结束。
private void front(Node2 current) {
StackL stack = new StackL((Object)current);
do {
if (current == null) {
current = (Node2)stack.pop();
current = current.right;
} else {
asString += current.ch;
current = current.left;
}
if (!(current == null)) stack.push((Object)current);
} while (!(stack.isEmpty()));
}

//中序遍历二叉树
private void middle(Node2 current) {
if (current == null) return;
middle(current.left);
asString += current.ch;
middle(current.right);
}

//后序遍历二叉树的递归算法
private void rear(Node2 current) {
if (current == null) return;
rear(current.left);
rear(current.right);
asString += current.ch;
}

}


/**
* 二叉树所使用的节点类。包括一个值域两个链域
*/

public class Node2 {
char ch;
Node2 left;
Node2 right;

//构造函数
public Node2(char c) {
this.ch = c;
this.left = null;
this.right = null;
}

//设置节点的值
public void setChar(char c) {
this.ch = c;
}

//返回节点的值
public char getChar() {
return ch;
}

//设置节点的左孩子
public void setLeft(Node2 left) {
this.left = left;
}

//设置节点的右孩子
public void setRight (Node2 right) {
this.right = right;
}

//如果是叶节点返回true
public boolean isLeaf() {
if ((this.left == null) && (this.right == null)) return true;
return false;
}
}

作者: 383105662    时间: 2012-7-8 20:18
建议多看看毕姥爷的视频！！他讲的很清楚，直接要代码的不利于理解！！
作者: lantian    时间: 2012-7-8 20:28
有源码才能好学习。直接研究啊！！Q!
作者: 温少邦    时间: 2012-7-8 20:45
递归实现，大概就是这样：


  3. public class Tree{
  4.         private TreeNode root=null;

  6.         private int getDepth0(TreeNode tn){
  7.                 if(tn==null)
  8.                         return 0;
  9.                 int leftDepth=getDepth0(tn.left);
  10.                 int rightDepth=getDepth0(tn.right);
  11.                 if(leftDepth>rightDepth)
  12.                         return leftDepth+1;
  13.                 else
  14.                         return rightDepth+1;
  15.         }

  17.         public int getDepth(){
  18.                 return getDepth0(root);
  19.         }
  20.         
  21. }

  23. class TreeNode{
  24.         protected TreeNode left;
  25.         protected TreeNode right;
  26. }

复制代码
作者: lantian    时间: 2012-7-8 20:51
蒋映辉 发表于 2012-7-8 20:17
这个 百度来的
**
* 二叉树测试二叉树顺序存储在treeLine中，递归前序创建二叉树。另外还有能

:)ths   :handshake
作者: 韦念欣    时间: 2012-7-8 21:04
二叉树在数据结构的课本上有详细介绍哦。
作者: 位雪    时间: 2012-7-8 21:25
1、先根遍历
public void preorder(BinaryNode root){
if(root == null)
  return;
visit (root);
preorder(root.left);
preorder(root.right);
}
2、后根遍历
public void postorder(BinaryNode root){
if(root == null)
  return;
preorder(root.left);
preorder(root.right);
visit (root);
}
3、中根遍历
public voidinorder(BinaryNode root){
if(root == null)
  return;
preorder(root.left);
visit (root);
preorder(root.right);
}

书上的。。。。
作者: 位雪    时间: 2012-7-8 21:42
位丹丹 发表于 2012-7-8 21:25
1、先根遍历
public void preorder(BinaryNode root){
if(root == null)

先根遍历节点的访问次序：ABCDEFGHI
后根遍历节点的访问次序：EDFCBHIGA
中根遍历节点的访问次序：DECFBAHGI

无标题.png (85.64 KB, 下载次数: 24)

二叉树

二叉树
作者: 刘笑    时间: 2012-7-9 13:45
这是数据结构课本中的内容，楼主可以看看有关的书
作者: 彭嘉聪    时间: 2012-7-9 21:36
遍历判断两树深度大小就O了



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2