干货8：二叉树

#ifndef __BTREE_H__ #define __BTREE_H__ #define BLEFT 0 // 表示插入二叉树的左边 #define BRIGHT 1 // 表示插入二叉树的右边 #define TRUE 1 #define FALSE 0 typedef char BTreeData; // 二叉树的结点 typedef struct _btreeNode { BTreeData data; struct _btreeNode *lchild; // 指向左孩子结点的指针 struct _btreeNode *rchild; // 指向右孩子结点的指针 }BTreeNode; // 二叉树 typedef struct _btree { BTreeNode *root; // 指向二叉树的根节点 int count; // 记录二叉树结点的个数 }BTree; typedef void (*Print_BTree)(BTreeNode*); // 创建一棵二叉树 BTree *Create_BTree(); // pos 走的路径 值类似 110（左右右） 011 （右右左） // count 代表走的步数 // flag 代表被替换的结点应该插入在新节点的位置，如果是BLEFT 表示插在左边，BRIGHT表示插在右边 int Btree_Insert(BTree *tree, BTreeData data, int pos, int count, int flag); void Display (BTree* tree, Print_BTree pfunc); int Delete (BTree *tree, int pos, int count); int BTree_Height (BTree *); int BTree_Degree (BTree *); int BTree_Clear (BTree *); int BTree_Destroy (BTree **); // 前序遍历 void pre_order (BTreeNode *node); void mid_order (BTreeNode *node); void last_order (BTreeNode *node); #endif // __BTREE_H__

#include "BTree.h" #include <stdlib.h> #include <stdio.h> BTree *Create_BTree() { BTree *btree = (BTree*)malloc(sizeof(BTree)/sizeof(char)); if (btree == NULL) return NULL; btree->count = 0; btree->root = NULL; return btree; } int Btree_Insert(BTree *tree, BTreeData data, int pos, int count, int flag) { if (tree == NULL || (flag != BLEFT && flag != BRIGHT)) return FALSE; BTreeNode *node = (BTreeNode*)malloc(sizeof(BTreeNode)/sizeof(char)); if (node == NULL) return FALSE; node->data = data; node->lchild = NULL; node->rchild = NULL; // 找插入的位置 BTreeNode *parent = NULL; BTreeNode *current = tree->root; // current 一开始指向根节点，根节点的父节点是空 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 (flag == BLEFT) node->lchild = current; else node->rchild = current; // 把新节点插入到二叉树中,way保存了应该插入在父节点的左边还是右边 if (parent != NULL) { if (way == BLEFT) parent->lchild = node; else parent->rchild = node; } else { tree->root = node; // 替换根节点 } tree->count ++; return TRUE; } void r_display(BTreeNode* node, Print_BTree pfunc,int gap) { int i; if (node == NULL) { for (i = 0; i < gap; i++) { printf ("-"); } printf ("\n"); return; } for (i = 0; i < gap; i++) { printf ("-"); } // 打印结点 // printf ("%c\n", node->data); pfunc (node); if (node->lchild != NULL || node->rchild != NULL) { // 打印左孩子 r_display (node->lchild, pfunc, gap+4); // 打印右孩子 r_display (node->rchild, pfunc, gap+4); } } void Display (BTree* tree, Print_BTree pfunc) { if (tree == NULL) return; r_display(tree->root, pfunc, 0); } 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 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; } 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; } int BTree_Clear (BTree *tree) { if (tree == NULL) return FALSE; Delete (tree, 0, 0); // 删除根节点 tree->root = NULL; return TRUE; } int BTree_Destroy (BTree **tree) { if (tree == NULL) return FALSE; BTree_Clear(*tree); free (*tree); *tree = NULL; return TRUE; } void pre_order (BTreeNode *node) { if (node == NULL) return; printf ("L", node->data); pre_order (node->lchild); pre_order (node->rchild); } void mid_order (BTreeNode *node) { if (node == NULL) return; mid_order (node->lchild); printf ("L", node->data); mid_order (node->rchild); } void last_order (BTreeNode *node) { if (node == NULL) return; last_order (node->lchild); last_order (node->rchild); printf ("L", node->data); }