本文共 4458 字，大约阅读时间需要 14 分钟。
对下面代码的说明：
该代码的二叉树节点中含有三个指针，分别指向左儿子、右儿子、和父亲。函数接口包括，节点的插入函数，查找函数，树的前序遍历函数和广度优先遍历函数，二叉树节点的左旋和右旋函数。广度优先遍历利用了辅助队列，开辟在堆空间，因此还存在一个队列节点的删除函数。#define _CRT_SECURE_NO_WARNINGS#include#include typedef struct treenode{ int val; struct treenode* pparent; struct treenode* plchild; struct treenode* prchild;}treeNode_t, *pTreeNode_t;typedef struct quene{ pTreeNode_t InsertPos; struct quene* next;}Quene_t, * pQuene_t;void Insert_Node(pTreeNode_t* ppbstnode, int value); void PreOrder(pTreeNode_t pbstnode); pTreeNode_t Find_Node(pTreeNode_t pbstnode, int value);void rbtree_left_rotate(pTreeNode_t* ppbstnode, pTreeNode_t x);void rbtree_right_rotate(pTreeNode_t* ppbstnode, pTreeNode_t x);void BFS(pTreeNode_t pbstnode, pQuene_t* quehead, pQuene_t* quetail);void ClearQuene(pQuene_t* head);int main(){ int num; int value; pTreeNode_t ptr; pTreeNode_t proot = NULL; pQuene_t queHead = NULL, queTail = NULL; //50 40 60 35 45 55 65 测试数据 while (scanf("%d", &num) != EOF) { Insert_Node(&proot, num); } PreOrder(proot); printf("\n"); BFS(proot, &queHead, &queTail); ClearQuene(&queHead); queHead = NULL; queTail = NULL; printf("\nwant to find value:\n"); scanf("%d", &value); ptr = Find_Node(proot,value); printf("it is %d\n", ptr->val); rbtree_left_rotate(&proot, ptr); BFS(proot, &queHead, &queTail); printf("\n"); ClearQuene(&queHead); queHead = NULL; queTail = NULL; ptr = Find_Node(proot, 65); rbtree_right_rotate(&proot, ptr); BFS(proot, &queHead, &queTail); printf("\n"); ClearQuene(&queHead); return 0;}void Insert_Node(pTreeNode_t* ppbstnode, int value){ pTreeNode_t p = *ppbstnode; pTreeNode_t pnew = (pTreeNode_t)malloc(sizeof(treeNode_t)); pnew->val = value; pnew->plchild = NULL; pnew->prchild = NULL; pnew->pparent = NULL; if (*ppbstnode == NULL) { *ppbstnode = pnew; } else { while (p) { if (pnew->val < p->val) { if (p->plchild == NULL) { pnew->pparent = p; p->plchild = pnew; return; } p = p->plchild; } else { if (p->prchild == NULL) { pnew->pparent = p; p->prchild = pnew; return; } p = p->prchild; } } } return;}void PreOrder(pTreeNode_t pbstnode){ if (pbstnode) { printf("%d ", pbstnode->val); PreOrder(pbstnode->plchild); PreOrder(pbstnode->prchild); }}void rbtree_left_rotate(pTreeNode_t* ppbstnode, pTreeNode_t x){ pTreeNode_t y = x->prchild; x->prchild = y->plchild; if (y->plchild != NULL) { y->plchild->pparent = x; } y->pparent = x->pparent; if (x->pparent == NULL) { *ppbstnode = y; } else { if (x->pparent->plchild == x) { x->pparent->plchild = y; } else { x->pparent->prchild = y; } } y->plchild = x; x->pparent = y;}void rbtree_right_rotate(pTreeNode_t* ppbstnode, pTreeNode_t x){ pTreeNode_t y = x->plchild; x->plchild = y->prchild; if (y->prchild != NULL) { y->prchild->pparent = x; } y->pparent = x->pparent; if (x->pparent == NULL) { *ppbstnode = y; } else { if (x->pparent->plchild == x) { x->pparent->plchild = y; } else { x->pparent->prchild = y; } } y->prchild = x; x->pparent = y;}pTreeNode_t Find_Node(pTreeNode_t pbstnode, int value){ while (pbstnode) { if (value == pbstnode->val) { return pbstnode; } else if (value < pbstnode->val) { pbstnode = pbstnode->plchild; } else if (value > pbstnode->val) { pbstnode = pbstnode->prchild; } else { printf("Not Find this value.\n"); return NULL; } }}void BFS(pTreeNode_t pbstnode, pQuene_t* quehead, pQuene_t* quetail){ //pQuene_t head = *quehead; //pQuene_t tail = *quetail; pQuene_t quenew = (pQuene_t)calloc(1, sizeof(Quene_t)); if (NULL == *quehead) { *quehead = quenew; *quetail = quenew; } pQuene_t head = *quehead; pQuene_t tail = *quetail; head->InsertPos = pbstnode; while (head) { printf("%d ", head->InsertPos->val); if (head->InsertPos->plchild) { pQuene_t quenew_left = (pQuene_t)calloc(1, sizeof(Quene_t)); quenew_left->InsertPos = head->InsertPos->plchild; tail->next = quenew_left; tail = quenew_left; } if (head->InsertPos->prchild) { pQuene_t quenew_right = (pQuene_t)calloc(1, sizeof(Quene_t)); quenew_right->InsertPos = head->InsertPos->prchild; tail->next = quenew_right; tail = quenew_right; } head = head->next; }}void ClearQuene(pQuene_t* head){ pQuene_t ptr; while (*head) { ptr = (*head)->next; free(*head); *head = ptr; }}
转载地址：http://xxxmb.baihongyu.com/