【数据结构】简单二叉树遍历,递归与非递归用法-Java版


维基百科

计算机科学中,二叉树(英语:Binary tree)是每个节点最多只有两个分支(不存在分支度大于2的节点)的树结构。通常分支被称作“左子树”和“右子树”。二叉树的分支具有左右次序,不能颠倒。

二叉树的第i层至多拥有2^{i-1}个节点数;深度为k的二叉树至多总共有{\displaystyle 2^{\begin{aligned}k+1\end{aligned}}-1}个节点数(定义根节点所在深度 {\displaystyle k_{0}=0}),而总计拥有节点数匹配的,称为“满二叉树”;深度为k有n个节点的二叉树,当且仅当其中的每一节点,都可以和同样深度k的满二叉树,序号为1到n的节点一对一对应时,称为“完全二叉树”。;对任何一棵非空的二叉树T,如果其叶片(终端节点)数为n0,分支度为2的节点数为n2,则n0n2 + 1。

与普通树不同,普通树的节点个数至少为1,而二叉树的节点个数可以为0;普通树节点的最大分支度没有限制,而二叉树节点的最大分支度为2;普通树的节点无左、右次序之分,而二叉树的节点有左、右次序之分。

二叉树通常作为数据结构应用,典型用法是对节点定义一个标记函数,将一些值与每个节点相关系。这样标记的二叉树就可以实现二叉查找树二元堆积,并应用于高效率的搜索和排序。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class BinaryTree {
 private TreeNode root = null;

 //构造函数,默认创建一个根节点 可传参 这里省略
 public BinaryTree() {
 root = new TreeNode(1, "A");
 }

 /**
 * 最原始的构建二叉树
 * A
 * B C
 * D E F
 */ public void createBinaryTree() {
 TreeNode nodeB = new TreeNode(2, "B");
 TreeNode nodeC = new TreeNode(3, "C");
 TreeNode nodeD = new TreeNode(4, "D");
 TreeNode nodeE = new TreeNode(5, "E");
 TreeNode nodeF = new TreeNode(6, "F");
 root.leftChild = nodeB;
 root.rightChild = nodeC;
 nodeB.leftChild = nodeD;
 nodeB.rightChild = nodeE;
 nodeC.rightChild = nodeF;
 }

 /**
 * 根据先序字符串来进行二叉树创建
 * A,B,D,#,#,E,#,#,C,#,F,#,#
 * @param data
 */ private void creatBinaryTreePre(ArrayList<String> data) {
 //为保持原始节点下标,这里传入原始大小
 creatBinaryTree(data.size(), data);
 }

 /**
 *
 * @param size 原始大小
 * @param data 待创建的节点数组
 * @return
 */ private TreeNode creatBinaryTree(int size, ArrayList<String> data) {
 String d = data.get(0);
 TreeNode node;
 //得到剩余的第一个节点在原节点串中的位置,这样就可以根据index=0判断是不是根节点
 int index = size - data.size();
 //如果是#则说明是一个空节点 返回并移除
 if (d.equals("#")) {
 node = null;
 data.remove(0);
 return node;
 }
 //不是#则创建一个新节点
 node = new TreeNode(index, d);
 //根据index判断根节点是否存在
 if (index == 0) {
 //创建根节点
 root = node;
 }
 //移除已创建的
 data.remove(0);
 //按先序递归左右
 node.leftChild = creatBinaryTree(size, data);
 node.rightChild = creatBinaryTree(size, data);
 return node;
 }

 /**
 * 求二叉树的高度
 *
 * @author Administrator
 */ public int getHeight() {
 return getHeight(root);
 }

 /**
 * A
 * B C
 * @param node
 * @return
 */ private int getHeight(TreeNode node) {
 if (node == null) {
 return 0;
 } else {
 //递归,第一次是A的时候 传入B,C,由于B没有左右B的递归i,j均为0,而return时返回的是i+1,
 // 最后返回A的递归i=1,j=1,不满足i<j,这时返回i+1,最后为2
 int i = getHeight(node.leftChild);
 int j = getHeight(node.rightChild);
 return (i < j) ? j + 1 : i + 1;
 }
 }

 /**
 * 获取二叉树的结点数
 *
 * @author Administrator
 */ public int getSize() {
 return getSize(root);
 }


 private int getSize(TreeNode node) {
 if (node == null) {
 return 0;
 } else {
 //这个很好理解,不为空就+1,因为根节点如果为空就返回了0,走到这里说明根节点不为空,得+1
 return 1 + getSize(node.leftChild) + getSize(node.rightChild);
 }
 }

 /**
 * 前序遍历——迭代
 *
 * @author Administrator
 */ public void preOrder(TreeNode node) {
 if (node == null) {
 return;
 } else {
 System.out.println("preOrder data:" + node.getData());
 preOrder(node.leftChild);
 preOrder(node.rightChild);
 }
 }

 /**
 * 前序遍历——非迭代
 */
 public void nonRecOrder(TreeNode node) {
 if (node == null) {
 return;
 }
 Stack<TreeNode> stack = new Stack<TreeNode>();
 stack.push(node);
 while (!stack.isEmpty()) {
 //出栈和进栈
 TreeNode n = stack.pop();//弹出根结点
 //压入子结点
 System.out.println("nonRecOrder data" + n.getData());
 if (n.rightChild != null) {
 stack.push(n.rightChild);
 }
 if (n.leftChild != null) {
 stack.push(n.leftChild);
 }
 }
 }

 /**
 * 中序遍历——迭代
 *
 * @author Administrator
 */ public void midOrder(TreeNode node) {
 if (node == null) {
 return;
 } else {
 midOrder(node.leftChild);
 System.out.println("midOrder data:" + node.getData());
 midOrder(node.rightChild);
 }
 }

 /**
 * 中旬遍历 非遍历
 *
 * @param node
 */ public void nonMidOrder(TreeNode node) {
 Stack<TreeNode> stack = new Stack<TreeNode>();
 while (node != null) {
 while (node != null) {
 if (node.rightChild != null) {
 stack.push(node.rightChild);
 }
 stack.push(node);
 node = node.leftChild;
 }
 node = stack.pop();
 while (!stack.isEmpty() && node.rightChild == null) {
 System.out.println(node.data);
 node = stack.pop();
 }
 System.out.println(node.data);
 if (!stack.isEmpty()) {
 node = stack.pop();
 } else {
 node = null;
 }
 }
 }

 /**
 * 后序遍历——迭代
 *
 * @author Administrator
 */ public void postOrder(TreeNode node) {
 if (node == null) {
 return;
 } else {
 postOrder(node.leftChild);
 postOrder(node.rightChild);
 System.out.println("postOrder data:" + node.getData());
 }
 }

 /**
 * 非递归实现后序遍历 单栈法
 * A
 * B C
 * D E F
 */ protected static void nonPostOrder(TreeNode p) {
 Stack<TreeNode> stack = new Stack<TreeNode>();
 TreeNode node = p, prev = p;
 while (node != null || stack.size() > 0) {
 while (node != null) {
 stack.push(node);
 node = node.leftChild;
 }
 if (stack.size() > 0) {
 TreeNode temp = stack.peek().rightChild;
 if (temp == null || temp == prev) {
 node = stack.pop();
 System.out.println(node.data);
 prev = node;
 node = null;
 } else {
 node = temp;
 }
 }
 }
 }


 public class TreeNode {
 private int index;
 private String data;
 private TreeNode leftChild;
 private TreeNode rightChild;


 public int getIndex() {
 return index;
 }


 public void setIndex(int index) {
 this.index = index;
 }


 public String getData() {
 return data;
 }


 public void setData(String data) {
 this.data = data;
 }


 public TreeNode(int index, String data) {
 this.index = index;
 this.data = data;
 this.leftChild = null;
 this.rightChild = null;
 }
 }


 public static void main(String[] args) {
 BinaryTree binaryTree = new BinaryTree();
 String[] dataArray = new String("A,B,D,#,#,E,#,#,C,#,F,#,#").split(",");
 ArrayList data = new ArrayList(Arrays.asList(dataArray));
 binaryTree.creatBinaryTreePre(data);
// binaryTree.createBinaryTree();
 int height = binaryTree.getHeight();
 System.out.println("treeHeihgt:" + height);
 int size = binaryTree.getSize();
 System.out.println("treeSize:" + size);
 binaryTree.preOrder(binaryTree.root);
// binaryTree.midOrder(binaryTree.root);
// binaryTree.postOrder(binaryTree.root);
// binaryTree.nonRecOrder(binaryTree.root);
// binaryTree.nonMidOrder(binaryTree.root);
// binaryTree.nonPostOrder(binaryTree.root);
 }
}

另外一种实现,这种使用Comparable来进行排序

import java.util.Arrays;

public class BinaryTree {
 public static void main(String[] args) {
 BinaryTreeOld bt=new BinaryTreeOld();
 bt.add("B");
 bt.add("A");
 bt.add("X");
 System.out.println(Arrays.toString(bt.toArray()));
 }
}

class BinaryTreeOld {
 public class Node {
 private Comparable data;//保存的操作数据 Comparable子类比较大小
 private Node left;
 private Node right;

 public Node(Comparable data) {
 this.data = data;
 }

 public void addNode(Node newNode) {
 if (this.data.compareTo(newNode.data) > 0) {
 if (this.left == null) {
 this.left = newNode;
 } else {
 this.left.addNode(newNode);
 }
 } else {
 if (this.right == null) {
 this.right = newNode;
 } else {
 this.right.addNode(newNode);
 }
 }
 }
 public void toArrayNode(){
 if (this.left!=null){
 this.left.toArrayNode();
 }
 BinaryTreeOld.this.retData[BinaryTreeOld.this.foot++]=this.data;
 if (this.right!=null){
 this.right.toArrayNode();
 }
 }
 }

 //--------------
 private Node root;
 private int count;
 private Object[] retData;
 private int foot = 0;

 public Object[] toArray() {
 this.foot = 0;
 this.retData = new Object[this.count];
 this.root.toArrayNode();
 return this.retData;
 }

 public void add(Object data) {
 if (data == null) {
 return;
 }
 Node newNode = new Node((Comparable) data);
 if (this.root == null) {
 this.root = newNode;
 } else {
 this.root.addNode(newNode);
 }
 this.count++;
 }
}

讲解的话,有难度,不知道怎么用文字表示,这个最好还是看视频,配合图讲解,我也只是了解了下

声明:TIL|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA[ZH]协议进行授权

转载:转载请注明原文链接 - 【数据结构】简单二叉树遍历,递归与非递归用法-Java版


Life is very interesting. In the end, some of your greatest pains become your greatest strengths.