# 写出生成具最少节点、高度为 H 的 AVL 树的程序，函数得运行时间是多少？

	AvlTree MinGenTree(int height, int* lastNode)
	{
	AvlTree T;

	if(height>=0)
	{
	T = malloc(sizeof(AvlNode));
	T->left = MinGenTree(height-1,lastNode);
	T->data = ++(*lastNode);
	T->height = 0;
	T->right = MinGenTree(height-2,lastNode);
	// update height
	T->height = MAX(Height(T->left),Height(T->right))+1;
	return T;
	}
	else
	return NULL;
	}
	// Generate minimal AVL tree
	AvlTree MinAvlTree(int H)
	{
	int lastNodeAssigned = 0;
	return MinGenTree(H,&lastNodeAssigned);
	}

运行时间为 O (N)。

# 编写一个函数，使它生成一棵具有关键字从 1 直到 $2^{H+1}-1$ 且高为的理想平衡二叉查找树。该函数运行时间是多少？

	BinaryTree MakeBinaryRandomTree1(int lower,int upper)
	{
	BinaryTree T;
	int RandomValue;

	T = NULL;
	if(lower<=upper)
	{
	T = malloc(sizeof(TreeNode));
	if(T!= NULL)
	{
	T->data = RandomValue = RandInt(lower, upper);
	T->left = MakeBinaryRandomTree1(lower, RandomValue-1);
	T->right = MakeBinaryRandomTree1(RandomValue+1, upper);
	}
	}
	return T;
	}

	BinaryTree MakeBinaryRandomTree(int N)
	{
	return MakeBinaryRandomTree1(1, N);
	}

运行时间为 O (N)。

# 编写一个函数以二叉查找树 T 和两个有序的关键字 $k_1$ 和 $k_2$ $(k_1\le k_2)$ 作为输人，打印树中所有满足 $k_1 \le Key(X) \le k_2$ 的元素 X。除去可以排序外・不对关键字的类型做任何假设。所写的程序应该以平均时间 $O(K+\log_{2}{N})$ 运行，其中 K 是所打印的关键字的个数确定你的算法的运行时间界

	void BinaryPrintRange(ElementType Lower,ElementType Upper,BinaryTree T)
	{
	if(T!= NULL)
	{
	if(Lower<=T->data)
	BinaryPrintRange(Lower,Upper,T->left);
	if(Lower<=T->data&&T->data<=Upper)
	printf("%d ",T->data);
	if(T->data<=Upper)
	BinaryPrintRange(Lower,Upper,T->right);
	}
	}

算法的运行时间界为 $O(K+\log_{2}{N})$ 。

# 由一个自动程序来生成二叉树：通过给树的每一个节点指定坐标（x，y），围绕每个坐标画一个圆圈，并将每个节点连到它的父节点上。假设在存储器中存有一棵二叉查找树（或许由此程序生成）并设每个节点都有两个附加的域存放坐标。

a. 坐标 x 可以通过指定中序遍历数来计算。对于树中的每个节点写出这样一个例程。

	// Calculate binary tree X coordinate using inorder traversal
	void calcX(AvlTree T,int *LastX)
	{
	if(T!=NULL)
	{
	calcX(T->left,LastX);
	T->x = ++(*LastX);
	calcX(T->right,LastX);
	}
	}

b. 坐标 y 可以通过使用节点深度的相反数算出。对于树中的每一个节点写出这样的例程。
层序遍历需要用到队列，队列实现在之前得文章里。

	/*
	Calculate binary tree Y coordinate using level-order traversal.
	If you need to use this function, you need to change
	typedef int ElementType to typedef AvlTree ElementType in queueArrary.h
	*/
	void calcY(AvlTree T)
	{
	Queue queue = EmptyQueue(10);

	Enqueue(queue,T);
	int depth = T->height, count = 1, nextcount = 0;

	while(!QueueIsEmpty(queue))
	{
	for(int i = 0; i < count; i++)
	{
	AvlTree temp = QueueFront(queue);
	if(temp->left!= NULL)
	{
	Enqueue(queue,temp->left);
	nextcount++;
	}
	if(temp->right!= NULL)
	{
	Enqueue(queue,temp->right);
	nextcount++;
	}
	temp->y = depth;
	Dequeue(queue);
	}
	depth--;
	count = nextcount;
	nextcount = 0;
	}
	}
	// Calculate X and Y coordinates
	void Coordinates(AvlTree T)
	{
	int i = 0;
	calcX(T,&i);
	calcY(T);
	}

# 写出向一棵 B - 树进行插入的例程。

插入和删除代码贴出来也是长的一批，最重要的操作其实是分裂和合并。
一句两句说不清，推荐直接去 geeksforgeeks 看，写的老详细了。

插入参考链接

	#define MIN_T 3
	#define MAX_T (MIN_T * 2)
	typedef int KeyPosition;
	typedef int BtreeKeyType;
	typedef struct _BTreeNode BTreeNode;
	typedef BTreeNode* BTree;
	typedef BTreeNode* BtreePosition;
	typedef BTree* BTreeAdress;

	struct _BTreeNode {
	int KeyNum;//record number of the keywords
	bool IsLeaf; //check if this is a leaf.true is leaf.false is not leaf
	BtreeKeyType Keywords[MAX_T-1]; //store keywords
	BTree Child[MAX_T]; //store child nodes.
	};
	/*
	* Insert keywords for the entire tree
	* When the tree has only one keyword and is full, a new node needs to be established as the root node of the tree,
	* When the root node of the original tree is used as the child node of the new node, the split operation is performed
	* Otherwise, directly perform the non-full node insertion operation
	*/
	BTree BTreeInsert(BTree T, BtreeKeyType Keywords)
	{
	// if B tree is empty
	if(T==NULL)
	{
	T = malloc(sizeof(BTreeNode));
	T->Keywords[0] = Keywords;
	T->KeyNum = 1;
	T->IsLeaf = true;
	}
	else //if B tree is not empty
	{
	// if root is full
	if(T->KeyNum == MAX_T - 1)
	{
	/*
	--------------- ----- ------
	T->\|10 20 30 40 50\| -> \| \|<-X -> \| 30 \| <-X
	---------------- ----- ------
	/ / \
	/ / \
	T->\|10 20 30 40 50\| T->\|10 20\| \|40 50\|
	*/
	BTree X = malloc(sizeof(BTreeNode));
	X->KeyNum = 0;
	X->IsLeaf = false;
	X->Child[0] = T;
	T = X;

	//Split the old root and move 1 keywords to the new root
	BTreeSplit(T,0);

	// New root has two children now. Decide which of the
	// two children is going to have new keywords
	int i = 0;
	if(T->Keywords[0]<Keywords) i++;
	BTreeInsertNotFull(T->Child[i], Keywords);
	}
	else //if root is not full
	BTreeInsertNotFull(T, Keywords);
	}
	return T;
	}
	/*
	* Insert keywords for non-full nodes
	*/
	void BTreeInsertNotFull(BTree T, BtreeKeyType Keywords)
	{
	int i = T->KeyNum - 1;

	if(T->IsLeaf==true)
	{
	/* When the node is a leaf node, find the corresponding position,
	insert the keywords, and modify the number of keywords */
	while(i >=0 && Keywords < T->Keywords[i])
	{
	T->Keywords[i+1] = T->Keywords[i];
	i--;
	}
	T->Keywords[i+1] = Keywords;
	T->KeyNum++;
	}
	else
	{
	/* When it is not a leaf node, find the corresponding child node to determine whether it is a full node,
	if yes, then split, if not, recursively insert.
	----- -------
	\|30 \| \|30 60\|
	----- -------
	/ \ / \| \
	/ \ / \| \
	------- ----------------- ------- ------ -------
	\|10 20\| \| 40 50 60 70 80\| --> \|10 20\|\|40 50\| \|70 80\|
	------- ----------------- ------- ------ -------
	*/
	while(i >=0 && Keywords < T->Keywords[i])
	i--;
	i++;
	if(T->Child[i]->KeyNum == MAX_T - 1)
	{
	BTreeSplit(T, i);
	if(Keywords > T->Keywords[i])
	i++;
	}

	BTreeInsertNotFull(T->Child[i], Keywords);
	}
	}
	/*
	* Split the full node of the child node whose location is N
	--------------- ------------------
	X-> \| 1 50 100 200 \| X-> \| 1 50 80 100 200 \|
	--------------- -------------------
	/ / \ \ \ / / / \ \ \
	\ ---> / \
	---------------- ------ ---------
	Y-> \| 55 70 80 85 90 \| Y-> \| 55 70 \| \| 85 90 \| <-Z
	----------------- --------- ---------
	/ / / \ \ \ / \ \ / \ \
	*/
	void BTreeSplit(BTree X, KeyPosition N)
	{
	/*Create a new empty node Z and Initialize the empty node Z,
	copy the information of the child node Y to the new node Z */
	BTree Z = malloc(sizeof(BTreeNode));
	BTree Y = X->Child[N];
	Z->IsLeaf = Y->IsLeaf;
	Z->KeyNum = MIN_T - 1;

	/* Copy the (Min_T-1) keywords after the child node Y to the new node Z,
	and change the number of keywords of the child node Y */
	for(int i = 0; i < MIN_T-1; i++)
	{
	Z->Keywords[i] = Y->Keywords[i+MIN_T];
	}
	Y->KeyNum = MIN_T - 1;

	/* If the child node Y is not a leaf node,
	copy the child of the node Y to the new node Z accordingly */
	if(Y->IsLeaf==false)
	{
	for(int i = 0;i<MIN_T -1; i++)
	Z->Child[i] = Y->Child[i+MIN_T];
	}

	/* Move the keyword corresponding to the parent node X and the position of the child node back one place */
	for(int i = X->KeyNum; i>N;i--)
	{
	X->Keywords[i] = X->Keywords[i-1];
	X->Child[i+1] = X->Child[i];
	}

	/* Add new keywords and child nodes to the parent node X,
	and modify the number of keywords */
	X->Child[N+1] = Z;
	X->Keywords[N] = Y->Keywords[MIN_T-1];
	X->KeyNum = X->KeyNum + 1;
	}

# 写出从一棵 B - 树执行删除的例程。

删除参考链接

	// Returns the node with the smallest key of the root node tree,
	// and the position of the key must be 0
	BtreePosition BTreeFindMin(BTree T)
	{
	if(T->KeyNum < 1)
	{
	printf("FindMin failed\n");
	return NULL;
	}

	if(T->IsLeaf)
	return T;
	else
	T = BTreeFindMin(T->Child[01]);

	return T;
	}
	// Returns the node with the largest key of the root node tree,
	// the position of the key must be the n-1 value of the node
	BtreePosition BTreeFindMax(BTree T)
	{
	if(T->KeyNum < 1)
	{
	printf("FindMax failed\n");
	return NULL;
	}

	if(T->IsLeaf)
	return T;
	else
	T = BTreeFindMax(T->Child[T->KeyNum - 1]);

	return T;
	}
	/*
	* Delete the keyword whose leaf node position is N
	* Directly move the keyword after position N forward by one
	*/
	void BTreeDeleteLeaf(BTree T, int N)
	{
	for(int i=N; i<T->KeyNum-1; i++)
	T->Keywords[i] = T->Keywords[i+1];

	T->KeyNum = T->KeyNum - 1;
	}
	// Delete the keyword at position N of the non-leaf node layer
	KeyPosition BtreeDeleteNotLeaf(BTree T, KeyPosition N)
	{
	// Get the left and right node pointers of the keywords
	BTree Left = T->Child[N];
	BTree Right = T->Child[N + 1];
	BtreeKeyType temp = 0;

	/*
	* When the number of left child node keywords of the keyword currently at this position is greater than or equal to T,
	* Find the key predecessor of the position (the largest key of the left child node)
	*/
	if(Left->KeyNum >= MIN_T)
	{
	BTree tmp = BTreeFindMax(Left);
	temp = T->Keywords[N];
	T->Keywords[N] = tmp->Keywords[tmp->KeyNum-1];
	tmp->Keywords[tmp->KeyNum-1] = temp;
	}
	/*
	* On the contrary, if the right child node meets the conditions,
	* find the successor (that is, the smallest key of the right child node)
	*/
	else if(Right->KeyNum >= MIN_T)
	{
	BTree tmp = BTreeFindMin(Right);
	temp = T->Keywords[N];
	T->Keywords[N] = tmp->Keywords[0];
	tmp->Keywords[0] = temp;
	//Keyword position moved to the next position
	N++;
	}
	/*
	* When the left and right child nodes do not meet the conditions,
	* merge the two child nodes
	*/
	else
	N = BTreeMerage(T,N);

	return N;
	}
	/*
	* Merge two keywords whose number is T-1 and the parent node is the child node whose parent location is location
	* Connect two child nodes with the keyword corresponding to the parent node as the intermediate value
	* and return the position of the child node that needs to be dropped
	*/
	KeyPosition BTreeMerage(BTree Parent,KeyPosition N)
	{
	if(N==Parent->KeyNum) N--;

	BTree Left = Parent->Child[N];
	BTree Right = Parent->Child[N+1];

	/* Copy the keyword corresponding to the parent node
	and all the keywords of the right sibling to the node,
	and modify the n value of the left child */
	Left->Keywords[Left->KeyNum] = Parent->Keywords[N];
	for(int i = 0; i < Right->KeyNum; i++)
	{
	Left->Keywords[MIN_T+i] = Right->Keywords[i];
	/* Left->KeyNum++;*/
	}

	/* If there is a child node, also copy to this node */
	if(Right->IsLeaf==false)
	{
	for(int i = 0; i < Right->KeyNum; i++)
	Left->Child[MIN_T+i] = Right->Child[i];
	}

	Left->KeyNum += Right->KeyNum+1;
	Right->KeyNum = 0;

	/* Change the corresponding keyword and child node position of the parent node */
	for(int i = N; i < Parent->KeyNum-1; i++)
	{
	Parent->Keywords[i] = Parent->Keywords[i+1];
	Parent->Child[i+1] = Parent->Child[i+2];
	}

	Parent->KeyNum--;
	BTree temp = Right;
	Right = NULL;
	free(temp);

	return N;
	}
	// delete keywords in the node
	void BTreeDelete(BTree T, BtreeKeyType Keywords)
	{
	int i = 0;

	// find keywords location or descending child node position
	while(i<T->KeyNum&&Keywords>T->Keywords[i]) i++;

	// if keywords is found
	if(i<T->KeyNum&&Keywords==T->Keywords[i])
	{
	// if keywords is in leaf nodes
	if(T->IsLeaf==true)
	BTreeDeleteLeaf(T,i);
	else // if keywords is not in leaf nodes
	{
	i = BtreeDeleteNotLeaf(T,i);
	BTreeDelete(T->Child[i],Keywords);
	}
	}
	else // if keywords is not found
	{
	if(T->IsLeaf==true)//Last keyword not found
	printf("the keywords is not in the tree\n");
	else
	{
	/*
	Traverse down to find the keyword, if it satisfies MIN_T,continue the recursion,
	otherwise, adjust the number of nodes in the left subtree or the right subtree first,
	after MIN_T is satisfied, continue the recursion.
	*/
	if(T->Child[i]->KeyNum >= MIN_T)
	BTreeDelete(T->Child[i], Keywords);
	else
	{
	if(i>0 && T->Child[i-1]->KeyNum >= MIN_T)
	BTreeBorrowPrev(T,i);
	else if(i>0 && T->Child[i+1]->KeyNum >=MIN_T)
	BTreeBorrowNext(T,i);
	else
	i = BTreeMerage(T,i);

	BTreeDelete(T,Keywords);
	}
	}
	}
	}
	/*
	delete 11
	------- ------
	X-> \|1 9 20\| X->\|1 7 20\|
	------ ------
	/ \ -> / \
	--------- ------ ------- ---------
	Y->\|4 5 6 7\| \|11 12\|<-Z Y->\|4 5 6\| \|9 11 12\| <-Z
	--------- ------ ------ ---------
	*/
	void BTreeBorrowPrev(BTree X, KeyPosition Position)
	{
	BTree Y = X->Child[Position-1];
	BTree Z = X->Child[Position];

	for(int i = Z->KeyNum-1; i >= 0; i--)
	Z->Keywords[i+1] = Z->Keywords[i];

	Z->Keywords[0] = X->Keywords[Position-1];
	X->Keywords[Position-1] = Y->Keywords[Y->KeyNum-1];

	if(Z->IsLeaf==false)
	{
	for(int i = Z->KeyNum;i>=0;i--)
	Z->Child[i+1] = Z->Child[i];
	Z->Child[0] = X->Child[ X->KeyNum];
	}

	Z->KeyNum++;
	Y->KeyNum--;
	}
	/*
	delete 2
	----- -----
	X-> \|1 4 9\| X->\|1 5 9\|
	------ ------
	/ \ -> / \
	--- ------- ----- -----
	Y-> \|2 3\| \|5 6 7 8\|<-Z Y->\|2 3 4\| \|6 7 8\| <-Z
	----- --------- ------- -------
	*/
	void BTreeBorrowNext(BTree X, KeyPosition Position)
	{
	BTree Y = X->Child[Position];
	BTree Z = X->Child[Position + 1];

	Y->Keywords[Y->KeyNum] = X->Keywords[Position];
	X->Keywords[Position] = Z->Keywords[0];

	for(int i= 0; i<Z->KeyNum-1; i++)
	Z->Keywords[i] = Z->Keywords[i+1];

	if(Z->IsLeaf==false)
	{
	Y->Child[Y->KeyNum+1] = Z->Child[0];
	for(int i= 0; i<Z->KeyNum-1; i++)
	Z->Child[i] = Z->Child[i+1];
	}

	Y->KeyNum++;
	Z->KeyNum--;
	}

实际上书中描述的方法其实是 B + 树，而不是 B 树。

# M 阶 B* 树（B-tree）是其每个内部节点的儿子数在 2M/3 和 M 之间的 B - 树。描述一种向 B 树进行插入的方法

找到第一个兄弟节点，若有空位，插入，没有，移至下一个兄弟节点。
若插入，发现数据超出规范，把多余的数据移至下一兄弟节点 (大约 1/2), 往复直至不影响规范。
若遍历完全部兄弟节点，仍无法插入，则开辟新的兄弟节点。

# 编写一个过程使该过程遍历一棵用儿子 / 兄弟链存储的树

	// Function to traverse all nodes in a subtree rooted with
	// this node
	void BTreeTraverse(BTree T)
	{
	// There are n keys and n+1 children, traverse through n
	// keys and first n children
	for (int i = 0; i < T->KeyNum; i++)
	{
	// If this is not leaf, then before printing keywords[i],
	// traverse the subtree rooted with Child[i].
	if(T->IsLeaf==false) BTreeTraverse(T->Child[i]);
	printf("%d ",T->Keywords[i]);
	}
	// Print the subtree rooted with last child
	if(T->IsLeaf==false) BTreeTraverse(T->Child[T->KeyNum]);
	}

# 如果两棵二叉树或者都是空树，或者非空且具有相似的左子树和右子树，则这两二叉树是相似的。编写一个函数以确定是否两棵二叉树是相似的。

	// Compare if two binary trees are similar
	bool BinarySimilar(BinaryTree T1,BinaryTree T2)
	{
	if(T1==NULL\|\|T2==NULL)
	return T1==NULL&&T2==NULL;

	return BinarySimilar(T1->left,T2->left)&&BinarySimilar(T1->right,T2->right);
	}

# 如果树 $T_1$ 通过交换其（某些）节点的左右儿子变换成树 $T_2$ ，则称树 $T_1$ 和 $T_2$ 是同构的 (isomorphic)。给出一个多项式时间算法以决定是否两棵树是同构的。

两棵树为空树，为真
一棵树为空树，另一棵树不是空树，为假
两棵树相应位置元素不一致，为假
若两棵树左子树相应位置左子树为空，转至右子树比较
若两棵树左子树相应位置右子树为空，转至左子树比较
若两棵树相应位置的元素一致且左右子树不为空，分别继续转至左子树和右子树比较，否则，分别转转至两棵树不同左右子树比较
运行时间为 O (N)。

# 由于具有 N 个点的二叉查找树有 N+1 个 NULL 指针，因此在二叉查找树中指定给指针信息的空间的一半被浪费了。设若一个节点有一个 NULL 左儿子，我们使它的左儿子指向它的中缀前驱 (inorder predecessor)，若一个节点有一个 NULL 右儿子，我们让它的右儿子指向它的中缀后继（inorder successor）。这就叫做线索树 (threadedtree)，而附加的指针就叫做线索（thread）。

# a. 我们如何能够从实际的儿子指针中区分出线索？

新增一个标志位表示线索就行了

# b. 编写执行向由上面描述的方式形成的线索树进行插人和删除例程

我这里实现的是双线索树。还是那句话，建议直接去 geeksforgeeks 看，它比我详细多了，这东西都能直接写一遍新文章了。

插入与删除参考链接

	typedef int ThreadTreeDataType;
	typedef struct _ThreadTreeNode ThreadTreeNode;
	typedef ThreadTreeNode* ThreadTree;
	typedef ThreadTreeNode* ThreadTreePosition;
	typedef ThreadTree* ThreadTreeAddress;

	struct _ThreadTreeNode{
	ThreadTreeDataType Data;
	// true is thread, false is not thread
	bool RightThread; //right lead line
	bool LeftThread; //left lead line
	ThreadTree Left;
	ThreadTree Right;
	};
	ThreadTree ThreadTreeInsert(ThreadTree root,ThreadTreeDataType Data)
	{
	ThreadTree ptr = root;
	ThreadTree par = NULL;

	while(ptr!=NULL)
	{
	if(Data==ptr->Data)
	{
	printf("Data has already been inserted\n");
	return root;
	}

	par = ptr;

	if(Data < ptr->Data && ptr->LeftThread ==false)
	ptr = ptr->Left;
	else if(Data > ptr->Data && ptr->RightThread ==false)
	ptr = ptr->Right;
	else
	break;
	}
	ThreadTree temp = malloc(sizeof(ThreadTreeNode));
	temp->Data = Data;
	temp->LeftThread = temp->RightThread = true;

	if(par == NULL)
	{
	root = temp;
	temp->Left = temp->Right = NULL;
	}
	else if(Data < par->Data)
	{
	temp->Left = par->Left;
	temp->Right = par;
	par->LeftThread = false;
	par->Left = temp;
	}
	else
	{
	temp->Left = par;
	temp->Right = par->Right;
	par->RightThread = false;
	par->Right = temp;
	}

	return root;
	}
	// find the element at the tree and delete it(replace it with a right subtree minimum)
	ThreadTree ThreadTreeDelete(ThreadTree root,ThreadTreeDataType Data)
	{
	ThreadTree par = NULL, ptr = root;

	// set true if key is found
	bool found = false;

	// The while loop traverses to find the Data location
	while (ptr!= NULL)
	{
	if(Data == ptr->Data)
	{
	found = true;
	break;
	}
	par = ptr;
	if(Data < ptr->Data&&ptr->LeftThread == false)
	ptr = ptr->Left;
	else if(Data > ptr->Data && ptr->RightThread == false)
	ptr = ptr->Right;
	else
	break;
	}

	if(!found)
	printf("the data %d is not in the thread tree\n",Data);
	// two children
	else if(ptr->LeftThread==false && ptr->RightThread== false)
	root = ThreadTreeDeleteTwoChildren(root,par,ptr);
	// only left children
	else if(ptr->LeftThread==false)
	root = ThreadTreeDeleteOneChildren(root,par,ptr);
	// only right children
	else if(ptr->RightThread==false)
	root = ThreadTreeDeleteOneChildren(root,par,ptr);
	// no children
	else
	root = ThreadTreeDeleteLeaf(root,par,ptr);

	return root;
	}

	ThreadTree ThreadTreeDeleteLeaf(ThreadTree root,ThreadTree parent,ThreadTree T)
	{
	if(parent==NULL)
	root = NULL;
	else if(T == parent->Left)
	{
	parent->LeftThread = true;
	parent->Left = T->Left;
	}
	else if(T == parent->Right)
	{
	parent->RightThread = true;
	parent->Right = T->Right;
	}
	free(T);

	return root;
	}

	ThreadTree ThreadTreeDeleteOneChildren(ThreadTree root,ThreadTree parent,ThreadTree T)
	{
	ThreadTree child;

	if(T->LeftThread == false) child = T->Left;
	else child = T->Right;

	if(parent == NULL) root = child;
	// left children
	else if(T == parent->Left) parent->Left = child;
	// right children
	else parent->Right = child;

	// find successor and predecessor
	ThreadTree succ = ThreadTreeFindSucc(T);
	ThreadTree pred = ThreadTreeFindPred(T);

	if(T->LeftThread == false) pred->Right = succ;
	else if(T->RightThread == false) succ->Left = pred;

	free(T);
	return root;
	}

	ThreadTree ThreadTreeDeleteTwoChildren(ThreadTree root,ThreadTree parent,ThreadTree T)
	{
	// find inorder successor and its parent
	ThreadTree parsucc = T;
	ThreadTree succ = T->Right;

	// find leftmost child of successor
	while(succ->LeftThread == false)
	{
	parsucc = succ;
	succ = succ->Left;
	}

	T->Data = succ->Data;

	if(succ->LeftThread&&succ->RightThread)
	root = ThreadTreeDeleteLeaf(root,parsucc,succ);
	else
	root = ThreadTreeDeleteOneChildren(root,parsucc,succ);

	return root;
	}
	// find successor or left leaf node(used in delete)
	ThreadTree ThreadTreeFindSucc(ThreadTree T)
	{
	// find successor
	if(T->RightThread == true) return T->Right;

	// find left leaf node to delete
	T = T->Right;
	while(T->LeftThread == false) T = T->Left;

	return T;
	}
	// find predecessor or right leaf node(used in delete)
	ThreadTree ThreadTreeFindPred(ThreadTree T)
	{
	// find predecessor
	if(T->LeftThread == true) return T->Left;

	// find right leaf node to delete
	T = T->Left;
	while(T->RightThread == false) T = T->Right;

	return T;
	}
	ThreadTree ThreadTreeFindMin(ThreadTree T)
	{
	if(T==NULL) return NULL;
	while(T!= NULL) T = T->Left;
	return T;
	}
	ThreadTree ThreadTreeFindMax(ThreadTree T)
	{
	if(T==NULL) return NULL;
	while(T!= NULL) T = T->Right;
	return T;
	}

# c. 使用线索树的优点是什么？

无需递归，能更轻松遍历树

# 二叉查找树预先假设搜索是基于每个记录只有一个关键字。设我们想要能够执行或者基于关键字 $Key_1$ 或者基于关键字 $Key_2$ 的查找。

# a. 一种方法是建立两棵分离的二又树。这需要多少额外的指针？

2N 个指针，因为有两棵节点为 N 的二叉树。

# b. b. 另一种方法时使用 2-d 树，2-d 树类似于二叉树，其不同之处在于，在偶数层用 Key1 来分叉，而在奇数层用 Key2 来分叉。编写一个向一棵 2-d 树进行插入的例程。

2-d 树又叫 K-D 树。还是之前那句话，去 geeksforgeeks 看，要详细讲这里压根讲不完。

	// Inserts a new node and returns root of modified tree
	// The parameter depth is used to decide axis of comparison
	// where 0 represents the x-axis and 1 represents the y-axis
	static kdTree kdTreeInsertRec(kdTree root, kdTreeDataType point[],unsigned int depth)
	{
	// calculate current dimension (cd) of comparison
	unsigned int cd = depth % DIM;

	if(root == NULL)
	{
	root = malloc(sizeof(kdTreeNode));

	for(int i = 0; i < DIM; i++)
	root->data[i] = point[i];

	root->left = root->right = NULL;
	}
	else if(point[cd]<root->data[cd])
	root->left = kdTreeInsertRec(root->left, point,depth+1);
	else
	root->right = kdTreeInsertRec(root->right, point,depth+1);

	return root;
	}
	// Function to insert a new point with given point in
	// KD Tree and return new root. It mainly uses above recursive
	// function "kdTreeInsertRec"
	kdTree kdTreeInsert(kdTree root, kdTreeDataType point[])
	{
	return kdTreeInsertRec(root, point, 0);
	}

# c. 编写一个高效的过程，该过程打印同时满足约束 $Low_1 \le Key_1 \le High_1$ 和 $Low_2 \le Key_2 \le High_2$ 的树的所有记录。

实际叫你写的是 K-D 树的范围查找，而这第十二章有例程....

	// Print a point in the K D tree(default 2 D tree).
	// It satisfies the following conditions:
	// 1. Low[0] <= point[0] <= High[0]
	// 2. Low[0] <= point[1] <= High[1]
	static void kdTreePrintRangeRec(kdTree root, kdTreeDataType Low[], kdTreeDataType High[], unsigned int depth)
	{
	// calculate the current dimension (cd)
	unsigned int cd = depth % DIM;

	if(root != NULL)
	{
	if(Low[0] <= root->data[0] && root->data[0] <= High[0] &&
	Low[1] <= root->data[1] && root->data[1] <= High[1])
	printf("%d %d\n", root->data[0], root->data[1]);

	if(Low[cd] <= root->data[cd])
	kdTreePrintRangeRec(root->left,Low,High,depth+1);
	if(High[cd] >= root->data[cd])
	kdTreePrintRangeRec(root->right,Low,High,depth+1);
	}
	}
	// Print a Point in the K D tree(default 2 D tree).
	// It mainly uses kdTreePrintRangeRec()
	void kdTreePrintRange(kdTree root, kdTreeDataType Low[], kdTreeDataType High[])
	{
	kdTreePrintRangeRec(root,Low,High,0);
	}

# d. 指出如何扩充 2-d 树以处理多余两个的搜索关键字。所得到的树叫作 k-d 树

2-d 树是由在偶数层用 Key1 来分叉，而在奇数层用 Key2 来分叉形成的。
那 K-D 树则是由 K 的关键字，K 个不同的层来分叉形成的。

# 写出生成具最少节点、高度为 H 的 AVL 树的程序，函数得运行时间是多少？

# 编写一个函数，使它生成一棵具有关键字从 1 直到2H+1−12^{H+1}-12H+1−1 且高为的理想平衡二叉查找树。该函数运行时间是多少？