首页 > 代码库 > 二叉树的三叉存储
二叉树的三叉存储
形态:
实现:
/***************************************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)>
二叉树的三叉存储
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。