Java二叉树的建立

Java二叉树的建立,第1张

Java二叉树的建立

如果你已经知道了如何把一颗二叉树用两个数组来储存,即一个数组储存索引,一个数组储存值。那么今天在这里我们要学的是:如果给你这两个数组,你要去把它还原成一棵二叉树,并且能够实现二叉树的基本方法。

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
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5695310.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存