1些概念:
1棵树是1些结点的集合。这个集合可以是空集,若不是空集,则树由称作根(root)的结点r和零个或多个非空的(子)树T1,T2...Ta组成,子树中每个棵的根都被来自根r的1条有向的边(edge)所连接。
每棵子树的根叫做根r的儿子(child),而r是每棵子树的根的父亲(parent)。
没有儿子的结点成为叶(leaf)结点。
具有相同父亲的结点为兄弟(siblings)结点。
对任意结点n,n的深度(depth)为从根到n的唯1路径的长。因此根的深度为0.
n的高度是从n到1片树叶的最长路径的长。因此所有的树叶的高度都是0.
1棵树的高等于它的根的高。
1棵树的深度等于它最深的树叶的深度。等于根的高度。
前序遍历:对结点的处理工作是在它的诸儿子结点被处理之前进行的。
后序遍历:对结点的处理工作是在它的诸儿子结点被处理以后进行的。
内部路径长(internal path length)1棵树所有结点的深度总和。
//普通的树结点 template <typename Object> struct TreeNode { Object element;//结点的数据 TreeNode* firstChild;//第1个儿子的指针 TreeNode* nexSibling;//当前结点的兄弟结点的指针 };
2叉树:每一个结点最多有两个儿子的树。
每一个2叉树,具有N个结点,N+1个NULL结点
//2叉树结点 template<typename Object> struct BinaryNode { Object element;//结点的数据 BinaryNode* left;//左结点 BinaryNode* right;//右结点 };
// // Vector.h // HelloWorld // csdn blog:http://blog.csdn.net/u012175089 // Created by Fable on 17/1/7. // Copyright (c) 2017年 Fable. All rights reserved. // #ifndef __HelloWorld__Tree__ #define __HelloWorld__Tree__ #include <iostream> namespace Fable { //2叉查找树,对Comparable,必须实现了><=的比较 template<typename Comparable> class BinarySearchTree { public: //构造函数 BinarySearchTree(){} //复制构造函数 BinarySearchTree(const BinarySearchTree& rhs) { root = clone(rhs.root); } //析构函数 ~BinarySearchTree() { makeEmpty(root); } //复制赋值运算符 const BinarySearchTree& operator=(const BinarySearchTree& rhs) { if (this != &rhs) { makeEmpty(root);//先清除 root = clone(rhs.root);//再复制 } return *this; } //查找最小的对象 const Comparable& findMin()const { findMin(root); } //查找最大的对象 const Comparable& findMax()const { findMax(root); } //是不是包括了某个对象 bool contains(const Comparable& x)const { return contains(x, root); } //树为空 bool isEmpty()const { return root == nullptr; } //打印整棵树 void printTree()const { printTree(root); } //清空树 void makeEmpty() { makeEmpty(root); } //插入某个对象 void insert(const Comparable& x) { insert(x, root); } //移除某个对象 void remove(const Comparable& x) { remove(x, root); } private: struct BinaryNode { Comparable element; BinaryNode* left; BinaryNode* right; BinaryNode(const Comparable& theElement, BinaryNode* lt, BinaryNode* rt) :element(theElement), left(lt), right(rt){} }; BinaryNode* root;//根结点 //插入对象,这里使用了援用 void insert(const Comparable& x, BinaryNode*& t)const { if (!t) { t = new BinaryNode(x, nullptr, nullptr); } else if (x < t->element) { insert(x, t->left);//比根结点小,插入左侧 } else if (x > t->element) { insert(x, t->right);//比根结点大,插入右侧 } else { //相同的 } } void removeMin(BinaryNode*& x, BinaryNode*& t)const { if (!t) { return nullptr;//找不到 } if (t->left) { return removeMin(t->left);//使用了递归的方式 } else { //找到最小的结点了 x->element = t->element; BinaryNode* oldNode = t; t = t->right; delete oldNode;//删除原来要删除的结点 return t; } } //删除某个对象,这里必须要援用 void remove(const Comparable& x, BinaryNode*& t)const { if (!t) { return;//树为空 } else if (x < t->element) { remove(x, t->left);//比根结点小,去左侧查找 } else if (x > t->element) { remove(x, t->right);//比根结点大,去右侧查找 } else if (!t->left && !t->right)//找到结点了,有两个叶子 { removeMin(t, t->right); } else { BinaryNode* oldNode = t; t = (t->left) ? t->left : t->right;//走到这里,t最多只有1个叶子,将t指向这个叶子 delete oldNode;//删除原来要删除的结点 } } //左侧子树的结点肯定比当前根小的,所以1直往左侧寻觅 BinaryNode* findMin(BinaryNode* t)const { if (!t) { return nullptr;//找不到 } if (!t->left) { return t; } return findMin(t->left);//使用了递归的方式 } //右侧子树的结点肯定比当前根大,所以1直往右侧找 BinaryNode* findMax(BinaryNode* t)const { if (t) { while (t->right)//使用了循环的方式 { t = t->right; } } return t; } //判断是不是包括某个对象,由于要使用递归,所以还有1个public版本的 bool contains(const Comparable& x, BinaryNode* t)const { if ( !t ) { return false;//空结点了 } else if (x < t->element) { //根据2叉树的定义,比某个结点小的对象,肯定只能存在与这个结点的左侧的子树 return contains(x, t->left); } else if (x > t->element) { //根据2叉树的定义,比某个结点大的对象,肯定只能存在与这个结点的右侧的子树 return contains(x, t->right); } else { //相等,就是找到啦。 return true; } } //清空子树 void makeEmpty(BinaryNode*& t) { if (t) { makeEmpty(t->left);//清空左侧 makeEmpty(t->right);//清空右侧 delete t;//释放本身 } t = nullptr;//置为空 } //打印子树,这里没有使用复杂的排位,纯属打印 void printTree(BinaryNode* t)const { if (!t) { return; } std::cout << t->element << std::endl;//输出本身的对象 printTree(t->left);//打印左子树 printTree(t->right);//打印右子树 } BinaryNode* clone(BinaryNode* t)const { if (!t) { return nullptr; } return new BinaryNode(t->element, clone(t->left), clone(t->right)); } }; } #endif2叉树的所有操作平均运算时间是O(logN)。
但是在极真个情况下,是有可能失衡的,例如常常插入和删除数据,按上面的算法来讲,是会造成左子树的比右子树深。
当极度失衡,就变成1个单向链表了。
有些经过转变的树会斟酌着方面的问题,会做调剂。下1章再说了。
上一篇 桌面软件一般用什么开发
下一篇 深刻理解HDFS工作原理