文章目录

一、排序二叉树性质二、代码实例三、测试结果    

一、排序二叉树性质

就是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于其根节点的值。换句话说就是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。

 

二、代码实例

tree.h

#ifndef __TREE_H_ #define __TREE_H_ typedef int ElemType; typedef struct _treeNode { ElemType value; struct _treeNode *parent; struct _treeNode *lChild; struct _treeNode *rChild; }treeNode_s, *treeNode_p; int createTreeNode(treeNode_s **bTree, ElemType value); treeNode_p findTreeNode(treeNode_p bTree, ElemType value); int insertTreeNode(treeNode_s **bTree, ElemType value); int deleteTreeNode(treeNode_s **bTree, ElemType value); int countTreeNode(treeNode_p bTree); int printfTree(treeNode_p bTree); #endif

tree.c

#include <stdio.h> #include <stdlib.h> #include <string.h> #include "tree.h" /*创建节点*/ int createTreeNode(treeNode_s **bTree, ElemType value) { *bTree = (treeNode_s *)malloc(sizeof(treeNode_s)); if (!bTree) { perror("malloc error"); return -1; } memset(*bTree, 0, sizeof(treeNode_s)); (*bTree)->value = value; return 0; } /*查找节点*/ treeNode_p findTreeNode(treeNode_p bTree, ElemType value) { if (!bTree) return NULL; if (bTree->value == value) return bTree; else if (bTree->value > value) return findTreeNode(bTree->lChild, value); else return findTreeNode(bTree->rChild, value); } /*插入节点*/ int insertTreeNode(treeNode_s **bTree, ElemType value) { treeNode_p node = NULL; if (!*bTree) { createTreeNode(&node, value); if (!node) return -1; *bTree = node; } else { /*允许重复*/ if ((*bTree)->value >= value) insertTreeNode(&((*bTree)->lChild), value); else insertTreeNode(&((*bTree)->rChild), value); } return 0; } /*删除节点，分为四种情况*/ int deleteTreeNode(treeNode_s **bTree, ElemType value) { treeNode_p pnode = *bTree, r, p; if (!bTree) return -1; if (pnode->value > value) deleteTreeNode(&(pnode->lChild), value); else if (pnode->value < value) deleteTreeNode(&(pnode->rChild), value); else { /*被删节点没有左右子节点*/ if (!(pnode->lChild) && !(pnode->rChild)) *bTree = NULL; /*被删节点没有左子节点*/ else if (!(pnode->lChild) && pnode->rChild) *bTree = pnode->rChild; /*被删节点没有右子节点*/ else if (!(pnode->rChild) && pnode->lChild) *bTree = pnode->lChild; /*被删节点有左右子节点*/ else { r = pnode->rChild; if (!(r->lChild)) { r->lChild = pnode->lChild; } else { while(r->lChild) { p = r; r = r->lChild; } p->lChild = r->rChild; r->lChild = pnode->lChild; r->rChild = pnode->rChild; } *bTree = r; } free(pnode); } return 0; } /*返回当前节点数量*/ int countTreeNode(treeNode_p bTree) { if (!bTree) return 0; return 1 + countTreeNode(bTree->lChild) + countTreeNode(bTree->rChild); } /*打印数据*/ int printfTree(treeNode_p bTree) { if (bTree) { printfTree(bTree->lChild); printf("%d\t", bTree->value); printfTree(bTree->rChild); } return 0; } void freeTree(treeNode_p bTree) { if (bTree) { free(bTree->lChild); free(bTree->rChild); free(bTree); } } #if 1 /*test*/ int main() { int i; treeNode_p tree = NULL; treeNode_p node = NULL; printf("插入10以内偶数:\n"); for(i = 0; i < 10 ; i += 2) insertTreeNode(&tree, i); printfTree(tree); printf("\n"); printf("插入10以内奇数:\n"); for(i = 1; i < 10 ; i += 2) insertTreeNode(&tree, i); printfTree(tree); printf("\n"); printf("当前总数量: \n"); printf("current count: %d\n", countTreeNode(tree)); printf("查找数值8: \n"); node = findTreeNode(tree, 8); printf("find value: %d\n", node->value); printf("\n删除0:\t"); deleteTreeNode(&tree, 0); printfTree(tree); insertTreeNode(&tree, 0); printf("\n删除1:\t"); deleteTreeNode(&tree, 1); printfTree(tree); insertTreeNode(&tree, 1); printf("\n删除2:\t"); deleteTreeNode(&tree, 2); printfTree(tree); insertTreeNode(&tree, 2); printf("\n删除3:\t"); deleteTreeNode(&tree, 3); printfTree(tree); insertTreeNode(&tree, 3); printf("\n删除4:\t"); deleteTreeNode(&tree, 4); printfTree(tree); insertTreeNode(&tree, 4); printf("\n删除5:\t"); deleteTreeNode(&tree, 5); printfTree(tree); insertTreeNode(&tree, 5); printf("\n删除6:\t"); deleteTreeNode(&tree, 6); printfTree(tree); printf("\n"); insertTreeNode(&tree, 6); freeTree(tree); return 0; } #endif

 

三、测试结果

              关注公众号"小败日记"，搬砖过程遇到的问题，大家一起探讨，资源共享