二叉排序树 r囧r小猫 2022-06-16 08:58 164阅读 0赞 二叉排序树(Binary Sort Tree)性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; #include <stdio.h> #include <stdlib.h> typedef struct BinSortTree{ struct BinSortTree *lChild; struct BinSortTree *rChild; int num; }BinSortTree; //节点 void CreateBinSortTree(BinSortTree **Node,int Num); void InitNode(BinSortTree **Node); void PreOrderTraverse(BinSortTree *Node); void InOrderTraverse(BinSortTree *Node); void leaf_sum(BinSortTree *Node,int *Sum); int BinaryTreeHeight(BinSortTree *Node); int main() { int a[10] = {49,29,9,18,28,5,7,55,80,100}; //for debuging BinSortTree *root = NULL; //根节点 InitNode(&root); //初始化根节点 for(int i = 0; i < 10;++i) { CreateBinSortTree(&root,a[i]); //创建二叉树 } InOrderTraverse(root); //中序遍历二叉树 int leafNum = 0; //叶子节点 leaf_sum(root,&leafNum); //后序遍历二叉树找所有叶子节点 printf("\nleaf Numbers : %d\n",leafNum); int Height = 0; Height = BinaryTreeHeight(root); printf("Height of Tree : %d",Height); return 0; } void InitNode(BinSortTree **Node) //初始化一个节点 { *Node = (BinSortTree *)calloc(1,sizeof(BinSortTree)); if(!*Node) { printf("Error\n"); return ; } (*Node)->lChild = NULL; (*Node)->num = -1; (*Node)->rChild = NULL; } void CreateBinSortTree(BinSortTree **Node,int Num) //创建排序二叉树 { BinSortTree *p_Temp = *Node; if((*Node)->num == -1) { (*Node)->num = Num; return ; } while(p_Temp) { if(p_Temp->num >= Num) //插入的元素小于节点,插入在子树 { if(!p_Temp->lChild) //遍历到要插入的左子树的最后一个空节点 { InitNode(&p_Temp->lChild); p_Temp->lChild->num = Num; return ; } else { p_Temp = p_Temp->lChild;//不断遍历 continue; } } else //插入的元素大于节点,插入右子树 { if(!p_Temp->rChild) { InitNode(&p_Temp->rChild); p_Temp->rChild->num = Num; return ; } else { p_Temp = p_Temp->rChild; continue; } } } return ; } void PreOrderTraverse(BinSortTree *Node) //先序遍历二叉树 { if(!Node) { return ; } printf("%d ",Node->num); PreOrderTraverse(Node->lChild); PreOrderTraverse(Node->rChild); return; } void InOrderTraverse(BinSortTree *Node) //中序遍历二叉树 { if(!Node) { return ; } InOrderTraverse(Node->lChild); printf("%d ",Node->num); InOrderTraverse(Node->rChild); } void leaf_sum(BinSortTree *Node,int *Sum) //遍历二叉树找到叶子节点 { if(!Node) { return ; } if(!Node->lChild && !Node->rChild) //先序遍历二叉树来查找叶子节点 { (*Sum)++; } leaf_sum(Node->lChild,Sum); leaf_sum(Node->rChild,Sum); return ; } int BinaryTreeHeight(BinSortTree *Node) //遍历二叉树得到高度 { if(!Node) { return -1; } static int lHeight = 0; static int rHeight = 0; lHeight = BinaryTreeHeight(Node->lChild); rHeight = BinaryTreeHeight(Node->rChild); return (lHeight) > (rHeight) ? (lHeight + 1) :(rHeight + 1); } ## 博主新地址:[http://www.firefoxbug.net][http_www.firefoxbug.net] ## [http_www.firefoxbug.net]: http://www.firefoxbug.net/
相关 二叉树和排序二叉树 二叉树 > 相关名词 > > 根节点 > > 左叶子节点 > > 右叶子节点 > > 子树 > > 高度 > 二叉树的排序方式: > > - 广度遍历( 灰太狼/ 2023年08月17日 16:53/ 0 赞/ 91 阅读
相关 二叉排序树 \define FALSE 0 \define TRUE 1 \define ElemType int \define Status int \define EQ(a, 你的名字/ 2022年08月25日 05:29/ 0 赞/ 151 阅读
相关 二叉排序树 Problem Description 二叉排序树的定义是:或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它 偏执的太偏执、/ 2022年07月12日 07:48/ 0 赞/ 137 阅读
相关 二叉排序树 Problem Description 二叉排序树的定义是:或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 怼烎@/ 2022年07月12日 03:54/ 0 赞/ 140 阅读
相关 二叉排序树 二叉排序树(Binary Sort Tree)性质: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的 r囧r小猫/ 2022年06月16日 08:58/ 0 赞/ 165 阅读
相关 二叉排序树 题目描述 输入一系列整数,建立二叉排序数,并进行前序,中序,后序遍历。 输入 输入第一行包括一个整数n(1<=n<=100)。 接下来的一行包 痛定思痛。/ 2022年05月31日 01:58/ 0 赞/ 138 阅读
相关 二叉树-详解二叉排序树 二叉搜索树 首先二叉排序树也是一棵二叉树,所谓二叉树,就是“任何节点最多只允许两个子节点”,这两个子节点称为左右子节点。如下便是一个二叉树。 ![这里写图片描述][2 旧城等待,/ 2022年05月17日 01:18/ 0 赞/ 283 阅读
相关 二叉排序树 include<iostream> using namespace std; struct BiTree { in 拼搏现实的明天。/ 2022年05月14日 23:12/ 0 赞/ 198 阅读
相关 二叉排序树 二叉排序树BST,又叫二叉搜索树 或者是一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空 川长思鸟来/ 2022年02月24日 07:48/ 0 赞/ 209 阅读
还没有评论,来说两句吧...