`
jaychang
  • 浏览: 734631 次
  • 性别: Icon_minigender_1
  • 来自: 嘉兴
社区版块
存档分类
最新评论

二叉排序树转双向链表(要求无任何新增节点)

阅读更多

题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。
  比如将二元查找树
                                         10
                                       /      \
                                    6         14
                                   /   \      /  \
                                  4    8   12    16


转换成双向链表
4=6=8=10=12=14=16。
  分析:本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决,本题也不例外。

我们可以中序遍历整棵树。按照这个方式遍历树,比较小的结点先访问。如果我们每访问一个结点,假设之前访问过的结点已经调整成一个排序双向链表,我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后,整棵树也就转换成一个排序双向链表了。

 

 


#include <stdio.h>
#include <stdlib.h>

#define N 20

int count = 0;
typedef struct tree
{
   int num;
   struct tree* lchild;
   struct tree* rchild;
}TREE;

int add_tree(TREE** T, int num)
{
    if(*T == NULL)
     {
       *T = (TREE*)malloc(sizeof(TREE));
        (*T)->num = num;
       (*T)->lchild = NULL;
       (*T)->rchild = NULL;
     }
    else if((*T)->num < num)
      return add_tree(&((*T)->rchild),num);
    else
      return add_tree(&((*T)->lchild),num);
}

int mid_walk_tree(TREE* T)
{
    if(T!=NULL)
     {
        mid_walk_tree(T->lchild);
        count++;
        if(count%10 == 0)
         printf("%d\n",T->num);
        else
         printf("%d\t",T->num);
       
        mid_walk_tree(T->rchild);
      }
}

int convert_node(TREE* T,TREE** L)
{
   if(T == NULL)
     return 0;
     
   TREE* pCurrent = T;
  
   if(pCurrent->lchild != NULL)
     convert_node(pCurrent->lchild, L);
   
   pCurrent->lchild = *L;
   if(*L != NULL)
     (*L)->rchild = pCurrent;
    
   *L = pCurrent;
  
   
   if(pCurrent->rchild != NULL)
     convert_node(pCurrent->rchild, L);
}

TREE* tree_2_list(TREE* T)
{
   TREE* L = NULL;
   convert_node(T, &L);
  
   TREE* list_head = L;
   L->rchild = NULL;
  
   while(list_head && list_head->lchild)
     list_head = list_head->lchild;
  
   return list_head;
}

void print_list(TREE* H)
{
    count = 0;
    if(H!=NULL)
      printf("H is not null\n");
    else
      {
       printf("H is null\n");
       return;
       }
      
      
    while(H!=NULL)
     {
        count++;
        if(count%10 == 0)
          printf("%d\n",H->num);
        else
          printf("%d\t",H->num);
         
         H = H->rchild;
      }
}

int main(int argc, char *argv[])
{
   srand((unsigned)time(NULL));
   TREE* T = NULL;
   int num;
   int i = 0;
   
    for(;i<N;i++)
     {
       num = rand()%100 + 50;
       add_tree(&T, num);
     }
  
   printf("tree walk is:\n");
   mid_walk_tree(T);
  
   TREE* head = tree_2_lis t(T);
  
   printf("list walk is:\n");
   print_list(head);
  
   system("PAUSE");    
   return 0;

}
 
分享到:
评论

相关推荐

    二叉平衡树改进物联网数据流分析效率.pptx

    它是一种特殊的二叉搜索树,其中任何节点的两个子树的高度差最多为1。这种特性使得二叉平衡树能够在保持树形结构的同时,保持较高的查询效率。 - **性质**:二叉平衡树的查找效率与树的高度成线性关系,这意味着其...

    程序员面试题精选100题(更新至60)

    题目要求不新增任何节点的情况下,将给定的二叉查找树转化为一个排序的双向链表。 **二叉查找树的特性**:二叉查找树是一种特殊的二叉树,其中每个节点的值都大于其左子树中的任意节点的值,小于其右子树中的任意...

    程序员面试题精选100题

    - **题目描述**:给定一棵二叉查找树,要求不新增节点的情况下,将其转换为一个排序的双向链表。 - **示例**: - 输入的二叉查找树如下: ``` 10 / \ 6 14 / \ / \ 4 8 12 16 ``` - 输出的排序双向链表应为...

    数据结构与算法 全 数据结构与算法全 Java

    - **双向链表(带哨兵)**:每个节点都有指向前后节点的指针。 - **环形链表(带哨兵)**:最后一个节点指向头节点,形成闭环。 **习题** 1) **反转单向链表**:实现反转单向链表的算法。 2) **根据值删除节点**:...

    2012计算机考研大纲解析(全部科目).pdf

    考生需要熟悉树的各种性质,树和二叉树的存储结构,森林、树和二叉树之间的转换,线索化二叉树,以及二叉树的应用,如二叉排序树、平衡二叉树和Huffman树。二叉树的前、中、后三种遍历方式的算法设计是复习的重点。...

    海文10年计算机大纲完全解读二数据结构.doc

    二叉树的应用,如二叉排序树、平衡二叉树(如AVL树和红黑树)以及Huffman树,都是需要深入理解的部分。树的遍历(前序、中序、后序)是历年考试的重点和难点,要求考生能够熟练设计相应的算法。 在选择题中,常见的...

    计算机考研大纲.pdf

    二叉树的应用如二叉排序树、平衡二叉树(AVL树和红黑树)和Huffman树也需要熟练掌握。树的遍历(前序、中序、后序)是常考点,包括递归和非递归算法的设计。 图的相关知识包括图的定义、存储方式以及深度优先搜索和...

    数据结构习题解析

    - 双向链表支持双向访问,即每个节点都有指向前后两个方向的指针。 - 这种结构使得数据的检索速度更快,特别是在需要频繁地从前向后或从后向前遍历时。 **结论**:正确答案是A。 **14. 设计一个判别表达式中左右...

    新东方2022计算机考研大纲解析之数据结构.docx

    二叉排序树、平衡二叉树和Huffman树也是考察重点。 5. 图:理解图的定义和存储方式,熟练掌握深度遍历和广度遍历算法,以及基于图的其他算法如最小生成树(PRIM和KRUSKAL算法)、拓扑排序和关键路径问题。 复习时,...

Global site tag (gtag.js) - Google Analytics