數據結構之樹，二叉樹，二叉搜索樹

一.樹

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;
}