转自: http://blog.csdn.net/cnnumen/article/details/5727328
#include <cstdlib> #include <iostream> using namespace std; typedef struct _NODE { int value; struct _NODE *left; struct _NODE *right; _NODE(int value) : value(value), left(NULL), right(NULL) {}; }NODE, *PTRNODE; void insert(PTRNODE &root, int value) { if(root == NULL) root = new NODE(value); else { if(value < root->value) insert(root->left, value); else if(value > root->value) insert(root->right, value); else cout << "duplicated value" << endl; } } void clear(PTRNODE &root) { if(root != NULL) { clear(root->left); clear(root->right); delete root; root = NULL; } } void _search(PTRNODE root, int searchVal) { if(root == NULL) { cout << "not find... " << endl; return; } if(searchVal < root->value) _search(root->left, searchVal); else if(searchVal > root->value) _search(root->right, searchVal); else cout << "find... " << endl; } int main(int argc, char *argv[]) { PTRNODE root = NULL; cout << "init is: " << endl; for(int i=0; i<10; i++) { int value = rand() % 100; cout << value << " "; insert(root, value); } cout << endl; cout << "pre order result is: " << endl; preOrder(root); cout << endl; cout << "in order result is: " << endl; inOrder(root); cout << endl; cout << "post order result is: " << endl; postOrder(root); cout << endl; cout << "please input a search value: "; int searchVal; cin >> searchVal; _search(root, searchVal); clear(root); system("PAUSE"); return EXIT_SUCCESS; }
计算二叉树节点数量和高度的实现如下:
int getSize(PTRNODE root) { if(root == NULL) return 0; return 1 + getSize(root->left) + getSize(root->right); } int getHeight(PTRNODE root) { if(root == NULL) return -1; return 1 + max(getHeight(root->left), getHeight(root->right)); }
二叉树的拷贝和比较实现如下:
PTRNODE copy(const PTRNODE root) { if(root == NULL) return NULL; PTRNODE temp = new NODE(0); temp->value = root->value; temp->left = copy(root->left); temp->right = copy(root->right); return temp; } bool isEqual(const PTRNODE tree1, const PTRNODE tree2) { if(tree1 == NULL && tree2 == NULL) return true; if(tree1 != NULL && tree2 != NULL && tree1->value == tree2->value && isEqual(tree1->left, tree2->left) && isEqual(tree1->right, tree2->right)) return true; return false; }
相关推荐
1.二叉搜索树的建立 2.二叉搜索树节点的查找 3.二叉搜索树节点的删除 4.二叉搜索树的中序、后序递归遍历 5.二叉搜索树的中序、后序非递归遍历 6.二叉搜索树查找某个节点的前驱(下一个值比当前节点x大的节点)
1.实现二叉搜索树的基本操作 2.包括建立,查找,删除,显示 3.得到最长路径和最短路径,并能分别计算长度
有关二叉搜索树的概念以及二叉树中常用的一些基本的操作:删除 增加 查找
二叉查找树的实现。包括树的平衡以及树节点的删除。以及树的广度优先遍历,深度优先遍历。
大连理工大学数据结构上机 二叉树三种遍历,先序和中序建立二叉树,后序和中序建立二叉树,二叉搜索树查找,删除,插入
本源代码通过用户两种选择:冒泡排序或快速排序,然后建立二叉排序树,进行二叉查找、删除、插入等操作。
而在二叉排序树上进行查找时的平均查找长度和二叉树的形态有关: ①在最坏情况下,二叉排序树是通过把一个有序表的n个结点依次插入而生成的,此时所得的二叉排序树蜕化为棵深度为n的单支树,它的平均查找长度和...
用上面的数据,建立二叉搜索树,查找Key=15000的节点,输出查找花费时间。 4). 重复3-5次3)中操作,求各自平均时间。 5). 在1)-4)的红黑树算法基础上修改完成P307 14.1-4算法 OS_Key_Rank(T,k). 输入 1,2,3,4,...
随机产生300,000个不同自然数Key值(1-300,000),建立二叉搜索树,查找Key=15000的节点,输出查找花费时间。 4). 重复3-5次3)中操作,求各自平均时间。 5). 在1)-4)的红黑树算法基础上修改完成P307 14.1-4...
随机产生300,000个不同自然数Key值(1-300,000),建立二叉搜索树,查找Key=15000的节点,输出查找花费时间。 4). 重复3-5次3)中操作,求各自平均时间。 5). 在1)-4)的红黑树算法基础上修改完成P307 14.1-4...
用上面的数据,建立二叉搜索树,查找Key=15000的节点,输出查找花费时间。 4). 重复3-5次3)中操作,求各自平均时间。 5). 在1)-4)的红黑树算法基础上修改完成P307 14.1-4算法 OS_Key_Rank(T,k). 输入 1,2,3,...
二叉排序树.txt 二叉树.txt 二叉树实例.txt 二进制数.txt 二进制数2.txt 余弦曲线.txt 余弦直线.txt 傻瓜递归.txt 冒泡排序.txt 冒泡法改进.txt 动态计算网络最长最短路线.txt 十五人排序.txt 单循环...
二叉排序树.txt 二叉树.txt 二叉树实例.txt 二进制数.txt 二进制数2.txt 余弦曲线.txt 余弦直线.txt 傻瓜递归.txt 冒泡排序.txt 冒泡法改进.txt 动态计算网络最长最短路线.txt 十五人排序.txt 单循环...
二叉排序树.c 二叉树实例.c 单链表 双链表正排序.c 各种排序法.c 哈夫曼算法.c 哈慢树.c 大整数.c 建树和遍历.c 排序法.c 推箱子.c 数据结构2.c 数据结构3.c 数据结构.c 无向图.c 栈操作.c 线性顺序存储结构.c 线索...
用上面的数据,建立二叉搜索树,查找Key=15000的节点,输出查找花费时间。 4). 重复3-5次3)中操作,求各自平均时间。 5). 在1)-4)的红黑树算法基础上修改完成P307 14.1-4算法 OS_Key_Rank(T,k). 输入 1,2,3,4,5...
2019/12/16 20:10 1,955 查找表.cpp 2019/11/25 21:17 2,442 树.cpp 2019/09/10 21:44 641 立方体.cpp 2019/10/24 18:28 3,455 算术表达式求值.cpp 2019/12/09 21:30 1,406 邻接矩阵.cpp 2019/10/27 14:38 1,...
\数据结构flash演示\版本1\9-3-3二叉排序树建立.swf \数据结构flash演示\版本1\9-3-4二叉排序树删除.swf \数据结构flash演示\版本1\9-3-5二叉排序树删除.swf \数据结构flash演示\版本1\9-3-6二叉排序树删除.swf ...
AVL 树(二叉平衡搜索树)、Patricia Trie(前缀树)、散列表等, 任选一种方法实现字典的操作, 查找单词、 插入单词(插入时,先查找此,找不到插入,找到提示用户)、 删除单词(删除时,先查找,找到删除,找不...
3) 为提高管理效率,尝试设计较好的面向应用的查找存储结构,如二叉排序树。 2.实验任务: 设计一个学生档案管理信息系统,管理的学生信息包括学号、姓名、性别、高数成绩、英语成绩、大学物理成绩;要求可对学生...