关于二叉树的一些问题

朱雀 2021-11-19 14:44 341阅读 0赞

1，写一个算法，要求给定一个二叉树，算法能够返回其高度？

解答：可以递归地去求子树的高度，这个问题的子问题就是，以当前节点为根的树德高度，为其左右子树高度的最大者再+1。定义空节点的高度为-1，叶子节点的高度为0，伪代码如下：

int Tree-Height(Node\* root)               //root为当前所访问节点

>  if (root == NULL)

>  return -1;

>   else

> > return max( Tree-Height(root.left()), Tree-Height(root.right()) ) +1;

2，给定一颗二叉树和两个节点，写一个算法求离他们最近的公共父节点（假设：除了关键字key之外，1，每个节点有父指针，左右孩子指针的情况，2，每个节点只有左右孩子指针的情况），要求给出这两种假设下的算法？

解答： 先给出在条件1下的解答，即每个节点包含指向父节点的指针parent的情况。这个问题可以规约为求两个单向链表的交点问题，假设两个节点分别为x和y，那么以x为链表起点，以该二叉树根节点为终点的链表就是L(x)，相应的以y为链表起点，以二叉树根为终点的链表就是L(y)，那么问题就归结为求这两个链表L(x)和L(y)交点问题。伪代码如下：

Node \*common\_parent(Node \*n, Node \*x, Node \*y)

> //先求出两个链表的长度L1和L2
> 
> int L1=0;
> 
> int L2=0;
> 
> int distance=0;     //两个链表长度之差
> 
> Node \*t1=x;
> 
> Node \*t2=y;
> 
>  //求两个链表的长度
> 
> while(t1 -> parent != NULL)
> 
> \{

> > t1 = t1->parent;
> > 
> > L1++;
> 
> \}  
> while(t2 -> parent != NULL)

> \{

> > t2 = t2 -> parent;
> 
> > L2++;

> \}
> 
> distance = L1 > L2 ? L1-L2  : L2-L1;
> 
> //用两者的长度之差来修正长链表的其实位置
> 
> t1 = L1 > L2 ? x : y ;
> 
> t2 = L1 > L2 ? y : x ;

> while(distance >0 )

> > t1 = t1 -> parent;
> 
> //然后两个链表分别从修正后的起始位置开始，一块移动，直到某个相同的节点停止，该节点就是答案

> while(t1 != t2)

> \{

> > t1 = t1 -> parent;
> 
> > t2 = t2 -> parent;

> \}

> return t1;

在程序中有比较两个节点是否相同的情况，只需要比较指向它的存储地址（即指针内容）即可。

3，给定一个二叉树，求这个树中距离最远的两个节点的距离？（提示：这个题目是求二叉树高度的扩展）

解答：还是利用递归的思想来求，分析这个问题的子问题就是，以当前节点为根的子树中两个节点的最远距离，就是左子树中两个节点的最远距离max\_left、右子树中两个节点的最远距离max\_right和左右子树的高度之和left\_height+right\_height+2，这三个值中的最大值。定义空节点的高度为-1，左右子树的最大两个节点的距离为-1.

由于除了要保存最大距离之外，还要要在递归的过程中求树的高度，所以要用一个结构体来存储每次的返回值：

struct info

> int max\_value;
> 
> int height;

\};

int max\_distance(Node \*n)

> info value, value\_left, value\_right;

> if(n == NULL)

> \{

> > value.max\_value=-1;
> > 
> > value.height=-1;
> > 
> > return value;

> \}
> 
> value\_left= max\_distance(n -> left);  
> value\_right= max\_distance(n -> right);

> //设置当前节点下的树中相距最远的两个节点的距离  
> 
> 
> value.max\_value = max\{ value\_left.max\_value, value\_right.max\_value, value\_left.height+value\_right.height+2 \};  
> 
> //设置当前节点的高度
> 
> value.height = max\{ value\_left.height, value\_right.height \} +1;
> 
> return value;
> 
> \}

4，石子移动问题，现在假定有n个节点的二叉树，并且有n个石子散落在这n个节点的二叉树中，每个节点可能有0个，1个或多个石子，写一个算法，能够将所有石子平均的分配在每个节点上，并且能够证明该算法是移动的最少次数的算法。

转载于:https://www.cnblogs.com/kevinLee-xjtu/archive/2011/11/26/2299112.html