如果你已经知道了如何把一颗二叉树用两个数组来储存，即一个数组储存索引，一个数组储存值。那么今天在这里我们要学的是：如果给你这两个数组，你要去把它还原成一棵二叉树，并且能够实现二叉树的基本方法。
1.算法思想：
1.1我们二叉树的建立，是不是就是初始一棵二叉树？没错，就是再写一个二叉树的构造函数，不同的是初始化直接生成一棵树而非一个结点。
1.2首先他会给你两个数组，那么构造函数就应该以这两个数组为形参：
public BinaryCharTree(char[] paraDataArray, int[] paraIndicesArray)
1.3还原这可二叉树，你可以把给你的这些结点值看做是毫无关系的孤立点，我们先生成一个二叉树数组，它给你多少个结点值，那么二叉树的长度就应该有多大。由于这个二叉树数组中，每个单元的数并没有数值，其左右孩子也没有链接。我们要做的便是给这二叉树数组赋值并且链接起来。
1.4结点值直接按一个for循坏赋值就好了，关键是链接。这里需要两个for循环，采用孩子找妈妈的方法。第一个for是孩子的范围，第二个for是父亲的范围。再利用索引数组判断他们是不是父子，是则相连，不是则跳过。
for (int i = 1; i < tempNumNodes; i++) {
for (int j = 0; j < i; j++) {
System.out.println("indices " + paraIndicesArray[j] + " vs. " + paraIndicesArray[i]);
if (paraIndicesArray[i] == paraIndicesArray[j] * 2 + 1) {
tempAllNodes[j].leftChild = tempAllNodes[i];
System.out.println("linking " + j + " with " + i);
break;
} else if (paraIndicesArray[i] == paraIndicesArray[j] * 2 + 2) {
tempAllNodes[j].rightChild = tempAllNodes[i];
System.out.println("linking " + j + " with " + i);
}
} // Of for j
} // Of for i
1.5最后一步了，我们是从第二个结点开始，也就是孩子结点开始。根节点没有链接，最后把根节点链接上。
value = tempAllNodes[0].value; leftChild = tempAllNodes[0].leftChild; rightChild = tempAllNodes[0].rightChild;
完整的函数：
// 二叉树的建立
public BinaryCharTree(char[] paraDataArray, int[] paraIndicesArray) {
// 第一步用一顺序表储存数据
int tempNumNodes = paraDataArray.length;
BinaryCharTree[] tempAllNodes = new BinaryCharTree[tempNumNodes];
for (int i = 0; i < tempNumNodes; i++) {
tempAllNodes[i] = new BinaryCharTree(paraDataArray[i]);
} // Of for i
// 第二步，链接结点
for (int i = 1; i < tempNumNodes; i++) {
for (int j = 0; j < i; j++) {
System.out.println("indices " + paraIndicesArray[j] + " vs. " + paraIndicesArray[i]);
if (paraIndicesArray[i] == paraIndicesArray[j] * 2 + 1) {
tempAllNodes[j].leftChild = tempAllNodes[i];
System.out.println("linking " + j + " with " + i);
break;
} else if (paraIndicesArray[i] == paraIndicesArray[j] * 2 + 2) {
tempAllNodes[j].rightChild = tempAllNodes[i];
System.out.println("linking " + j + " with " + i);
}
} // Of for j
} // Of for i
// 第三步，第一个结点是根节点
value = tempAllNodes[0].value;
leftChild = tempAllNodes[0].leftChild;
rightChild = tempAllNodes[0].rightChild;
}// Of the second constructor
这里只是思想，你自己要运行需要补充很多地方，了解思想就好了。下面是我集成部分。
package datastructure.tree;
import java.util.Arrays;
import datastructure.queue.*;
public class BinaryCharTree {
char value;
BinaryCharTree leftChild;
BinaryCharTree rightChild;
// 第一个构造函数
public BinaryCharTree(char paraName) {
value = paraName;
leftChild = null;
rightChild = null;
}// Of the constructor
//
public static BinaryCharTree manualConstructTree() {
// 第一步构造一个根节点
BinaryCharTree resultTree = new BinaryCharTree('a');
// 第二步构造所有结点。
BinaryCharTree tempTreeB = new BinaryCharTree('b');
BinaryCharTree tempTreeC = new BinaryCharTree('c');
BinaryCharTree tempTreeD = new BinaryCharTree('d');
BinaryCharTree tempTreeE = new BinaryCharTree('e');
BinaryCharTree tempTreeF = new BinaryCharTree('f');
BinaryCharTree tempTreeG = new BinaryCharTree('g');
// 第三步，连接所有节点
resultTree.leftChild = tempTreeB;
resultTree.rightChild = tempTreeC;
tempTreeB.rightChild = tempTreeD;
tempTreeC.leftChild = tempTreeE;
tempTreeD.leftChild = tempTreeF;
tempTreeD.rightChild = tempTreeG;
return resultTree;
}// Of manualConstructTree
// 先序遍历
public void preOrderVisit() {
System.out.print("" + value + " ");
if (leftChild != null) {
leftChild.preOrderVisit();
} // Of if
if (rightChild != null) {
rightChild.preOrderVisit();
} // Of if
}// Of preOrderVisit
// 中序遍历
public void inOrderVisit() {
if (leftChild != null) {
leftChild.inOrderVisit();
} // Of if
System.out.print("" + value + " ");
if (rightChild != null) {
rightChild.inOrderVisit();
} // Of if
}// Of inOrderVisit
// 后序遍历
public void postOrderVisit() {
if (leftChild != null) {
leftChild.postOrderVisit();
} // Of if
if (rightChild != null) {
rightChild.postOrderVisit();
} // Of if
System.out.print("" + value + " ");
}// Of postOrderVisit
// 得到树的高度
public int getDepth() {
// It is a leaf
if ((leftChild == null) && (rightChild == null)) {
return 1;
} // Of if
// The depth of the left child.
int tempLeftDepth = 0;
if (leftChild != null) {
tempLeftDepth = leftChild.getDepth();
} // Of if
// The depth of the right child.
int tempRightDepth = 0;
if (rightChild != null) {
tempRightDepth = rightChild.getDepth();
} // Of if
// 树的高度选取最高的那边+1
if (tempLeftDepth >= tempRightDepth) {
return tempLeftDepth + 1;
} else {
return tempRightDepth + 1;
} // Of if
}// Of getDepth
// 获得结点数目
public int getNumNodes() {
// If it is a leaf.
if (leftChild == null && rightChild == null) {
return 1;
} // Of if
// 左孩子的数目
int templeftNodes = 0;
if (leftChild != null) {
templeftNodes = leftChild.getNumNodes();
} // Of if
// 友孩子的数目
int tempRightNodes = 0;
if (rightChild != null) {
tempRightNodes = rightChild.getNumNodes();
} // Of if
// 总的节点数 = 左孩子数目 + 右孩子数目
return templeftNodes + tempRightNodes + 1;
}// Of getNumNodes
// 根据宽度优先遍历的结点值（我称之广度数组）
char[] valuesArray;
// 完全二叉树的索引
int[] indicesArray;
public void toDataArrays() {
// 初始化数组
int tempLength = getNumNodes();
valuesArray = new char[tempLength];
indicesArray = new int[tempLength];
int i = 0;
// 遍历和转化同时进行
CircleObjectQueue tempQueue = new CircleObjectQueue();
tempQueue.enqueue(this);
CircleIntQueue tempIntQueue = new CircleIntQueue();
tempIntQueue.enqueue(0);
BinaryCharTree tempTree = (BinaryCharTree) tempQueue.dequeue();
int tempIntdex = tempIntQueue.dequeue();
while (tempTree != null) {
valuesArray[i] = tempTree.value;
indicesArray[i] = tempIntdex;
i++;
if (tempTree.leftChild != null) {
tempQueue.enqueue(tempTree.leftChild);
tempIntQueue.enqueue(tempIntdex * 2 + 1);
} // Of if
if (tempTree.rightChild != null) {
tempQueue.enqueue(tempTree.rightChild);
tempIntQueue.enqueue(tempIntdex * 2 + 2);
} // Of if
tempTree = (BinaryCharTree) tempQueue.dequeue();
tempIntdex = tempIntQueue.dequeue();
} // Of while
}// Of toDataArrays
@SuppressWarnings("removal")
public void toDataArraysObjectQueue() {
// Initialize arrays.
int tempLength = getNumNodes();
valuesArray = new char[tempLength];
indicesArray = new int[tempLength];
int i = 0;
// Traverse and convert at the same time.
CircleObjectQueue tempQueue = new CircleObjectQueue();
tempQueue.enqueue(this);
CircleObjectQueue tempIntQueue = new CircleObjectQueue();
Integer tempIndexInteger = new Integer(0);
tempIntQueue.enqueue(tempIndexInteger);
BinaryCharTree tempTree = (BinaryCharTree) tempQueue.dequeue();
int tempIndex = ((Integer) tempIntQueue.dequeue()).intValue();
System.out.println("tempIndex = " + tempIndex);
while (tempTree != null) {
valuesArray[i] = tempTree.value;
indicesArray[i] = tempIndex;
i++;
if (tempTree.leftChild != null) {
tempQueue.enqueue(tempTree.leftChild);
tempIntQueue.enqueue(new Integer(tempIndex * 2 + 1));
} // Of if
if (tempTree.rightChild != null) {
tempQueue.enqueue(tempTree.rightChild);
tempIntQueue.enqueue(new Integer(tempIndex * 2 + 2));
} // Of if
tempTree = (BinaryCharTree) tempQueue.dequeue();
if (tempTree == null) {
break;
} // Of if
tempIndex = ((Integer) tempIntQueue.dequeue()).intValue();
} // Of while
}// Of toDataArraysObjectQueue
// 二叉树的建立
public BinaryCharTree(char[] paraDataArray, int[] paraIndicesArray) {
// 第一步用一顺序表储存数据
int tempNumNodes = paraDataArray.length;
BinaryCharTree[] tempAllNodes = new BinaryCharTree[tempNumNodes];
for (int i = 0; i < tempNumNodes; i++) {
tempAllNodes[i] = new BinaryCharTree(paraDataArray[i]);
} // Of for i
// 第二步，链接结点
for (int i = 1; i < tempNumNodes; i++) {
for (int j = 0; j < i; j++) {
System.out.println("indices " + paraIndicesArray[j] + " vs. " + paraIndicesArray[i]);
if (paraIndicesArray[i] == paraIndicesArray[j] * 2 + 1) {
tempAllNodes[j].leftChild = tempAllNodes[i];
System.out.println("linking " + j + " with " + i);
break;
} else if (paraIndicesArray[i] == paraIndicesArray[j] * 2 + 2) {
tempAllNodes[j].rightChild = tempAllNodes[i];
System.out.println("linking " + j + " with " + i);
}
} // Of for j
} // Of for i
// 第三步，第一个结点是根节点
value = tempAllNodes[0].value;
leftChild = tempAllNodes[0].leftChild;
rightChild = tempAllNodes[0].rightChild;
}// Of the second constructor
public static void main(String args[]) {
char[] tempCharArray = { 'A', 'B', 'C', 'D', 'E', 'F' };
int[] tempIndicesArray = { 0, 1, 3, 7, 15, 31 };
System.out.println("开始建立二叉树：");
BinaryCharTree tempTree2 = new BinaryCharTree(tempCharArray, tempIndicesArray);
System.out.println("rnPreorder visit:");
tempTree2.preOrderVisit();
System.out.println("rnIn-order visit:");
tempTree2.inOrderVisit();
System.out.println("rnPost-order visit:");
tempTree2.postOrderVisit();
}// Of main
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）