当前位置:   article > 正文

树——二叉树的概念及构造(Java实现)_构造一颗n层的二叉

构造一颗n层的二叉

先普及一下树的概念

  • 树的定义
    • 树是由n(n>=0)个结点点组成的有限集合。若n=0,称为空树;若n>0,则
      • (1)有一个特定的称为根(root)的结点,他只有后继,没有前驱;
      • (2)除根结点以外的其他结点可以划分为m(m>=0)个互不相关的集合T0、T1、...Tm-1,每个集合Ti又是一颗树,称为根的子树,
      • 每颗子树的结点有且只有直接前驱,但可以有一个或多个后继。
  • 树的基本术语
    • (1)结点
      • 指树中的一个数据元素,一般用一个字母表示。
    • (2)度
      • 一个结点包含树的数目,称为该结点的度
    • (3)树叶(叶子)
      • 度为0的结点,称为叶子结点或树叶,也叫终端结点
    • (4)孩子结点
      • 若结点X有子树,则紫薯的根结点为X的孩子结点,也称为孩子。
    • (5)双亲结点
      • 若结点X有子女Y,则X为Y的双亲结点
    • (6)祖先结点
      • 从根结点到该结点所经过分枝上的所有结点为该结点的祖先
    • (7)子孙结点
      • 某一结点的子女及子女的子女都为该结点子孙。
    • (8)兄弟结点
      • 具有同一个双亲的结点,称为兄弟结点
    • (9)树的度——唯一性
      • 树中结点度的最大值称为最大值称为树的度
    • (10)树的层数
      • 根结点的层数为1,其他结点的层数为从根结点到该结点所经过分支数目再加1。
    • (11)树的高度 (深度)
      • 树中结点所处的最大层数称为树的高度
    • (12)有序树与无序树
      • 若一棵树中所有子树从左到右的排序是有顺序的,不能颠倒次序,称该树为有序树,反之为无序树。
    • (13)森林(树林)
      • 若干颗数称为森林,一棵树也是一个特殊的森林。

树可以转换为二叉树,二叉树还原为树。所以我们在解决树的问题时,可以通过实现二叉树来实现目的。

二叉树

二叉树的性质

  • (1)若二叉树的层次从1开始,则二叉树的第i层最多有2^(i-1)个结点。(i>=1)
  • (2)深度为k的二叉树最多有2^k-1个结点。(k>=1)       推导公式:1+2+...+2^(k-1)
  • (3)对于任一棵非空二叉树,若其叶结点数为n0,度为2的非叶结点数为n2,则n0 = n2 +1。
  • (4) 具有n个结点的完全二叉树的深度为int_UP(log(2,n+1))。
  • (5).如果将一棵有n个结点的完全二叉树自顶向下,同一层自左向右连续给结点编号1,2,3,......,n,然后按此结点编号将树中各结点顺序的存放于一个一维数组,并简称编号为i的结点为结点i( i>=1 && i<=n),则有以下关系:
    • (1)若 i= 1,则结点i为根,无父结点;若 i> 1,则结点 i 的父结点为结点int_DOWN(i / 2);
    • (2)若 2*i <= n,则结点 i 的左子女为结点 2*i;
    • (3)若2*i<=n,则结点i的右子女为结点2*i+1;
    • (4)若结点编号i为奇数,且i!=1,它处于右兄弟位置,则它的左兄弟为结点i-1;
    • (5)若结点编号i为偶数,且i!=n,它处于左兄弟位置,则它的右兄弟为结点i+1;
    • (6)结点i所在的层次为 int_DOWN(log(2,i))+1。

存储方式

 (1)顺序存储——数组存储(占用空间大,适合存完全二叉树(只要层数达到,并且除最后一层外全满))

  (2)链式存储——二叉链表

实现方式

感觉用数组实现树的真的特别少,所以这里我们通过二叉链表实现二叉树。

  1. package cn.datastruct.tree;
  2. /**
  3. * 二叉树
  4. * @author hydra
  5. *
  6. */
  7. public class BinaryTree {
  8. private Node root;//根结点
  9. class Node{ //内部类模仿树结构
  10. private int val;
  11. private Node lchild;//左孩子
  12. private Node rchild;//右孩子
  13. public Node(int val) {
  14. this.val = val;
  15. }
  16. }
  17. public void setRoot(int val) {
  18. this.root.val= val;
  19. }
  20. public Node getRoot() {
  21. return root;
  22. }
  23. public BinaryTree(int val) {
  24. Node node = new Node(val);
  25. this.root = node;
  26. }
  27. public BinaryTree() {
  28. this.root = null;
  29. }
  30. /**
  31. * 添加节点
  32. * @param val
  33. */
  34. public boolean add(int val){
  35. //创建新节点对象
  36. Node node = new Node(val);
  37. if(root==null) {//根结点不存在
  38. root = node;
  39. return true;
  40. }else {
  41. Node cur = root;
  42. while(true) {
  43. if(val < cur.val) {
  44. if(cur.lchild == null) {
  45. Node newNode = new Node(val);
  46. cur.lchild = newNode;
  47. return true;
  48. }
  49. cur = cur.lchild;
  50. }else if(val > cur.val){
  51. if(val > cur.val) {
  52. if(cur.rchild == null) {
  53. Node newNode = new Node(val);
  54. cur.rchild = newNode;
  55. return true;
  56. }
  57. cur = cur.rchild;
  58. }
  59. }else {
  60. return false;//不允许重复
  61. }
  62. }
  63. }
  64. }
  65. /**
  66. * 查找树中是否含有某值
  67. * @param val
  68. * @return
  69. */
  70. public Object find(int val) {
  71. Node cur = root;//记录当前结点的对象
  72. while(true) {
  73. if(cur.val == val)
  74. {
  75. return cur.val;
  76. }else if(cur.val > val){
  77. cur = cur.lchild;
  78. if(cur==null) {
  79. return null;
  80. }
  81. }else if(cur.val < val){
  82. cur = cur.rchild;
  83. if(cur==null) {
  84. return null;
  85. }
  86. }
  87. }
  88. }
  89. /**
  90. * 先序遍历
  91. * @param node
  92. */
  93. public static void preOrder(Node node) {
  94. if(node == null) {
  95. return ;
  96. }
  97. System.out.println(node.val);
  98. preOrder(node.lchild);
  99. preOrder(node.rchild);
  100. }
  101. /**
  102. * 中序遍历
  103. * @param node
  104. */
  105. public void inOrder(Node node) {
  106. if(node == null) {
  107. return ;
  108. }
  109. inOrder(node.lchild);
  110. System.out.println(node.val);
  111. inOrder(node.rchild);
  112. }
  113. /**
  114. * 后序遍历
  115. * @param node
  116. */
  117. public void froOrder(Node node) {
  118. if(node == null) {
  119. return ;
  120. }
  121. froOrder(node.lchild);
  122. froOrder(node.rchild);
  123. System.out.println(node.val);
  124. }
  125. public static void main(String[] args) {
  126. BinaryTree tree = new BinaryTree();
  127. int[] a = new int[] {3,1,0,2,7,5,8,9};
  128. for (int i : a) {
  129. tree.add(i);
  130. }
  131. // tree.setRoot(3);
  132. System.out.println("前序遍历");
  133. tree.preOrder(tree.getRoot());
  134. System.out.println("中序遍历");
  135. tree.inOrder(tree.getRoot());
  136. System.out.println("后序遍历");
  137. tree.froOrder(tree.getRoot());
  138. }
  139. }

其中中序输出是有序。

*************************************************************如有错误,欢迎指正**********************************************************

 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/747824
推荐阅读
相关标签
  

闽ICP备14008679号