二叉树的三叉存储

形态：

实现：

/***************************************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 = pTreeNodeTemp; pQueueNodeTemp->pNext = NULL; pQueueTemp->pTail->pNext = pQueueNodeTemp; pQueueTemp->pTail = pQueueNodeTemp; pQueueTemp->nodeCount++; } void DeQueue(pQueue pQueueTemp,ppTreeNode ppTreeNodeTemp) { if(pQueueTemp == NULL) { return; } pQueueNode pDel = pQueueTemp->pHead->pNext; pQueueTemp->pHead->pNext = pDel->pNext; if(pQueueTemp->pTail == pDel) { pQueueTemp->pTail = pQueueTemp->pHead; } *ppTreeNodeTemp = pDel->data; free(pDel); pQueueTemp->nodeCount--; } void DestroyQueue(pQueue pQueueTemp) { if(pQueueTemp == NULL) { return; } pQueueNode pTravel = pQueueTemp->pHead->pNext; while(pTravel != NULL) { pQueueTemp->pHead->pNext = pTravel->pNext; free(pTravel); pTravel = pQueueTemp->pHead->pNext; } free(pQueueTemp->pHead); pQueueTemp->nodeCount = 0; } bool IsQueueEmpty(Queue QueueTemp) { return QueueTemp.nodeCount == 0; } //------二叉树部分------ void CreateNode(ppTreeNode ppTreeNodeTemp) { int a; cin>>a; if(a == -1) { return; } else { *ppTreeNodeTemp = (pTreeNode)malloc(sizeof(TreeNode)); if(*ppTreeNodeTemp == NULL) { return; } (*ppTreeNodeTemp)->pLeft = NULL; (*ppTreeNodeTemp)->pRight = NULL; (*ppTreeNodeTemp)->pParent = NULL; (*ppTreeNodeTemp)->data = a; CreateNode(&(*ppTreeNodeTemp)->pLeft); CreateNode(&(*ppTreeNodeTemp)->pRight); } } void CreateTree(ppTreeNode ppTreeNodeTemp) { if(*ppTreeNodeTemp == NULL) { return; } Queue queue; CreateNode(ppTreeNodeTemp); InitQueue(&queue); EnQueue(&queue,*ppTreeNodeTemp); (*ppTreeNodeTemp)->pParent = NULL; pTreeNode pTreeNodeNew; while(!IsQueueEmpty(queue)) { DeQueue(&queue,&pTreeNodeNew); if(pTreeNodeNew->pLeft != NULL) { pTreeNodeNew->pLeft->pParent = pTreeNodeNew; EnQueue(&queue,pTreeNodeNew->pLeft); } if(pTreeNodeNew->pRight != NULL) { pTreeNodeNew->pRight->pParent = pTreeNodeNew; EnQueue(&queue,pTreeNodeNew->pRight); } } DestroyQueue(&queue); } void PreTravel(pTreeNode pTreeNodeTemp) { if(pTreeNodeTemp == NULL) { return; } cout<<pTreeNodeTemp->data<<" "; 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 == e) { *ppTreeNodeTemp = pTreeNodeTemp; } else { if(pTreeNodeTemp->pLeft) { FindNode(pTreeNodeTemp->pLeft,e,ppTreeNodeTemp); } if(pTreeNodeTemp->pRight) { FindNode(pTreeNodeTemp->pRight,e,ppTreeNodeTemp); } } } pTreeNode Point(pTreeNode pTreeNodeTemp,ElemType e) { Queue queue; InitQueue(&queue); EnQueue(&queue,pTreeNodeTemp); pTreeNode pTreeNodeRet; while(!IsQueueEmpty(queue)) { DeQueue(&queue,&pTreeNodeRet); if(pTreeNodeRet->data == e) { return pTreeNodeRet; } else { if(pTreeNodeRet->pLeft) { EnQueue(&queue,pTreeNodeRet->pLeft); } if(pTreeNodeRet->pRight) { EnQueue(&queue,pTreeNodeRet->pRight); } } } DestroyQueue(&queue); return NULL; } ElemType GetParent(pTreeNode pTreeNodeTemp,ElemType e) { if(pTreeNodeTemp == NULL) { return -1; } pTreeNode p = Point(pTreeNodeTemp,e); if(p && p != pTreeNodeTemp)//p存在且非根节点 { return p->pParent->data; } else { return -1; } } ElemType GetLeftChild(pTreeNode pTreeNodeTemp,ElemType e) { if(pTreeNodeTemp == NULL) { return -1; } pTreeNode p = Point(pTreeNodeTemp,e); if(p && p->pLeft) { return p->pLeft->data; } else { return -1; } } ElemType GetRightChild(pTreeNode pTreeNodeTemp,ElemType e) { if(pTreeNodeTemp == NULL) { return -1; } pTreeNode p = Point(pTreeNodeTemp,e); if(p && p->pRight) { return p->pRight->data; } else { return -1; } } ElemType GetLeftSibling(pTreeNode pTreeNodeTemp,ElemType e) { if(pTreeNodeTemp == NULL) { return -1; } pTreeNode p = Point(pTreeNodeTemp,e); if(p && p!=pTreeNodeTemp && p->pParent && p->pParent->pLeft && p->pParent->pLeft!= p) { return p->pParent->pLeft->data; } return -1; } ElemType GetRightSibling(pTreeNode pTreeNodeTemp,ElemType e) { if(pTreeNodeTemp == NULL) { return -1; } pTreeNode p = Point(pTreeNodeTemp,e); if(p && p!= pTreeNodeTemp && p->pParent && p->pParent->pRight && p->pParent->pRight!=p) { return p->pParent->pRight->data; } return -1; }