By

文章目录
  1. 1. 题目
  2. 2. 分析
  3. 3. 代码实现
  4. 4. 具体实验代码

题目

输入一棵排序二叉树，将此树转换成一个排序的双向链表，要求不能创建任何新的借点，只能调整指针的指向.

分析

二叉排序树的中序遍历可以得到它的排序元素，但是，但是“它不能创建任何新的节点，只能调整指针的指向”，所以，直接中序法就不可行了。

大致思路是如下的：

  • 如果当前根节点的左子树不为空，则
    1. 递归左子树
    2. 查找左子树最大的元素
    3. 将该元素的right指针指向根节点，将根节点的left指针指向该元素
  • 如果当前根节点的右子树不为空，则
    1. 递归右子树
    2. 查找右子树最小的元素
    3. 将该元素的left指针指向根节点，将根节点的right指针指向该元素

注：tree的left和right结构正好对应list的pre和next结构

      8    
    /   \
   3     10
 /   \     \
1     6     14
    /  \   /
   4    7 13 

它依次调整的点为：1(l),4(l),7(r),4(r),7(l),13(l),13(r),10(r)
      8    
    /   \
 1-3     10
    \     \
    6     14
    /  \   /
   4    7 13 
   1为3左子树的最大点，所以的右指针指向3，3的左指针指向1


       8    
    /   \
 1-3     10
    \     \
   4-6     14
      \   /
       7 13 

 4为6的左子树的最大值，所以4的右指针指向6，6左指针4

      8    
    /   \
 1-3     10
    \     \
   4-6-7   14
          /
         13

 7为6的右子树的最小值，所以7的左指针指向6，6右指针4

     8    
    /   \
 1-3     10
    \     \
     4-6-7 14
          /
         13

 4为3的右子树的最小值，所以4的左指针指向3，3右指针4

 1-3-4-6-7-8    
           \
            10
             \
             14
             /
            13

7为8左子树的最小值，所以7的右指针指向8，8的左指针指向7
这样就完成了根节点左边的转换，右边的转换思路一致

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * 查找左子树中最大的节点
 * @param T
 * @return
 */
private static TreeNode findMaxNodeInLeft(TreeNode T)
{
	TreeNode t=T.left;
	if(t!=null)
		while(t.right!=null)
		{
			t=t.right;//因为肯定右子树更加大
		}
	
	return t;
	
}

/**
 * 查找右子树种的最小节点
 * @param T
 * @return
 */
private static TreeNode findMinNodeInRight(TreeNode T)
{
	TreeNode t=T.right;
	if(t!=null)
		while(t.left!=null)
			t=t.left;
	
	return t;
}

/**
 * 二叉排序树转双向链表
 * @param T
 */
public static void convertNode(TreeNode T)
{
	if(T==null)
		return ;
	
	if(T.left!=null)
	{
		convertNode(T.left);
		TreeNode t=findMaxNodeInLeft(T);//左子树中最大的点  它一定是在叶子上面
		t.right=T;//将左子树最小的点连在根节点的左侧
		T.left=t;
		t.parent=null;
	}
	
	if(T.right!=null)
	{
		convertNode(T.right);
		TreeNode t=findMinNodeInRight(T);
		t.left=T;//将右子树最小的点连点根节点的右侧
		T.right=t;
		t.parent=null;
	}
}

具体实验代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public static void main(String[] args) {
	TreeNode root=new TreeNode();
	root.parent=new TreeNode(Integer.MAX_VALUE);//凭空设置一个超级根节点  
	root.parent.right=root;//超级根节点接管根节点
	insert(root,8);
	insert(root,3);
	insert(root,10);
	insert(root,1);
	insert(root,6);
	insert(root,14);
	insert(root,4);
	insert(root,7);
	insert(root,13);//上面的insert是构建排序二叉树
	System.out.println(root);
	convertNode(root);
	System.out.println(root);
	
	TreeNode head=root;
	while(head.left!=null)
	{
		head=head.left;//查找头结点
	}
	
	//将双向链表打印出来
	while(head.right!=null)
	{
		System.out.println(head.data);
		head=head.right;
	}
		
}

关于二叉排序树具体介绍看我之前的二叉排序树

本作品采用[知识共享署名-非商业性使用-相同方式共享 2.5]中国大陆许可协议进行许可，我的博客欢迎复制共享，但在同时，希望保留我的署名权kubiCode，并且，不得用于商业用途。如您有任何疑问或者授权方面的协商，请给我留言。

文章目录
  1. 1. 题目
  2. 2. 分析
  3. 3. 代码实现
  4. 4. 具体实验代码