首页 / 算法 / 将二叉树转为有序的双向链表

将二叉树转为有序的双向链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了将二叉树转为有序的双向链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2085字，纯文字阅读大概需要3分钟。

内容图文

一。题目要求：

输入一棵二叉排序树，现在要将该二叉排序树转换成一个有序的双向链表。而且在转换的过程中，不能创建任何新的结点，只能调整树中的结点指针的指向来实现。

 

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

typedef struct node
{
    int nValue;
    struct node *pLeft;
    struct node *pRight;
}BinaryTree;


void AddNode(BinaryTree **pTree,int nNum)
{
    BinaryTree *pTemp = NULL;
    pTemp = (BinaryTree*)malloc(sizeof(BinaryTree));
    pTemp->nValue = nNum;
    pTemp->pLeft = NULL;
    pTemp->pRight = NULL;

    //空树 新来节点就是根节点if(*pTree == NULL)
    {
        *pTree = pTemp;
        return;
    }

    //非空
    BinaryTree *pNode = NULL;
    pNode = *pTree;

    //遍历树 找到合适位置放入while(pNode)
    {
        //当前节点的值 比新来的大 if(pNode->nValue > nNum)
        {
            //新来节点放当前节点左侧if(pNode->pLeft == NULL)
            {
                pNode->pLeft = pTemp;
                return;
            }
            else
            {
                pNode = pNode->pLeft;
            }
        }
        //当前节点的值比新来的小elseif(pNode->nValue < nNum)
        {
            //新来节点放右侧if(pNode->pRight == NULL)
            {
                pNode->pRight = pTemp;
                return;
            }
            else
            {
                pNode = pNode->pRight;
            }
        }
        //相等 异常else
        {
            printf("error.\n");
            free(pTemp);
            pTemp = NULL;
            return;
        }
    }
}




BinaryTree *CreateBST(int arr[],int nLength)
{
    if(arr == NULL || nLength <=0)return NULL;

    BinaryTree *pRoot = NULL;
    int i;
    for(i = 0;i<nLength;i++)
    {
        AddNode(&pRoot,arr[i]);
    }
    return pRoot;
}

void Traversal(BinaryTree *pTree)
{
    if(pTree == NULL)return;

    Traversal(pTree->pLeft);
    printf("%d ",pTree->nValue);
    Traversal(pTree->pRight);
}


void TreeToList(BinaryTree *pTree,BinaryTree **pHead,BinaryTree **pTail)
{
    if(pTree == NULL)return;

    //按照中序遍历
    //遍历到的节点依次添加到双向链表中
    TreeToList(pTree->pLeft,pHead,pTail);

    //节点添加if(*pHead == NULL)
    {
        *pHead = pTree;
    }
    else
    {
        (*pTail)->pRight = pTree;
        pTree->pLeft = *pTail;
    }
    *pTail = pTree;

    TreeToList(pTree->pRight,pHead,pTail);
}

void Print(BinaryTree *pHead)
{
    while(pHead)
    {
        printf("%d ",pHead->nValue);
        pHead  =pHead->pRight;
    }
}

int main()
{
    int arr[] = {10,3,20,38,2,19,87};
    BinaryTree *pTree = NULL;
    pTree = CreateBST(arr,sizeof(arr)/sizeof(arr[0]));
    Traversal(pTree);
    printf("\n");
    BinaryTree *pHead = NULL;
    BinaryTree *pTail = NULL;
    TreeToList(pTree,&pHead,&pTail);
    Print(pHead);
    return0;
}

 

原文：http://www.cnblogs.com/curo0119/p/7845172.html

内容总结

以上是互联网集市为您收集整理的将二叉树转为有序的双向链表全部内容，希望文章能够帮你解决将二叉树转为有序的双向链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1082855.html

来源：【匿名】