`
128kj
  • 浏览: 601430 次
  • 来自: ...
社区版块
存档分类
最新评论

求二叉树的一条最长路径

阅读更多
import java.util.*;   
  
public class BinaryTree {   
    protected Node root;   
  
    public BinaryTree(Node root) {   
        this.root = root;   
    }   
  
    public Node getRoot() {   
        return root;   
    }   
  
    /** 构造树 */  
    public static Node init() {   
        Node a = new Node('A');   
        Node b = new Node('B', null, a);   
        Node c = new Node('C');   
        Node d = new Node('D', b, c);   
         Node i = new Node('I');
        Node e = new Node('E',i,null);   
        Node f = new Node('F', e, null);   
        Node g = new Node('G', null, f);   
        Node h = new Node('H', d, g);   
       
        return h;// root   
    }   
  
    /** 访问节点 */  
    public static void visit(Node p) {   
        System.out.print(p.getKey() + " ");   
    }   
  
   
    // 求二叉树的高度
 static int height(Node tree) {
    if (tree == null)
	return 0;
    else {
	int leftTreeHeight = height(tree.getLeft());
	int rightTreeHeight = height(tree.getRight());;
	return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1: rightTreeHeight + 1;
    }
}

// 求二叉树的结点总数
  static int nodes(Node tree) {
   if (tree == null)
	return 0;
   else {
	int left = nodes(tree.getLeft());
	int right = nodes(tree.getRight());
	return left + right + 1;
  }
}


// 求二叉树叶子节点的总数
 static int leaf(Node tree) {
   if (tree == null)
	return 0;
   else {
	int left = leaf(tree.getLeft());
	int right = leaf(tree.getRight());
	if (tree.getLeft() == null && tree.getRight() == null)
		return left + right + 1;
	else
		return left + right;
    }
 }

//将二叉树所有结点的左右子树交换

static void swapTree(Node root){

  if(root != null) {

   Node tmp = root.getLeft();
   root.setLeft(root.getRight());
   root.setRight(tmp);

   swapTree(root.getLeft());
   swapTree(root.getRight());

  }
}

     /** 
     * getLeafNodes: 递归求解给定二叉树的所有叶子结点 
     * @param root   给定二叉树的根结点 
     * @param leaflist 给定二叉树的所有叶子结点 
     */  
  static void  getLeafNodes(Node root, List<Node> leaflist)  
    {  
        if (root != null) {  
            if (root.getLeft() == null && root.getRight() == null) {  
                leaflist.add(root);  
                return ;  
            }  
            getLeafNodes(root.getLeft(), leaflist);  
            getLeafNodes(root.getRight(), leaflist);  
        }  
    }  

  
  /** 
     * longestPath: 递归求解给定二叉树的一条最长路径 如果有多条,输出其中一条
     * @param root  给定二叉树的根结点 
     * @param longestPath 存放二叉树的最长路径上的结点 
     */  
    static void longestPath(Node root, List<Node> longestPath)  
    {  
        if (root != null) {  
            longestPath.add(root);  
            if (root.getLeft() == null && root.getRight() == null) { // 左右子树均空  
                 return ;  
            }  
         
                List<Node> leftLongestPath = new ArrayList<Node>();  
                List<Node> rightLongestPath = new ArrayList<Node>();  
                longestPath(root.getLeft(), leftLongestPath);  
                longestPath(root.getRight(), rightLongestPath);  
                if (leftLongestPath.size() >= rightLongestPath.size()) {  
                    longestPath.addAll(leftLongestPath);  
                } else if (leftLongestPath.size() < rightLongestPath.size()) {  
                    longestPath.addAll(rightLongestPath);  
                                
            }  
        }  
    }  



    /**  
     * @param args  
     */  
    public static void main(String[] args) {   
        BinaryTree tree = new BinaryTree(init());   
      

         System.out.println("叶子结点数");
         System.out.println(leaf(tree.getRoot()));
         System.out.println("总结点数");
         System.out.println(nodes(tree.getRoot()));
         System.out.println("树的高度");
         System.out.println(height(tree.getRoot()));

         System.out.println();   
         System.out.println("一条最长路径");   
         List<Node> l=new ArrayList<Node>();
         longestPath(tree.getRoot(),l);
          for(int i=0;i<l.size();i++)
               System.out.println(l.get(i).getKey());
     
    }    
  
}  
public class Node {   
    private char key;   
    private Node left, right;   
  
    public Node(char key) {   
        this(key, null, null);   
    }   
  
    public Node(char key, Node left, Node right) {   
        this.key = key;   
        this.left = left;   
        this.right = right;   
    }   
  
    public char getKey() {   
        return key;   
    }   
  
    public void setKey(char key) {   
        this.key = key;   
    }   
  
    public Node getLeft() {   
        return left;   
    }   
  
    public void setLeft(Node left) {   
        this.left = left;   
    }   
  
    public Node getRight() {   
        return right;   
    }   
  
    public void setRight(Node right) {   
        this.right = right;   
    }   
} 


下载源码
分享到:
评论

相关推荐

    二叉树的前,中,后序非递归,递归遍历,层次遍历,最长路径

    这个问题可以通过动态规划或者深度优先搜索(DFS)来解决,对于非负权重的二叉树,可以采用两次深度优先搜索,一次求最大路径,一次求最小路径,两者相减即为最长路径。 在C++实现中,`bitree.cpp`很可能是包含上述...

    寻找树中两叶子节点之间的最长路径

    选取其中较长的一条,更新该节点的最长路径长度。 4. **更新全局最长路径**:在BFS过程中,每次遇到非叶子节点时,将当前节点的最长路径与全局最长路径进行比较,如果当前路径更长,则更新全局最长路径。 5. **...

    二叉树的直径指的是该二叉树上任意两个节点路径长度中最长的一条,其长度为这两个节点之间经过的边数

    二叉树的直径指的是该二叉树上任意两个节点路径长度中最长的一条,其长度为这两个节点之间经过的边数。 可以使用深度优先搜索(DFS)来求解二叉树的直径。具体做法如下: 定义一个私有变量 diameter,用于存储当前...

    求二叉树中节点的最大距离

    这是因为每个非叶节点都会贡献两条边,而叶节点贡献一条边,但总边数比节点数少一个。 #### 结论 通过以上分析,我们不仅理解了如何求解二叉树中节点的最大距离这一问题,而且也看到了动态规划和深度优先搜索在...

    求二叉树节点的最大距离

    在计算机科学中,二叉树是一种非常重要的数据结构,而求二叉树节点的最大距离是二叉树中一个经典的问题。问题的定义是这样的:在二叉树中,计算任意两个节点之间的最大路径长度,路径长度是指路径上的边数。解决这个...

    C二叉树中的伪回文路径.zip

    在二叉树中,如果我们沿着一条路径从根节点到某个叶节点,将这条路径上所有节点的标签(也就是节点值)连接成一个字符串,如果这个字符串是回文,那么我们称这条路径为回文路径。 然而,“伪回文路径”不是严格的...

    python-leetcode面试题解之第298题二叉树最长连续序列.zip

    首先,我们要理解问题的背景:给定一棵二叉树,每个节点的值都是一个整数,我们需要找出这棵树中能形成最长连续序列的一条路径。这里的“连续序列”是指节点值构成的序列是连续的,比如1、2、3或5、6、7。我们的目标...

    图的深度广度遍历,关键路径和最短路径

    关键路径(Critical Path)是项目管理中一个重要的概念,它是指项目中从头到尾最长的一条路径,决定了项目的最短完成时间。在图中,关键路径可以视为任务之间的依赖关系,其中任何任务的延迟都会导致整个项目的延期...

    链式存储二叉树基本操作函数.rar

    7. **计算二叉树深度**:从根节点出发,沿着最长的路径到达最远的叶子节点,这条路径的长度就是二叉树的深度。可以通过递归算法实现,每次进入子树时增加深度,返回时减去1。 这些基本操作是理解和操作链式存储...

    二叉树实验报告 (1).doc

    最长路径则是所有这些路径中最长的一条,这对于理解二叉树的结构和性质非常有用。 二叉树的表示法输出也是一项重要任务。括号表示法(或称前缀表示法)使用圆括号来表示子树,如`(A(B(C)(D))(E(F(G)(H)))`。凹入...

    平衡二叉树可视化

    红黑树则是一种弱平衡的二叉查找树,它允许节点不平衡,但通过颜色属性(红色或黑色)来保证任何节点到每个叶子节点的最长路径不超过最短路径的两倍,同样保持高效的查找性能。 在Windows编程中实现平衡二叉树的...

    二叉树_二叉树_

    - 求二叉树的直径:找到最长的路径,这条路径经过两个节点,但不经过根节点。 综上所述,二叉树是数据结构的重要组成部分,其丰富的性质和操作使其在多种场景下得到广泛应用。理解并熟练掌握二叉树的原理和算法,...

    二叉树实验报告

    3. **路径查找**:能够准确地找到所有从叶子节点到根节点的路径,并输出其中最长的一条路径。 4. **二叉树表示**:使用括号表示法和凹入表示法正确地输出了二叉树的结构。 5. **资源管理**:实验最后能够释放分配给...

    二叉树的直径,PDF 版本

    二叉树的直径是指树中任意两个节点之间最长路径的长度,这条路径可能经过也可能不经过根节点root。两节点之间路径的长度由它们之间边数表示。 在解决这道题时,我们需要注意到二叉树的直径有两种可能:一是左子树的...

    二叉树的直径问题求解.pdf

    题目要求计算一棵二叉树的直径,即树中任意两个节点之间的最长路径。这条路径可以经过根节点,也可以不经过。给定的输入格式包括一个整数n,表示树的节点数,以及n-1对整数x和y,表示x是y的父亲节点。在二叉树中,x...

    数据结构二叉树实验报告.doc

    数据结构二叉树实验报告 二叉树是一种常用的数据结构,在计算机科学和信息技术领域中广泛应用。...* 实验 7.3:输出所有的叶子节点、输出所有从叶子节点到根节点的路径、输出(2)中的第一条最长的路径。

    c++实现二叉树的基本功能

    树的深度是所有节点的路径中最长的一条,而高度则是根节点到最远叶子节点的距离: ```cpp int treeDepth(TreeNode* root) { if (!root) return 0; queue*&gt; q; q.push(root); int depth = 0; while (!q.empty()...

    msyyyy#learning-plan#二叉树的深度1

    题目描述输入一棵二叉树,求该树的深度。从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

Global site tag (gtag.js) - Google Analytics