首页 > 代码库 > 二叉树的三叉存储

二叉树的三叉存储

形态:

技术分享

实现:

/***************************************8
二叉树的三叉链表存储
by Rowandjj
2014/5/23
*****************************************/

#include<iostream>
using namespace std;

typedef int ElemType;    
//-------二叉树的三叉链表存储结构-----------
typedef struct _TREENODE_
{
    struct _TREENODE_ *pParent;//父节点
    struct _TREENODE_ *pLeft;//左孩子
    struct _TREENODE_ *pRight;//右孩子
    
    ElemType data;
}TreeNode,*pTreeNode,**ppTreeNode;
//---------辅助队列-------------------
typedef struct _QUEUENODE_//队列节点
{
    struct _QUEUENODE_ *pNext;
    pTreeNode data;
}QueueNode,*pQueueNode;

typedef struct _QUEUE_//队列存储结构
{
    pQueueNode pHead;
    pQueueNode pTail;

    int nodeCount;
}Queue,*pQueue;

//队列操作定义
void InitQueue(pQueue pQueueTemp);
void EnQueue(pQueue pQueueTemp,pTreeNode pTreeNodeTemp);
void DeQueue(pQueue pQueueTemp,ppTreeNode ppTreeNodeTemp);
void DestroyQueue(pQueue pQueueTemp);
bool IsQueueEmpty(Queue QueueTemp);
//三叉链表树操作定义
void CreateNode(ppTreeNode ppTreeNodeTemp);
void CreateTree(ppTreeNode ppTreeNodeTemp);

void PreTravel(pTreeNode pTreeNodeTemp);
void PostTravel(pTreeNode pTreeNodeTemp);
void LevelTravel(pTreeNode pTreeNodeTemp);
void MidTravel(pTreeNode pTreeNodeTemp);
int GetDepth(pTreeNode pTreeNodeTemp);
void FindNode(pTreeNode pTreeNodeTemp,ElemType e,ppTreeNode ppTreeNodeTemp);
pTreeNode Point(pTreeNode pTreeNodeTemp,ElemType e);
ElemType GetParent(pTreeNode pTreeNodeTemp,ElemType e);
ElemType GetLeftChild(pTreeNode pTreeNodeTemp,ElemType e);
ElemType GetRightChild(pTreeNode pTreeNodeTemp,ElemType e);
ElemType GetLeftSibling(pTreeNode pTreeNodeTemp,ElemType e);
ElemType GetRightSibling(pTreeNode pTreeNodeTemp,ElemType e);
//------------------------------------------

//------队列部分-----------
void InitQueue(pQueue pQueueTemp)
{
    pQueueTemp->pHead = pQueueTemp->pTail = (pQueueNode)malloc(sizeof(QueueNode));
    if(pQueueTemp->pHead == NULL)
    {
        return;
    }
    pQueueTemp->pHead->pNext = NULL;
    pQueueTemp->nodeCount = 0;
}
void EnQueue(pQueue pQueueTemp,pTreeNode pTreeNodeTemp)
{
    if(pQueueTemp == NULL)
    {
        return;
    }
    pQueueNode pQueueNodeTemp = (pQueueNode)malloc(sizeof(QueueNode));
    if(pQueueNodeTemp == NULL)
    {
        return;
    }
    pQueueNodeTemp->data = http://www.mamicode.com/pTreeNodeTemp;" ";
    PreTravel(pTreeNodeTemp->pLeft);
    PreTravel(pTreeNodeTemp->pRight);
}
void PostTravel(pTreeNode pTreeNodeTemp)
{
    if(pTreeNodeTemp == NULL)
    {
        return;
    }
    
    PostTravel(pTreeNodeTemp->pLeft);
    PostTravel(pTreeNodeTemp->pRight);
    cout<<pTreeNodeTemp->data<<" ";
}
void LevelTravel(pTreeNode pTreeNodeTemp)
{
    Queue queue;
    InitQueue(&queue);
    EnQueue(&queue,pTreeNodeTemp);
    
    pTreeNode pTreeNodeNew;
    
    while(!IsQueueEmpty(queue))
    {
        DeQueue(&queue,&pTreeNodeNew);
        if(pTreeNodeNew != NULL)
        {
            cout<<pTreeNodeNew->data<<" ";
        //    if(pTreeNodeNew->pParent != NULL)//打印父节点
        //    {
        //        cout<<"father:"<<pTreeNodeNew->pParent->data<<" ";
        //    }
            if(pTreeNodeNew->pLeft)
            {
                EnQueue(&queue,pTreeNodeNew->pLeft);
            }
            if(pTreeNodeNew->pRight)
            {
                EnQueue(&queue,pTreeNodeNew->pRight);
            }    
        }
    }
    DestroyQueue(&queue);
}
void MidTravel(pTreeNode pTreeNodeTemp)
{
    if(pTreeNodeTemp == NULL)
    {
        return;
    }
    MidTravel(pTreeNodeTemp->pLeft);
    cout<<pTreeNodeTemp->data<<" ";
    MidTravel(pTreeNodeTemp->pRight);
}

int GetDepth(pTreeNode pTreeNodeTemp)
{
    if(pTreeNodeTemp == NULL)
    {
        return 0;
    }
    int i = 0;
    int j = 0;
    if(pTreeNodeTemp->pLeft)
    {
        i = GetDepth(pTreeNodeTemp->pLeft);
    }else
    {
        i = 0;
    }
    if(pTreeNodeTemp->pRight)
    {
        j = GetDepth(pTreeNodeTemp->pRight);
    }else
    {
        j = 0;
    }
    return (i > j) ? i+1 : j+1;
}

void FindNode(pTreeNode pTreeNodeTemp,ElemType e,ppTreeNode ppTreeNodeTemp)
{
    if(pTreeNodeTemp == NULL)
    {
        return;
    }
    if(pTreeNodeTemp->data =http://www.mamicode.com/= e)>

二叉树的三叉存储