二叉树和二叉树的遍历_Suger 二叉树的层次遍历

分享人:余生一个浪来源:互联网16

1. 二叉树

一般的树限制比较少，所以才提出了具有特色的二叉树的概念。二叉树顾名思义，每个节点最多有两个子节点，分别叫做左子节点和右子节点。有了这个限定性后，就可以干很多树不能干的事情了。如果树的所有层，除了最后一层的节点外都是两个子节点，那么称这个树为满二叉树。如下图

若设二叉树的高度为h，除第h 层外，其它各层 (1～h-1)的结点数都达到最大个数，第 h层所有的节点都连续集中在最左边，这就是完全二叉树。

2.二叉树的操作

二叉树具有为指定节点增加子节点操作、判断树是否为空、返回根节点、返回指定节点的父节点，返回指定节点的左子节点、返回指定节点的右子节点、返回树的深度、返回指定节点的位置。

3.二叉树的延伸

其实二叉树只是一个引子，计算机界很多的算法都是根据二叉树所展开的，比如排序二叉树、红黑树、哈夫曼树、线索二叉树等等。

4.顺序实现二叉树

下面我们来看看二叉树的顺序实现方式，顺序实现二叉树就是利用数组存储所有的二叉树的节点。代码如下

Java代码
  1. packagedateStructer.tree.binaryTree;
  3. public classArrayBinaryTree<T>{
  4. // 树的默认深度
  5. private static final intDefTreeDeep = 4;
  6. // 节点数组
  7. private Object[]datas;
  8. // 指定的树的深度
  9. private inttreeDeep;
  10. // 实际的数组个数
  11. private intarraySize;
  13. public ArrayBinaryTree(){
  14. // 设置默认的树深度
  15. treeDeep = DefTreeDeep;
  16. //2的DefTreeDeep次方-1个数组元素
  17. arraySize = (int)Math.pow(2, DefTreeDeep) - 1;
  18. datas = newObject[arraySize];
  19. }
  21. publicArrayBinaryTree(intdeep) {
  22. // 按指定深度
  23. treeDeep = deep;
  24. arraySize = (int)Math.pow(2, treeDeep) - 1;
  25. datas = newObject[arraySize];
  26. }
  28. publicArrayBinaryTree(intdeep, T data) {
  29. // 按指定深度
  30. treeDeep = deep;
  31. arraySize = (int)Math.pow(2, treeDeep) - 1;
  32. datas = newObject[arraySize];
  33. datas[0] = data;
  34. }
  36. public booleanaddNode(int index, T data,boolean isLeft){
  37. if (index *2+ 2 > arraySize ||datas[index] == null) {
  38. throw newRuntimeException("标记无效");
  39. }
  40. if (isLeft) {
  41. datas[index * 2 + 1] =data;
  42. } else {
  43. datas[index * 2 + 2] =data;
  44. }
  45. return true;
  46. }
  48. public boolean isEmpty(){
  49. return arraySize ==0;
  50. }
  52. @SuppressWarnings("unchecked")
  53. public T getRoot(){
  54. return (T)datas[0];
  55. }
  57. @SuppressWarnings("unchecked")
  58. public TgetParent(int index) {
  59. if (index >arraySize || datas[index] == null) {
  60. throw newRuntimeException("标记无效");
  61. }
  62. if (datas[(index -1)/ 2] == null) {
  63. throw newRuntimeException("无父节点");
  64. }
  65. return (T) datas[(index- 1) / 2];
  66. }
  68. @SuppressWarnings("unchecked")
  69. public TgetLeftNode(int index) {
  70. if (index *2+ 2 > arraySize ||datas[index] == null) {
  71. throw newRuntimeException("标记无效");
  72. }
  73. return (T) datas[index* 2+ 1];
  74. }
  76. @SuppressWarnings("unchecked")
  77. public TgetRightNode(int index) {
  78. if (index *2+ 2 > arraySize ||datas[index] == null) {
  79. throw newRuntimeException("标记无效");
  80. }
  81. return (T) datas[index* 2+ 2];
  82. }
  84. public intgetTreeDeep() {
  85. return treeDeep;
  86. }
  88. public intgetNodeIndex(T data) {
  89. for (inti = 0; i < arraySize; i++){
  90. if (data == datas[i]){
  91. return i;
  92. }
  93. }
  94. return -1;
  95. }
  96. @Override
  97. public String toString(){
  98. StringBuffer str = newStringBuffer("[");
  99. for (inti = 0; i < datas.length;i++) {
  100. str.append("[" + datas[i] + "],");
  101. }
  102. if (datas.length> 0) {
  103. returnstr.substring(0,str.lastIndexOf(",")) + "]";
  104. }
  105. returnstr.append("]").toString();
  106. }
  107. }
package dateStructer.tree.binaryTree;public class ArrayBinaryTree<T> {        // 树的默认深度        private static final int DefTreeDeep = 4;        // 节点数组        private Object[] datas;        // 指定的树的深度        private int treeDeep;        // 实际的数组个数        private int arraySize;                public ArrayBinaryTree() {                // 设置默认的树深度                treeDeep = DefTreeDeep;                // 2的DefTreeDeep次方-1个数组元素                arraySize = (int) Math.pow(2, DefTreeDeep) - 1;                datas = new Object[arraySize];        }                public ArrayBinaryTree(int deep) {                // 按指定深度                treeDeep = deep;                arraySize = (int) Math.pow(2, treeDeep) - 1;                datas = new Object[arraySize];        }                public ArrayBinaryTree(int deep, T data) {                // 按指定深度                treeDeep = deep;                arraySize = (int) Math.pow(2, treeDeep) - 1;                datas = new Object[arraySize];                datas[0] = data;        }                public boolean addNode(int index, T data, boolean isLeft) {                if (index * 2 + 2 > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                if (isLeft) {                        datas[index * 2 + 1] = data;                } else {                        datas[index * 2 + 2] = data;                }                return true;        }                public boolean isEmpty() {                return arraySize == 0;        }                @SuppressWarnings("unchecked")        public T getRoot() {                return (T) datas[0];        }                @SuppressWarnings("unchecked")        public T getParent(int index) {                if (index > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                if (datas[(index - 1) / 2] == null) {                        throw new RuntimeException("无父节点");                }                return (T) datas[(index - 1) /  2];        }                @SuppressWarnings("unchecked")        public T getLeftNode(int index) {                if (index * 2 + 2 > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                return (T) datas[index * 2 + 1];        }                @SuppressWarnings("unchecked")        public T getRightNode(int index) {                if (index * 2 + 2 > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                return (T) datas[index * 2 + 2];        }                public int getTreeDeep() {                return treeDeep;        }                public int getNodeIndex(T data) {                for (int i = 0; i < arraySize; i++) {                        if (data == datas[i]) {                                return i;                        }                }                return -1;        }        @Override        public String toString() {                StringBuffer str = new StringBuffer("[");                for (int i = 0; i < datas.length; i++) {                        str.append("[" + datas[i] + "],");                }                if (datas.length > 0) {                        return str.substring(0, str.lastIndexOf(",")) + "]";                }                return str.append("]").toString();        }}

测试代码如下

Java代码
  1. public static voidmain(String[] args) {
  2. ArrayBinaryTree<String>arrayBinaryTree = newArrayBinaryTree<String>(4,"汉献帝");
  3. System.out.println(arrayBinaryTree);
  4. arrayBinaryTree.addNode(0,"刘备", true);
  5. arrayBinaryTree.addNode(0,"曹操", false);
  6. arrayBinaryTree.addNode(1,"关羽", true);
  7. arrayBinaryTree.addNode(1,"张飞", false);
  8. arrayBinaryTree.addNode(2,"张辽", true);
  9. arrayBinaryTree.addNode(2,"许褚", false);
  10. System.out.println(arrayBinaryTree);
  11. System.out.println(arrayBinaryTree.getLeftNode(1));
  12. System.out.println(arrayBinaryTree.getRightNode(0));
  13. System.out.println(arrayBinaryTree.isEmpty());
  14. System.out.println(arrayBinaryTree.getParent(4));
  15. }
public static void main(String[] args) {                ArrayBinaryTree<String> arrayBinaryTree = new ArrayBinaryTree<String>(4,"汉献帝");                System.out.println(arrayBinaryTree);                arrayBinaryTree.addNode(0, "刘备", true);                arrayBinaryTree.addNode(0, "曹操", false);                arrayBinaryTree.addNode(1, "关羽", true);                arrayBinaryTree.addNode(1, "张飞", false);                arrayBinaryTree.addNode(2, "张辽", true);                arrayBinaryTree.addNode(2, "许褚", false);                System.out.println(arrayBinaryTree);                System.out.println(arrayBinaryTree.getLeftNode(1));                System.out.println(arrayBinaryTree.getRightNode(0));                System.out.println(arrayBinaryTree.isEmpty());                System.out.println(arrayBinaryTree.getParent(4));        }

测试效果如下

顺序实现是比较浪费资源的，可以看到数组没有元素的位置都是null。如果将测试代码稍微变更一下，如下因为树本身就是具有递归性质的结构。

Java代码
  1. public static voidmain(String[] args) {
  2. ArrayBinaryTree<String>arrayBinaryTree = newArrayBinaryTree<String>(4,"汉献帝");
  3. System.out.println(arrayBinaryTree);
  4. arrayBinaryTree.addNode(0,"刘备", true);
  5. arrayBinaryTree.addNode(0,"曹操", false);
  6. arrayBinaryTree.addNode(2,"张辽", true);
  7. arrayBinaryTree.addNode(2,"许褚", false);
  8. arrayBinaryTree.addNode(6,"李典", true);
  9. arrayBinaryTree.addNode(6,"乐进", false);
  10. System.out.println(arrayBinaryTree);
  11. System.out.println(arrayBinaryTree.getLeftNode(2));
  12. System.out.println(arrayBinaryTree.getRightNode(0));
  13. System.out.println(arrayBinaryTree.isEmpty());
  14. System.out.println(arrayBinaryTree.getParent(14));
  15. }
public static void main(String[] args) {                ArrayBinaryTree<String> arrayBinaryTree = new ArrayBinaryTree<String>(4,"汉献帝");                System.out.println(arrayBinaryTree);                arrayBinaryTree.addNode(0, "刘备", true);                arrayBinaryTree.addNode(0, "曹操", false);                arrayBinaryTree.addNode(2, "张辽", true);                arrayBinaryTree.addNode(2, "许褚", false);                arrayBinaryTree.addNode(6, "李典", true);                arrayBinaryTree.addNode(6, "乐进", false);                System.out.println(arrayBinaryTree);                System.out.println(arrayBinaryTree.getLeftNode(2));                System.out.println(arrayBinaryTree.getRightNode(0));                System.out.println(arrayBinaryTree.isEmpty());                System.out.println(arrayBinaryTree.getParent(14));        }

运行效果如下

可以看到数组中间资源浪费得很严重。

5.二叉链表实现二叉树

为了弥补顺序实现的空间浪费问题，可以使用链表方式实现二叉树，但是链表又分为两种情况，一种是二叉链表，另一种稍后再说。二叉链表的思想就是构造一个对象，记住它的两个子节点，所谓记住两个子节点可以是子节点的位置，可以是子节点的实体对象。如果记录了位置，其实是离不开数组的帮助的。如果记录了整个子节点对象，那么就可以完全脱离数组，完完全全，真真正正的链表离散式存储。这次使用记录节点位置，算法如下

Java代码
  1. packagedateStructer.tree.binaryTree;
  3. public classTwoLinkedBinaryTree<T>{
  4. // 树的默认深度
  5. private static final intDefTreeDeep = 4;
  6. // 节点数组
  7. privateTwoLinkNode<T>[]datas;
  8. // 指定的树的深度
  9. private inttreeDeep;
  10. // 实际的数组个数
  11. private intarraySize;
  12. //节点个数
  13. private intnodeSize;
  15. @SuppressWarnings("hiding")
  16. classTwoLinkNode<T> {
  17. public intleftChildIndex;
  18. public intrightChildIndex;
  19. public intindex;
  20. public T data;
  21. }
  22. @SuppressWarnings("unchecked")
  23. public TwoLinkedBinaryTree(){
  24. treeDeep = DefTreeDeep;
  25. arraySize = (int)Math.pow(2, treeDeep) - 1;
  26. datas = newTwoLinkNode[arraySize];
  27. }
  28. @SuppressWarnings("unchecked")
  29. publicTwoLinkedBinaryTree(intdeep, T data) {
  30. treeDeep = DefTreeDeep;
  31. arraySize = (int)Math.pow(2, treeDeep) - 1;
  32. datas = newTwoLinkNode[arraySize];
  33. TwoLinkNode<T> twoLinkNode= newTwoLinkNode<T>();
  34. twoLinkNode.data = data;
  35. twoLinkNode.leftChildIndex = 1;
  36. twoLinkNode.rightChildIndex = 2;
  37. twoLinkNode.index = 0;
  38. datas[0] = twoLinkNode;
  39. nodeSize = 1;
  40. }
  42. public booleanaddNode(int index, T data,boolean isLeft){
  43. if (index +1> arraySize || datas[index] ==null) {
  44. throw newRuntimeException("标记无效");
  45. }
  46. for (inti = index + 1; i < arraySize; i++){
  47. if (datas[i] ==null) {
  48. TwoLinkNode<T> twoLinkNode= newTwoLinkNode<T>();
  49. twoLinkNode.data = data;
  50. twoLinkNode.index = i;
  51. datas[i] = twoLinkNode;
  52. if (isLeft) {
  53. datas[index].leftChildIndex = i;
  54. } else {
  55. datas[index].rightChildIndex = i;
  56. }
  57. nodeSize ++;
  58. return true;
  59. }
  60. }
  61. return false;
  62. }
  64. public boolean isEmpty(){
  65. return nodeSize ==0;
  66. }
  68. @SuppressWarnings("unchecked")
  69. public T getRoot(){
  70. return (T)datas[0];
  71. }
  73. public TgetParent(int index) {
  74. if (index >arraySize || datas[index] == null) {
  75. throw newRuntimeException("标记无效");
  76. }
  77. for (inti = 0; i < arraySize; i++){
  78. if (datas[i] !=null) {
  79. if (datas[i].leftChildIndex== index
  80. || datas[i].rightChildIndex == index) {
  81. returndatas[i].data;
  82. }
  83. }
  84. }
  85. return null;
  86. }
  88. public TgetLeftNode(int index) {
  89. if (index +2> arraySize || datas[index] ==null) {
  90. throw newRuntimeException("标记无效");
  91. }
  92. return (T)datas[datas[index].leftChildIndex].data;
  93. }
  95. public TgetRightNode(int index) {
  96. if (index +2> arraySize || datas[index] ==null) {
  97. throw newRuntimeException("标记无效");
  98. }
  99. return (T)datas[datas[index].rightChildIndex].data;
  100. }
  102. public intgetTreeDeep() {
  103. return treeDeep;
  104. }
  106. public intgetNodeIndex(T data) {
  107. for (inti = 0; i < arraySize; i++){
  108. if (data == datas[i]){
  109. return i;
  110. }
  111. }
  112. return -1;
  113. }
  114. @Override
  115. public String toString(){
  116. StringBuffer str = newStringBuffer("[");
  117. for (inti = 0; i < nodeSize; i++){
  118. if(datas[i].data !=null){
  119. str.append("[" + datas[i].data +"],");
  120. }
  121. }
  122. if (datas.length> 0) {
  123. returnstr.substring(0,str.lastIndexOf(",")) + "]";
  124. }
  125. returnstr.append("]").toString();
  126. }
  127. }
package dateStructer.tree.binaryTree;public class TwoLinkedBinaryTree<T> {        // 树的默认深度        private static final int DefTreeDeep = 4;        // 节点数组        private TwoLinkNode<T>[] datas;        // 指定的树的深度        private int treeDeep;        // 实际的数组个数        private int arraySize;                //节点个数        private int nodeSize;                @SuppressWarnings("hiding")        class TwoLinkNode<T> {                public int leftChildIndex;                public int rightChildIndex;                public int index;                public T data;        }        @SuppressWarnings("unchecked")        public TwoLinkedBinaryTree() {                treeDeep = DefTreeDeep;                arraySize = (int) Math.pow(2, treeDeep) - 1;                datas = new TwoLinkNode[arraySize];        }        @SuppressWarnings("unchecked")        public TwoLinkedBinaryTree(int deep, T data) {                treeDeep = DefTreeDeep;                arraySize = (int) Math.pow(2, treeDeep) - 1;                datas = new TwoLinkNode[arraySize];                TwoLinkNode<T> twoLinkNode = new TwoLinkNode<T>();                twoLinkNode.data = data;                twoLinkNode.leftChildIndex = 1;                twoLinkNode.rightChildIndex = 2;                twoLinkNode.index = 0;                datas[0] = twoLinkNode;                nodeSize = 1;        }                public boolean addNode(int index, T data, boolean isLeft) {                if (index + 1 > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                for (int i = index + 1; i < arraySize; i++) {                        if (datas[i] == null) {                                TwoLinkNode<T> twoLinkNode = new TwoLinkNode<T>();                                twoLinkNode.data = data;                                twoLinkNode.index = i;                                datas[i] = twoLinkNode;                                if (isLeft) {                                        datas[index].leftChildIndex = i;                                } else {                                        datas[index].rightChildIndex = i;                                }                                nodeSize ++;                                return true;                        }                }                return false;        }                public boolean isEmpty() {                return nodeSize == 0;        }                @SuppressWarnings("unchecked")        public T getRoot() {                return (T) datas[0];        }                public T getParent(int index) {                if (index > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                for (int i = 0; i < arraySize; i++) {                        if (datas[i] != null) {                                if (datas[i].leftChildIndex == index                                                || datas[i].rightChildIndex == index) {                                        return datas[i].data;                                }                        }                }                return null;        }                public T getLeftNode(int index) {                if (index + 2 > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                return (T) datas[datas[index].leftChildIndex].data;        }                public T getRightNode(int index) {                if (index + 2 > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                return (T) datas[datas[index].rightChildIndex].data;        }                public int getTreeDeep() {                return treeDeep;        }                public int getNodeIndex(T data) {                for (int i = 0; i < arraySize; i++) {                        if (data == datas[i]) {                                return i;                        }                }                return -1;        }        @Override        public String toString() {                StringBuffer str = new StringBuffer("[");                for (int i = 0; i < nodeSize; i++) {                        if(datas[i].data != null){                                str.append("[" + datas[i].data + "],");                        }                }                if (datas.length > 0) {                        return str.substring(0, str.lastIndexOf(",")) + "]";                }                return str.append("]").toString();        }        }

使用这种实现其实是想利用好数组的空间。别让中间任何的节点空间白白浪费了。但是可以发现找父节点的时候比较麻烦。还得遍历一下整个节点。三叉链表就不必遍历，因为三叉链表比二叉链表多了记录了一个节点，那就是此节点的父节点。无论是父节点的位置或者父节点实体，都是一样的思想。

6.三叉链表实现二叉树

下面我们基于上面的二叉链表形式编写三叉链表。代码如下

Java代码
  1. packagedateStructer.tree.binaryTree;
  3. public classThreeLinkedBinaryTree<T>{
  4. // 树的默认深度
  5. private static final intDefTreeDeep = 4;
  6. // 节点数组
  7. privateThreeLinkNode<T>[]datas;
  8. // 指定的树的深度
  9. private inttreeDeep;
  10. // 实际的数组个数
  11. private intarraySize;
  12. // 节点个数
  13. private intnodeSize;
  15. @SuppressWarnings("hiding")
  16. classThreeLinkNode<T> {
  17. public intparentIndex;
  18. public intleftChildIndex;
  19. public intrightChildIndex;
  20. public intindex;
  21. public T data;
  22. }
  23. @SuppressWarnings("unchecked")
  24. publicThreeLinkedBinaryTree() {
  25. treeDeep = DefTreeDeep;
  26. arraySize = (int)Math.pow(2, treeDeep) - 1;
  27. datas = newThreeLinkNode[arraySize];
  28. }
  29. @SuppressWarnings("unchecked")
  30. publicThreeLinkedBinaryTree(intdeep, T data) {
  31. treeDeep = DefTreeDeep;
  32. arraySize = (int)Math.pow(2, treeDeep) - 1;
  33. datas = newThreeLinkNode[arraySize];
  34. ThreeLinkNode<T>threeLinkNode = newThreeLinkNode<T>();
  35. threeLinkNode.data = data;
  36. threeLinkNode.leftChildIndex = 1;
  37. threeLinkNode.rightChildIndex = 2;
  38. threeLinkNode.index = 0;
  39. threeLinkNode.parentIndex = -1;
  40. datas[0] = threeLinkNode;
  41. nodeSize = 1;
  42. }
  44. public booleanaddNode(int index, T data,boolean isLeft){
  45. if (index +1> arraySize || datas[index] ==null) {
  46. throw newRuntimeException("标记无效");
  47. }
  48. for (inti = index + 1; i < arraySize; i++){
  49. if (datas[i] ==null) {
  50. ThreeLinkNode<T>threeLinkNode = newThreeLinkNode<T>();
  51. threeLinkNode.data = data;
  52. threeLinkNode.index = i;
  53. threeLinkNode.parentIndex = index;
  54. datas[i] = threeLinkNode;
  55. if (isLeft) {
  56. datas[index].leftChildIndex = i;
  57. } else {
  58. datas[index].rightChildIndex = i;
  59. }
  60. nodeSize++;
  61. return true;
  62. }
  63. }
  64. return false;
  65. }
  67. public boolean isEmpty(){
  68. return nodeSize ==0;
  69. }
  71. @SuppressWarnings("unchecked")
  72. public T getRoot(){
  73. return (T)datas[0];
  74. }
  76. @SuppressWarnings("unchecked")
  77. public TgetParent(int index) {
  78. if (index >arraySize || datas[index] == null) {
  79. throw newRuntimeException("标记无效");
  80. }
  81. return (T)datas[datas[index].parentIndex];
  82. }
  84. public TgetLeftNode(int index) {
  85. if (index +2> arraySize || datas[index] ==null
  86. || datas[datas[index].leftChildIndex] ==null) {
  87. throw newRuntimeException("标记无效");
  88. }
  89. return (T)datas[datas[index].leftChildIndex].data;
  90. }
  92. public TgetRightNode(int index) {
  93. if (index +2> arraySize || datas[index] ==null
  94. || datas[datas[index].rightChildIndex] ==null) {
  95. throw newRuntimeException("标记无效");
  96. }
  97. return (T)datas[datas[index].rightChildIndex].data;
  98. }
  100. public intgetTreeDeep() {
  101. return treeDeep;
  102. }
  104. public intgetNodeIndex(T data) {
  105. for (inti = 0; i < arraySize; i++){
  106. if (data == datas[i]){
  107. return i;
  108. }
  109. }
  110. return -1;
  111. }
  112. @Override
  113. public String toString(){
  114. StringBuffer str = newStringBuffer("[");
  115. for (inti = 0; i < nodeSize; i++){
  116. if (datas[i].data !=null) {
  117. str.append("[" + datas[i].data +"],");
  118. }
  119. }
  120. if (datas.length> 0) {
  121. returnstr.substring(0,str.lastIndexOf(",")) + "]";
  122. }
  123. returnstr.append("]").toString();
  124. }
  125. }
package dateStructer.tree.binaryTree;public class ThreeLinkedBinaryTree<T> {        // 树的默认深度        private static final int DefTreeDeep = 4;        // 节点数组        private ThreeLinkNode<T>[] datas;        // 指定的树的深度        private int treeDeep;        // 实际的数组个数        private int arraySize;        // 节点个数        private int nodeSize;                @SuppressWarnings("hiding")        class ThreeLinkNode<T> {                public int parentIndex;                public int leftChildIndex;                public int rightChildIndex;                public int index;                public T data;        }        @SuppressWarnings("unchecked")        public ThreeLinkedBinaryTree() {                treeDeep = DefTreeDeep;                arraySize = (int) Math.pow(2, treeDeep) - 1;                datas = new ThreeLinkNode[arraySize];        }        @SuppressWarnings("unchecked")        public ThreeLinkedBinaryTree(int deep, T data) {                treeDeep = DefTreeDeep;                arraySize = (int) Math.pow(2, treeDeep) - 1;                datas = new ThreeLinkNode[arraySize];                ThreeLinkNode<T> threeLinkNode = new ThreeLinkNode<T>();                threeLinkNode.data = data;                threeLinkNode.leftChildIndex = 1;                threeLinkNode.rightChildIndex = 2;                threeLinkNode.index = 0;                threeLinkNode.parentIndex = -1;                datas[0] = threeLinkNode;                nodeSize = 1;        }                public boolean addNode(int index, T data, boolean isLeft) {                if (index + 1 > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                for (int i = index + 1; i < arraySize; i++) {                        if (datas[i] == null) {                                ThreeLinkNode<T> threeLinkNode = new ThreeLinkNode<T>();                                threeLinkNode.data = data;                                threeLinkNode.index = i;                                threeLinkNode.parentIndex = index;                                datas[i] = threeLinkNode;                                if (isLeft) {                                        datas[index].leftChildIndex = i;                                } else {                                        datas[index].rightChildIndex = i;                                }                                nodeSize++;                                return true;                        }                }                return false;        }                public boolean isEmpty() {                return nodeSize == 0;        }                @SuppressWarnings("unchecked")        public T getRoot() {                return (T) datas[0];        }                @SuppressWarnings("unchecked")        public T getParent(int index) {                if (index > arraySize || datas[index] == null) {                        throw new RuntimeException("标记无效");                }                return (T) datas[datas[index].parentIndex];        }                public T getLeftNode(int index) {                if (index + 2 > arraySize || datas[index] == null                                || datas[datas[index].leftChildIndex] == null) {                        throw new RuntimeException("标记无效");                }                return (T) datas[datas[index].leftChildIndex].data;        }                public T getRightNode(int index) {                if (index + 2 > arraySize || datas[index] == null                                || datas[datas[index].rightChildIndex] == null) {                        throw new RuntimeException("标记无效");                }                return (T) datas[datas[index].rightChildIndex].data;        }                public int getTreeDeep() {                return treeDeep;        }                public int getNodeIndex(T data) {                for (int i = 0; i < arraySize; i++) {                        if (data == datas[i]) {                                return i;                        }                }                return -1;        }        @Override        public String toString() {                StringBuffer str = new StringBuffer("[");                for (int i = 0; i < nodeSize; i++) {                        if (datas[i].data != null) {                                str.append("[" + datas[i].data + "],");                        }                }                if (datas.length > 0) {                        return str.substring(0, str.lastIndexOf(",")) + "]";                }                return str.append("]").toString();        }}

可以看到基本上方法实现都一样，就是找寻父节点的时候更省事了。因为节点对象多存了父节点的信息，当然就省事了。

7.二叉树的遍历

遍历二叉树实际上就是将一个非线性的二维结构给排列呈线性的过程。如果是顺序实现了二叉树的结构，自然底层就是线性的，无需转化。如果是纯链表实现呢，就需要将离散的节点重新组织组织了。

遍历也分为深度优先遍历、广度优先遍历。而对于深度优先遍历又分为三种模式：先根遍历、中根遍历、后根遍历。

深度优先遍历：就是优先访问树中最深层次的节点

广度优先遍历：就是从根往下一层一层遍历访问

先根遍历：先遍历根节点，之后处理其他子节点

中根遍历：先遍历根节点的左子树，之后遍历根节点，最后遍历右子树

后根遍历：先遍历根节点的左子树，之后遍历右子树，最后遍历根节点

先根遍历算法如下

Java代码
  1. publicList<TwoLinkNode<T>>firstRoot(TwoLinkNode<T> twoLinkNode){
  2. if (twoLinkNode ==null) {
  3. return null;
  4. }
  5. List<TwoLinkNode<T>>list = newArrayList<TwoLinkNode<T>>();
  6. list.add(twoLinkNode);
  7. if(twoLinkNode.leftChildIndex >0){
  8. list.addAll(firstRoot(datas[twoLinkNode.leftChildIndex]));
  9. }
  10. if(twoLinkNode.rightChildIndex >0){
  11. list.addAll(firstRoot(datas[twoLinkNode.rightChildIndex]));
  12. }
  13. return list;
  14. }
public List<TwoLinkNode<T>> firstRoot(TwoLinkNode<T> twoLinkNode) {        if (twoLinkNode == null) {                return null;        }        List<TwoLinkNode<T>> list = new ArrayList<TwoLinkNode<T>>();        list.add(twoLinkNode);        if (twoLinkNode.leftChildIndex > 0) {                list.addAll(firstRoot(datas[twoLinkNode.leftChildIndex]));        }        if (twoLinkNode.rightChildIndex > 0) {                list.addAll(firstRoot(datas[twoLinkNode.rightChildIndex]));        }        return list;}

中根遍历算法如下

Java代码
  2. publicList<TwoLinkNode<T>>minRoot(TwoLinkNode<T> twoLinkNode){
  3. if (twoLinkNode ==null) {
  4. return null;
  5. }
  6. List<TwoLinkNode<T>>list = newArrayList<TwoLinkNode<T>>();
  7. if(twoLinkNode.leftChildIndex >0){
  8. list.addAll(minRoot(datas[twoLinkNode.leftChildIndex]));
  9. }
  10. list.add(twoLinkNode);
  11. if(twoLinkNode.rightChildIndex >0){
  12. list.addAll(minRoot(datas[twoLinkNode.rightChildIndex]));
  13. }
  14. return list;
  15. }
public List<TwoLinkNode<T>> minRoot(TwoLinkNode<T> twoLinkNode) {        if (twoLinkNode == null) {                return null;        }        List<TwoLinkNode<T>> list = new ArrayList<TwoLinkNode<T>>();        if (twoLinkNode.leftChildIndex > 0) {                list.addAll(minRoot(datas[twoLinkNode.leftChildIndex]));        }        list.add(twoLinkNode);        if (twoLinkNode.rightChildIndex > 0) {                list.addAll(minRoot(datas[twoLinkNode.rightChildIndex]));        }        return list;}

后根遍历

Java代码
  2. publicList<TwoLinkNode<T>>afterRoot(TwoLinkNode<T> twoLinkNode){
  3. if (twoLinkNode ==null) {
  4. return null;
  5. }
  6. List<TwoLinkNode<T>>list = newArrayList<TwoLinkNode<T>>();
  7. if(twoLinkNode.leftChildIndex >0){
  8. list.addAll(afterRoot(datas[twoLinkNode.leftChildIndex]));
  9. }
  10. if(twoLinkNode.rightChildIndex >0){
  11. list.addAll(afterRoot(datas[twoLinkNode.rightChildIndex]));
  12. }
  13. list.add(twoLinkNode);
  14. return list;
  15. }
public List<TwoLinkNode<T>> afterRoot(TwoLinkNode<T> twoLinkNode) {        if (twoLinkNode == null) {                return null;        }        List<TwoLinkNode<T>> list = new ArrayList<TwoLinkNode<T>>();        if (twoLinkNode.leftChildIndex > 0) {                list.addAll(afterRoot(datas[twoLinkNode.leftChildIndex]));        }        if (twoLinkNode.rightChildIndex > 0) {                list.addAll(afterRoot(datas[twoLinkNode.rightChildIndex]));        }                list.add(twoLinkNode);        return list;}

广度优先遍历

Java代码
  2. publicList<TwoLinkNode<T>>deepFirst() {
  3. List<TwoLinkNode<T>>list = newArrayList<TwoLinkNode<T>>();
  4. Queue<TwoLinkNode<T>>queue = newArrayDeque<TwoLinkNode<T>>();
  5. queue.add(datas[0]);
  6. while (!queue.isEmpty()){
  7. list.add(queue.peek());
  8. TwoLinkNode<T> twoLinkNode= queue.poll();
  9. if(twoLinkNode.leftChildIndex >0){
  10. queue.add(datas[twoLinkNode.leftChildIndex]);
  11. }
  12. if(twoLinkNode.rightChildIndex >0){
  13. queue.add(datas[twoLinkNode.rightChildIndex]);
  14. }
  15. }
  16. return list;
  17. }
public List<TwoLinkNode<T>> deepFirst() {        List<TwoLinkNode<T>> list = new ArrayList<TwoLinkNode<T>>();        Queue<TwoLinkNode<T>> queue = new ArrayDeque<TwoLinkNode<T>>();        queue.add(datas[0]);        while (!queue.isEmpty()) {                list.add(queue.peek());                TwoLinkNode<T> twoLinkNode = queue.poll();                if (twoLinkNode.leftChildIndex > 0) {                        queue.add(datas[twoLinkNode.leftChildIndex]);                }                if (twoLinkNode.rightChildIndex > 0) {                        queue.add(datas[twoLinkNode.rightChildIndex]);                }        }        return list;}

8.二叉树、树、森林转换

其实这三个结构可以互相转换，具体参考

http://jpkc.nwu.edu.cn/sjjg/study_online/book/6/4_2.htm

9. 总结

这次总结学习了二叉树的概念、用法、实现细节、二叉树的遍历法。当然了这篇总结还不是很全面。回头再补上吧。

from:琉璃仙境

  
二叉树的建立和遍历 二叉树的创建和遍历 

爱华网本文地址 » http://www.aihuau.com/a/25101015/265110.html

更多阅读

老妻少夫:李玉成和马玉琴的幸福生活之二辽视访谈

辽宁电视台对李玉成和马玉琴的访谈,录制地点就在他们家的小屋里...3日中午,李玉成打来电话,说辽宁电视台某专栏摄制组记者来采访他和他的妻子马玉琴.邀请我过去,顺便看一看他俩的新家.晚上6点后,我处理完私事后,按照李玉成说的那

关于硕士研究生学制、学习年限和学位论文答辩的暂行

关于硕士研究生学制、学习年限和学位论文答辩的暂行规定（2008年4月2日合肥工业大学校长办公会修订通过）为保证研究生培养质量，提高研究生学术水平和能力，根据我校学科特点和研究生培养的实际情况，现就硕士研究生学制、学习年限和学位论

腌制韭菜花和韭菜花酱的做法 韭菜花怎么腌制

腌制韭菜花和韭菜花酱的做法 韭菜花是秋天里韭白上生出的白色花簇，多在欲开未开时采摘，韭菜花是中国南北城乡普遍食用的一种佐料。腌制韭菜花或磨碎后腌制成酱食用，一般人群均可食用。适宜夜盲症、皮肤粗糙、便秘、干眼病患者多食。 怎

电影《喊山》和《雨中的树》2013.5.9. 喊山电影为什么被禁

电影《喊山》和《雨中的树》（2013.5.9.）**近段时间，无意发现几部好电影，都是在央视电影频道看到的。现在的世界很精彩，书实在太多了，看不完！电影也实在太多了，看不完！偶尔看到几部名不见经传的电影，竟感觉超过那些“大喊大叫”、“呼风唤雨”

声明:《二叉树和二叉树的遍历_Suger 二叉树的层次遍历》为网友余生一个浪分享！如侵犯到您的合法权益请联系我们删除