数据结构之树，二叉树，二叉搜索树

一.树

1.形状

2. 相关概念

节点的度：一个节点含有的子树的个数称为该节点的度；如上图：A的为6

叶节点或终端节点：度为0的节点称为叶节点；如上图：B、C、H、I...等节点为叶节点

非终端节点或分支节点：度不为0的节点；如上图：D、E、F、G...等节点为分支节点

双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；如上图：A是B的父节点

孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；如上图：B是A的孩子节点

兄弟节点：具有相同父节点的节点互称为兄弟节点；如上图：B、C是兄弟节点

树的度：一棵树中，最大的节点的度称为树的度；如上图：树的度为6

节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

树的高度或深度：树中节点的最大层次；如上图：树的高度为4

堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

森林：由m（m>0）棵互不相交的树的集合称为森林；

3.树的实现

#include <iostream>
using namespace std;//链表
template <typename T>
struct ListNode
{T data;ListNode* next;ListNode(T d):data(d),next(NULL){}
};//树的节点
template<typename T>
struct TreeNode
{T data;ListNode<TreeNode<T>*>* childHead;TreeNode() {data = T();childHead = NULL;}void addChild(TreeNode<T>* node){ListNode<TreeNode<T>*>* childNode = new ListNode<TreeNode<T>*>(node);if (childHead == NULL){childHead = childNode;}else{childNode->next = childHead;childHead = childNode;}}
};//创建树的类
template <typename T>
class Tree{
private:TreeNode<T>* nodes;TreeNode<T>* root;
public:Tree();Tree(int maxNodes);~Tree();TreeNode<T>* getTreeNode(int id);void setRoot(int rootId);void addChild(int parent,int child);void assignData(int NodeId , T data);void print(TreeNode<T>* node = NULL);
};template <typename T>
Tree<T>::Tree(){nodes = new TreeNode<T>[10000];root = NULL;
}template <typename T>
Tree<T>::Tree(int maxNodes){nodes = new TreeNode<T>[maxNodes];root = NULL;
}template <typename T>
Tree<T>::~Tree(){delete[] nodes;
}template <typename T>
TreeNode<T>* Tree<T>::getTreeNode(int id){return &nodes[id];
}template <typename T>
void Tree<T>::setRoot(int rootId){root = getTreeNode(rootId);
}template <typename T>
void Tree<T>::addChild(int parent,int child){TreeNode<T>* Parat = getTreeNode(parent);TreeNode<T>* Child = getTreeNode(child);Parat->addChild(Child);
}template <typename T>
void Tree<T>::assignData(int NodeId , T data){getTreeNode(NodeId)->data = data;
}template <typename T>
void Tree<T>::print(TreeNode<T>* node){if (node == NULL){node = root;}cout<<node->data;ListNode<TreeNode<char>*>* temp = node->childHead;while (temp){print(temp->data);temp = temp->next;}
}int main(){Tree<char> p[9];p->setRoot(0);p->assignData(0,'a');p->assignData(1,'b');p->assignData(2,'c');p->assignData(3,'d');p->assignData(4,'e');p->assignData(5,'f');p->assignData(6,'g');p->assignData(7,'h');p->assignData(8,'i');p->addChild(0,1);p->addChild(0,2);p->addChild(1,3);p->addChild(2,4);p->addChild(2,5);p->addChild(3,6);p->addChild(3,7);p->addChild(3,8);p->print();return 0;
}

二.二叉树

1.形状(最多只有两个度，也就是最多有两个节点)

2.基本概念

1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个结点.

2. 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2^h-1

3. 对任何一棵二叉树, 如果度为0其叶结点个数为y, 度为2的分支结点个数为x,则y=x+1

4. 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1)

3.二叉树的存储方式

1.顺序存储

就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。

2.链式存储

用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。

3.二叉树的遍历

前序遍历

中序

后续
层序遍历

前，中，后序遍历的实现

#include <iostream>
using namespace std;//树的节点
template<typename T>
struct TreeNode 
{T val;TreeNode* left;	//左子树TreeNode* right;//右子树TreeNode():val(0),left(NULL),right(NULL){};	//构造函数TreeNode(T d):val(d),left(NULL),right(NULL){};//构造函数
};//树的类集合
template<typename T>
class Tree{//内置参数
private:TreeNode<T>* nodes;	//树的节点数组	TreeNode<T>* root;	//根节点size_t nodeSize;	//节点个数TreeNode <T>* Creat(T a[],int size,int nodeId,T nullNode);	//创建树void visit(TreeNode<T>* node);	//访问节点void preOrder(TreeNode<T>* node);	//先序遍历void inOrder(TreeNode<T>* node);	//中序遍历void postOrder(TreeNode<T>* node);	//后序遍历//用于外部函数调用
public:Tree();Tree(int maxNodes);	~Tree();	TreeNode<T>* getTreeNode (int Id);	//获取节点void CreatTree(T a[],int size,T nullNode);	//创建树void preOrder();	//先序遍历void inOrder();		//中序遍历void postOrder();	//后序遍历
};//默认构造函数
template<typename T>
Tree<T>::Tree(){nodeSize = 10000;root = NULL;nodes = new TreeNode<T>[nodeSize];
}//带参数的构造函数
template<typename T>
Tree<T>::Tree(int maxNodes){nodeSize = maxNodes;root = NULL;nodes = new TreeNode<T>[nodeSize];
}//析构函数，释放内存
template<typename T>
Tree<T>::~Tree(){delete[] nodes;
}//获取树节点
template<typename T>	
TreeNode<T>* Tree<T>::getTreeNode (int Id){return &nodes[Id];
}//打印节点值
template<typename T>
void Tree<T>::visit(TreeNode<T>* node){cout<<node->val;
}//内部创建树，递归实现
template<typename T>
TreeNode <T>* Tree<T>::Creat(T a[],int size,int nodeId,T nullNode){if (nodeId >= size || a[nodeId] == nullNode){return NULL;}TreeNode <T>* nowNode = getTreeNode (nodeId);nowNode->val = a[nodeId];nowNode->left = Creat(a,size,nodeId * 2,nullNode);nowNode->right = Creat(a,size,nodeId * 2 + 1,nullNode);return nowNode;
}//外部函数创建树
template<typename T>
void  Tree<T>::CreatTree(T a[],int size,T nullNode){root = Creat(a,size,1,nullNode);//根节点从1开始
}//内部实现前序遍历
template<typename T>
void Tree<T>::preOrder(TreeNode<T>* node){if (node){visit(node);preOrder(node->left);preOrder(node->right);}
}//外部实现前序遍历
template<typename T>
void Tree<T>::preOrder(){preOrder(root);
}//内部实现中序遍历
template<typename T>
void Tree<T>::inOrder(TreeNode <T>* node){if (node) {inOrder(node->left);visit(node);inOrder(node->right);}
}//外部实现中序遍历
template<typename T>
void Tree<T>::inOrder(){inOrder(root);
}//内部实现后序遍历
template<typename T>
void Tree<T>::postOrder(TreeNode <T>* node){if (node) {postOrder(node->left);postOrder(node->right);visit(node);}
}//外部实现后序遍历
template<typename T>
void Tree<T>::postOrder(){postOrder(root);
}int main(){const char nullNpde = '-';char a[15] = {nullNpde, 'a', 'b', 'c', 'd',nullNpde, 'e', 'f', 'g', 'h',nullNpde, nullNpde, nullNpde, nullNpde, 'i'};Tree<char> T(15);T.CreatTree(a, 15, nullNpde);T.preOrder(); cout << endl;T.inOrder(); cout << endl;T.postOrder(); cout << endl;return 0;
}

三.二叉搜索树

1.形状

2.概念

3.二叉树代码实现

#include <iostream>
using namespace std;//树的节点
template<typename T>
struct TreeNode
{T data;TreeNode* left;TreeNode* right;TreeNode():data(0),left(NULL),right(NULL){}TreeNode(T d):data(d),left(NULL),right(NULL){}
};template<typename T>
class BinarySearchTree{
private:TreeNode<T>* root;TreeNode<T>* insertNode(TreeNode<T>* node,T value);TreeNode<T>* removeNode(TreeNode<T>* node,T value);bool searchNode(TreeNode<T>* node,T value);void inOrder(TreeNode<T>* node);public:BinarySearchTree():root(NULL){};~BinarySearchTree();void insert(T value){root = insertNode(root,value);}void remove(T value){root = removeNode(root,value);}bool search(T value){return searchNode(root,value);}void inOrderTree(){inOrder(root);cout<<endl;}
};//析构函数，删除所有节点
template<typename T>
BinarySearchTree<T>::~BinarySearchTree(){while (root){remove(root->data);}
}//插入节点
template<typename T>
TreeNode<T>* BinarySearchTree<T>::insertNode(TreeNode<T>* node,T value){if (node == NULL){return new TreeNode<T>(value);}if (value < node->data){node->left = insertNode(node->left,value);//递归调用，直到找到合适的位置}else if(value > node->data){node->right = insertNode(node->right,value);//递归调用，直到找到合适的位置}return node;
}//删除节点
template<typename T>
TreeNode<T>* BinarySearchTree<T>::removeNode(TreeNode<T>* node,T value){if (node == NULL){return NULL;}if (value < node->data)//如果要删除的值小于当前节点的值，则递归调用左子树{node->left = removeNode(node->left,value);}else if(value > node->data)//如果要删除的值大于当前节点的值，则递归调用右子树{node->right = removeNode(node->right,value);}else//如果要删除的值等于当前节点的值{if (node->left == NULL && node->right == NULL)//如果当前节点没有子节点，则直接删除{delete node;node = NULL;return NULL;}else if(node->left == NULL)//如果当前节点没有左子节点，则用右子节点替换当前节点{TreeNode<T>* rightChild = node->right;delete node;node = rightChild;return node;}else if(node->right == NULL)//如果当前节点没有右子节点，则用左子节点替换当前节点{TreeNode<T>* leftChild = node->left;delete node;node = leftChild;return node;}else//如果当前节点有两个子节点，则用右子树中的最小节点替换当前节点{TreeNode<T>* replacement = node->right;while (replacement->left != NULL) {replacement = replacement->left;}node->data = replacement->data;node->right = removeNode(node->right, replacement->data);}}return node;
}//查找节点
template<typename T>
bool BinarySearchTree<T>::searchNode(TreeNode<T>* node,T value){if (node == NULL){return false;}if (value < node->data){return searchNode(node->left,value);}else if(value > node->data){return searchNode(node->right,value);}return true;
}//中序遍历
template<typename T>
void BinarySearchTree<T>::inOrder(TreeNode<T>* node){if (node){inOrder(node->left);cout<<node->data<<",";inOrder(node->right);}	
}int main(){BinarySearchTree<int> bst;bst.insert(10);bst.insert(30);bst.insert(20);bst.insert(40);bst.insert(60);bst.insert(50);cout<<"中序遍历"<<endl;bst.inOrderTree();cout<<"查找20："<<bst.search(20)<<endl;cout<<"查找100："<<bst.search(100)<<endl;bst.remove(30);bst.inOrderTree();return 0;
}