二叉树

mac2022-06-30 59

需再次了解：

package com.qdcz.breadth.demo;

import java.util.ArrayList;import java.util.List;

/** * * Title: TwoforktreeAl * Description: * 二叉树定义：二叉树(binary tree)是结点的有限集合，这个集合或者空，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成. * 二叉树与一般树的区别: * 一般树的子树不分次序，而二叉树的子树有左右之分. * 由于二叉树也是树的一种，所以大部分的树的概念，对二叉树也适用. * 二叉树的存贮：每个节点只需要两个指针域（左节点，右节点）,有的为了操作方便也会增加指向父级节点的指针，除了指针域以外，还会有一个数据域用来保存当前节点的信息 * 二叉树的特点 : * 性质1：在二叉树的第i层上至多有2^(i-1)个节点(i >= 1) * 性质2：深度为k的二叉树至多有2^(k-1)个节点(k >=1) * 性质3：对于任意一棵二叉树T而言，其叶子节点数目为N0,度为2的节点数目为N2，则有N0 = N2 + 1。 * 性质4：具有n个节点的完全二叉树的深度。 * 二叉树的遍历分为三种：前序遍历中序遍历后序遍历 * 前序遍历：按照“根左右”,先遍历根节点，再遍历左子树，再遍历右子树 * 中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树 * 后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点 * <a href="http://blog.csdn.net/gfj0814/article/details/51637696">具体资料</a> * Company:奇点创智 * Version:1.0 * @author Administrator * @date 2017年6月6日上午11:06:49 */public class TwoforktreeAl { private Node root; private List<Node> list=new ArrayList<>(); public TwoforktreeAl() { init(); } /** * *Title:init *Description:初始化。先从叶子开始。由叶到跟 *@return void *@author Administrator *@date 2017年6月6日上午11:05:44 */ private void init() { Node x=new Node("X",null,null); Node y=new Node("Y",null,null); Node d=new Node("D",x,y); Node e=new Node("E",null,null); Node f=new Node("F",null,null); Node c=new Node("C",e,f); Node b=new Node("B",d,null); Node a=new Node("A",b,c); root=a; } /** * * Title: Node * Description:定义节点类 * Company: * Version: * @author Administrator * @date 2017年6月6日上午11:02:17 */ private class Node{ private String data; private Node lchid;//定义指向左边字树的指针 private Node rchild;//定义指向右子树的指针 public Node(String data, Node lchid, Node rchild) { super(); this.data = data; this.lchid = lchid; this.rchild = rchild; } @Override public String toString() { return "[data=" + data + ", lchid=" + lchid + ", rchild=" + rchild+"]" ; } }

/** * *Title:preOrder *Description:二叉树初期遍历，遍历结果放List;前序遍历:ABDXYCEF *@param node *@return void *@author Administrator *@date 2017年6月6日上午11:01:33 */ public void preOrder(Node node){ list.add(node); if(node.lchid!=null){//如果左子树不为空继续往左找，在递归调用方法的时候一直会将子树的根存入list，这就做到了先遍历根节点 preOrder(node.lchid); } if(node.rchild!=null){//无论走到哪一层，只要当前节点左子树为空，那么就可以在右子树上遍历，保证了根左右的遍历顺序 preOrder(node.rchild); } } /** * *Title: inOrder *Description:对二叉树进行中期遍历，结果存list *@param node *@return void *@author Administrator *@date 2017年6月6日上午11:00:39 */ public void inOrder(Node node){ if(node.lchid!=null){ inOrder(node.lchid); } list.add(node); if(node.rchild!=null){ inOrder(node.rchild); } } /** * *Title: postOrder *Description:对二叉树后期遍历,遍历结果储到List中 *@param node *@return void *@author Administrator *@date 2017年6月6日上午10:59:05 */ public void postOrder(Node node){ if(node.lchid!=null){ postOrder(node.lchid); } if(node.rchild!=null){ postOrder(node.rchild); } list.add(node); } /** * *Title:getTreeDepth *Description:返回当前深度 * 说明: * 1、如果一棵树只有一个结点，它的深度为1。 * 2、如果根结点只有左子树而没有右子树，那么树的深度是其左子树的深度加1； * 3、如果根结点只有右子树而没有左子树，那么树的深度应该是其右子树的深度加1； * 4、如果既有右子树又有左子树，那该树的深度就是其左、右子树深度的较大值再加1。 * *@param node *@return *@return int *@author Administrator *@date 2017年6月6日上午10:57:25 */ public int getTreeDepth(Node node){ if(node.lchid==null&&node.rchild==null){ return 1; } int left=0,right=0; if(node.lchid!=null){ left=getTreeDepth(node.lchid); } if(node.rchild!=null){ right=getTreeDepth(node.rchild); } return left>right? left+1:right+1; } /** * *Title: getResult *Description:获取遍历结果 *@return *@return List<Node> *@author Administrator *@date 2017年6月6日上午10:57:09 */ public List<Node> getResult(){ return list; } public static void main(String[] args) { TwoforktreeAl tfa=new TwoforktreeAl(); System.out.print("根节点为："+tfa.root.toString()); System.out.println(); tfa.postOrder(tfa.root); for (Node node : tfa.getResult()) { System.out.print(node.data); } System.out.println(); System.out.println("树的深度是："+tfa.getTreeDepth(tfa.root)); }}

转载于:https://www.cnblogs.com/1x-zfd50/p/6959146.html

相关资源：JAVA上百实例源码以及开源项目

最新回复(0)