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

二叉树的三叉存储

形态:


实现:

/***************************************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;>