[Java知识库]JAVA第23天——二叉树（三）——拔高

二叉树

难点一：二叉树的存储

1. C语言版

void CreateBiTree(BiTree &T) {
	// C语言创建结点
	T = (BiTree)malloc(sizeof(BiTNode));
	// 向节点输值，例如：没有左节点就输入-1
	int data;
	scanf("%d",&data);
	if(data == -1) T = NULL;
	if(T) {
		T->data = data;
		printf("输入%d节点的左子节点：\n",data);
		CreatBiTree(T->lchild);
		printf("输入%d节点的右子节点：\n",data);
		CreatBiTree(T->rchild);		 
	} // end if
} // end CreatBiTree

2. Java语言版

	/**
	 * 二叉树的存储
	 * @return T 二叉树
	 */
	public BiTree CreateBiTree() {
		
		// 创建根节点
		BiTree T = new BiTree(1);
		
		// 创建树枝，值域
		BiTree T_l = new BiTree(2);
		BiTree T_r = new BiTree(3);
		BiTree T_l_l = new BiTree(4);
		BiTree T_r_r = new BiTree(5);
		
		// 指针域
		T.lchild = T_l;
		T.rchild = T_r;
		T_l.lchild = T_l_l;
		T_r.lchild = T_r_r;
		
		return T;
	} // end CreateBiTree

• 显而易见，这种方法不好。
• 我们假设要调用这个函数：

		System.out.print("先序遍历：");
		BT.CreateBiTree().PreorderTraversal();

• 因为我们没有一个像数组一样的东西，储存到数据，导致我们只能像以上形式用。
• C语言版能行，是因为C有指针，而Java是引用。两者不完全一样。

3. Java语言版改进，用队列来帮我们

在这里插入代码片

4. Java语言版改进，用栈来帮我们

在这里插入代码片

难点二：二叉树的泛型