建立一棵二叉树：除了创建每个结点外，我们还需要指定结点的父子关系。
我们可以按照二叉树存储的逻辑，用层次序号数组来反映结点的父子关系，设现在有结点i和结点j：
- 如果i*2+1==j，则说明j是i的左孩子；
- 如果i*2+2==j，则说明j是i的右孩子；
在实现代码之前，我手动模拟了一遍链接各个结点的过程，同时思考如何通过代码实现，这能很好的帮我们整理思路：
通过上面的流程我们不难发现，这就是遍历层次序号数组的过程，遍历过程我们要找到各个结点的孩子结点，孩子结点的序号一定大于当前结点，所以需要再嵌入一层循环从当前结点后面去找孩子结点，当发现层次序号大于当前结点层次序号*2+2时，则说明后面没有其孩子结点，可以直接内层循环，继续查找下一个结点的孩子结点。
换一种角度，除了第一个结点外的所有结点一定有且仅有一个父结点，我们可以从第二个结点开始，去找每个结点的父亲。
该节点的父结点层次序号一定会小于当前结点，我们需要再套一层循环，从当前结点的前面去依次找它的父结点，当找到父结点后，直接退出当前循环，查找下一个结点的父结点。
链接各个结点：
- 从父结点角度出发，遍历层次序号数组，找到该节点的左孩子和右孩子：
for (int i = 0; i < tempNumNodes - 1; i++) {
for (int j = i + 1; j < tempNumNodes; j++) {
if (paraIndicesArray[i] * 2 + 1 == paraIndicesArray[j]) {
tempAllNodes[i].leftChild = tempAllNodes[j];
System.out.println("Linking number " + paraIndicesArray[i] + " with number " + paraIndicesArray[j]);
} else if (paraIndicesArray[i] * 2 + 2 == paraIndicesArray[j]) {
tempAllNodes[i].rightChild = tempAllNodes[j];
System.out.println("Linking number " + paraIndicesArray[i] + " with number " + paraIndicesArray[j]);
break;
} else if (paraIndicesArray[i] * 2 + 2 < paraIndicesArray[j]) {
break;
} // Of if
} // Of for j
} // 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);
break;
} // Of if
} // Of for j
} // Of for i
完整代码：
package day12;
import java.util.Arrays;
import day07.CircleIntQueue;
import day11.CircleObjectQueue;
/**
* Binary tree with char type elements.
*
* @author Zhong Xiyan [email protected]
*/
public class BinaryCharTree {
/**
* The value in char.
*/
char value;
/**
* The left child.
*/
BinaryCharTree leftChild;
/**
* The right child.
*/
BinaryCharTree rightChild;
/**
*
*********************
* The first constructor.
*
* @param paraName The value.
*********************
*
*/
public BinaryCharTree(char paraName) {
value = paraName;
leftChild = null;
rightChild = null;
}// Of the constructor
/**
*
*********************
* The second constructor. The parameters must be correct since no validity check is undertaken.
*
* @param paraDataArry The array for data.
* @param paraIndicesArray The array for indices.
*********************
*
*/
public BinaryCharTree(char[] paraDataArry, int[] paraIndicesArray) {
// Step 1. Use a sequential list to store all nodes;
int tempNumNodes = paraDataArry.length;
BinaryCharTree[] tempAllNodes = new BinaryCharTree[tempNumNodes];
for (int i = 0; i < tempNumNodes; i++) {
tempAllNodes[i] = new BinaryCharTree(paraDataArry[i]);
} // Of for i
// Step 2. Link these nodes.
// 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);
// break;
// } // Of if
// } // Of for j
// } // Of for i
for (int i = 0; i < tempNumNodes - 1; i++) {
for (int j = i + 1; j < tempNumNodes; j++) {
if (paraIndicesArray[i] * 2 + 1 == paraIndicesArray[j]) {
System.out.println("Linking number " + paraIndicesArray[i] + " with number " + paraIndicesArray[j]);
tempAllNodes[i].leftChild = tempAllNodes[j];
} else if (paraIndicesArray[i] * 2 + 2 == paraIndicesArray[j]) {
System.out.println("Linking number " + paraIndicesArray[i] + " with number " + paraIndicesArray[j]);
tempAllNodes[i].rightChild = tempAllNodes[j];
break;
} else if (paraIndicesArray[i] * 2 + 2 < paraIndicesArray[j]) {
break;
} // Of if
} // Of for j
} // Of for i;
// Step 3. The root is the first node.
value = tempAllNodes[0].value;
leftChild = tempAllNodes[0].leftChild;
rightChild = tempAllNodes[0].rightChild;
}// Of BinaryCharTree
/**
*
*********************
* @Title: preOrderVisit
* @Description: TODO(Pre-order visit.)
*
*********************
*
*/
public void preOrderVisit() {
System.out.print("" + value + " ");
if (leftChild != null) {
leftChild.preOrderVisit();
} // Of if
if (rightChild != null) {
rightChild.preOrderVisit();
} // Of if
}// Of preOderVisit
/**
*
*********************
* @Title: inOrderVisit
* @Description: TODO(In-order visit.)
*
*********************
*
*/
public void inOrderVisit() {
if (leftChild != null) {
leftChild.inOrderVisit();
} // Of if
System.out.print("" + value + " ");
if (rightChild != null) {
rightChild.inOrderVisit();
} // Of if
}// Of inOrderVisit
/**
*
*********************
* @Title: postOrderVisit
* @Description: TODO(Post-order visit.)
*
*********************
*
*/
public void postOrderVisit() {
if (leftChild != null) {
leftChild.postOrderVisit();
} // Of if
if (rightChild != null) {
rightChild.postOrderVisit();
} // Of if
System.out.print("" + value + " ");
}// Of postOrderVisit
/**
*
*********************
* @Title: getDepth
* @Description: TODO(Get the depth of the binary tree.)
*
* @return The depth of the tree.
*********************
*
*/
public int getDepth() {
// It is a leaf.
if (leftChild == null && rightChild == null) {
return 1;
} // Of if
// Get the depth both of left child and right child. 0 for without the child.
int leftDepth = 0, rightDepth = 0;
if (leftChild != null) {
leftDepth = leftChild.getDepth() + 1;
} // Of if
if (rightChild != null) {
rightDepth = rightChild.getDepth() + 1;
} // Of if
return leftDepth > rightDepth ? leftDepth : rightDepth;
}// Of getDepth
/**
*
*********************
* @Title: getNumNodes
* @Description: TODO(Get the number of nodes)
*
* @return The number of nodes.
*********************
*
*/
public int getNumNodes() {
// It is a leaf.
if (leftChild == null && rightChild == null) {
return 1;
} // Of if
int leftChildNodes = 0, rightChildNodes = 0;
// Get the number of nodes of the left child.
if (leftChild != null) {
leftChildNodes = leftChild.getNumNodes();
} // Of if
// Get the number of nodes of the right child.
if (rightChild != null) {
rightChildNodes = rightChild.getNumNodes();
} // Of if
// The total number of nodes.
return leftChildNodes + rightChildNodes + 1;
}// Of getNumNodes
/**
* The values of nodes according to breadth first traversal.
*/
char[] valuesArray;
/**
* The indices in the complete binary tree.
*/
int[] indicesArray;
/**
*
*********************
* @Title: toDataArrays
* @Description: TODO(Convert the tree to data arrays, including a char array
* and an int array. The results are stored in two member
* variables)
*
* @see #valuesArray
* @see #indicesArray
*
*********************
*
*/
public void toDataArrays() {
// 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);
CircleIntQueue tempIntQueue = new CircleIntQueue();
tempIntQueue.enqueue(0);
BinaryCharTree tempTree = (BinaryCharTree) tempQueue.dequeue();
int tempIndex = tempIntQueue.dequeue();
while (tempTree != null) {
valuesArray[i] = tempTree.value;
indicesArray[i] = tempIndex;
i++;
if (tempTree.leftChild != null) {
tempQueue.enqueue(tempTree.leftChild);
tempIntQueue.enqueue(tempIndex * 2 + 1);
} // Of if
if (tempTree.rightChild != null) {
tempQueue.enqueue(tempTree.rightChild);
tempIntQueue.enqueue(tempIndex * 2 + 2);
} // Of if
tempTree = (BinaryCharTree) tempQueue.dequeue();
tempIndex = tempIntQueue.dequeue();
} // Of while
}// Of toDataArrays
/**
*
*********************
* @Title: toDataArraysObjectQueue
* @Description: TODO(Convert the tree to data arrays, including a char array
* and an int array. The results are stored in two member
* variables)
*
* @see #valuesArray
* @see #indicesArray
*
*********************
*
*/
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 = Integer.valueOf(0);
tempIntQueue.enqueue(tempIndexInteger);
BinaryCharTree tempTree = (BinaryCharTree) tempQueue.dequeue();
int tempIndex = ((Integer) tempIntQueue.dequeue()).intValue();
while (tempTree != null) {
valuesArray[i] = tempTree.value;
indicesArray[i] = tempIndex;
i++;
if (tempTree.leftChild != null) {
tempQueue.enqueue(tempTree.leftChild);
tempIndexInteger = Integer.valueOf(tempIndex * 2 + 1);
tempIntQueue.enqueue(tempIndexInteger);
} // Of if
if (tempTree.rightChild != null) {
tempQueue.enqueue(tempTree.rightChild);
tempIndexInteger = Integer.valueOf(tempIndex * 2 + 2);
tempIntQueue.enqueue(tempIndexInteger);
} // Of if
tempTree = (BinaryCharTree) tempQueue.dequeue();
if (tempTree == null) {
break;
} // Of if
tempIndex = ((Integer) tempIntQueue.dequeue()).intValue();
} // Of while
}// Of toDataArraysObjectQueue
/**
*
*********************
* @Title: manualConstructTree
* @Description: TODO(Manually construct a tree. Only for testing.)
*
* @return A binary tree.
*********************
*/
public static BinaryCharTree manualConstructTree() {
// Step 1. Construct a tree with only one node.
BinaryCharTree resultTree = new BinaryCharTree('a');
// Step 2. Construct all nodes. The first node is the root.
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');
// Step 3. Link all nodes.
resultTree.leftChild = tempTreeB;
resultTree.rightChild = tempTreeC;
tempTreeB.rightChild = tempTreeD;
tempTreeC.leftChild = tempTreeE;
tempTreeD.leftChild = tempTreeF;
tempTreeD.rightChild = tempTreeG;
return resultTree;
}// Of manualConstructTree
/**
*
*********************
* @Title: main
* @Description: TODO(The entrance of the program.)
*
* @param args Not used now.
*********************
*
*/
public static void main(String args[]) {
BinaryCharTree tempTree = manualConstructTree();
System.out.println("\r\nPreorder visit:");
tempTree.preOrderVisit();
System.out.println("\r\nInorder visit:");
tempTree.inOrderVisit();
System.out.println("\r\nPostorder visit:");
tempTree.postOrderVisit();
System.out.println("\r\n\r\nThe depth is: " + tempTree.getDepth());
System.out.println("The number of nodes is: " + tempTree.getNumNodes());
tempTree.toDataArrays();
System.out.println("The values are: " + Arrays.toString(tempTree.valuesArray));
System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));
tempTree.toDataArraysObjectQueue();
System.out.println("Only object queue.");
System.out.println("The values are: " + Arrays.toString(tempTree.valuesArray));
System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));
char[] tempCharArray = { 'A', 'B', 'C', 'D', 'E', 'F' };
int[] tempIndicesArray = { 0, 1, 2, 4, 5, 12 };
BinaryCharTree tempTree2 = new BinaryCharTree(tempCharArray, tempIndicesArray);
System.out.println("\r\nPreorder visit:");
tempTree2.preOrderVisit();
System.out.println("\r\nInorder visit:");
tempTree2.inOrderVisit();
System.out.println("\r\nPostorder visit:");
tempTree2.postOrderVisit();
}// Of main
}// Of class BinaryCharTree
运行结果：
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）