本文继续讲一些关于二叉树的操作 首先是删除:
int Delete (BTree *tree, int pos, int count) { if (tree == NULL) return FALSE; // 找结点 BTreeNode* parent = NULL; BTreeNode* current = tree->root; int way; while (count > 0 && current != NULL) { way = pos & 1; pos = pos >> 1; parent = current; if (way == BLEFT) current = current->lchild; else current = current->rchild; count --; } if (parent != NULL) { if (way == BLEFT) parent->lchild = NULL; else parent->rchild = NULL; } else { tree->root = NULL; } // 释放结点 r_delete (tree, current); return TRUE; }删除节点,首先也要找到这个节点,这一步与插入节点时 没有多大的区别,但我们要删除这个节点,同时也必须要删除这个节点的“子子孙孙”们,所以我们又要引入递归的思想了,由此可见递归堪称“神通广大”。下面是一个递归的函数:
void r_delete (BTree *tree, BTreeNode* node) { if (node == NULL || tree == NULL) return ; // 先删除左孩子 r_delete (tree, node->lchild); // 删除右孩子 r_delete (tree, node->rchild); free (node); tree->count --; }下面是求二叉树的高度与度:
高度: int r_height (BTreeNode *node) { if (node == NULL) return 0; int lh = r_height (node->lchild); int rh = r_height (node->rchild); return (lh > rh ? lh+1 : rh+1); } int BTree_Height (BTree *tree) { if (tree == NULL) return FALSE; int ret = r_height(tree->root); return ret; } 度: int r_degree (BTreeNode * node) { if (node == NULL) return 0; int degree = 0; if (node->lchild != NULL) degree++; if (node->rchild != NULL) degree++; if (degree == 1) { int ld = r_degree (node->lchild); if (ld == 2) return 2; int rd = r_degree (node->rchild); if (rd == 2) return 2; } return degree; } int BTree_Degree (BTree *tree) { if (tree == NULL) return FALSE; int ret = r_degree(tree->root); return ret; }求高度与度与求树的高度与度基本思想是差不多的,同样也都用到了递归的思想,难度也不是很大,代码也比较好理解。