关于树的概念：
a.节点：结点包含数据和指向其它节点的指针。
b.根节点：树第一个结点称为根节点。
c.结点的度：结点拥有的子节点个数。
d.叶节点：没有子节点的节点(度为0)。
e.父子节点：一个节点father指向另一个节点child，则child为孩子节点，father为父亲节点 。
f.兄弟节点：具有相同父节点的节点互为兄弟节点。
g.节点的祖先：从根节点开始到该节点所经的所有节点都可以称为该节点的祖先。
h.子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
i.树的高度：树中距离根节点最远节点的路径长度。
关于二叉树:
二叉树是一棵特殊的树，二叉树每个节点最多有两个孩子结点，分别称为左孩子和右孩子。
满二叉树:高度为N的满二叉树有2^N - 1个节点的二叉树。
完全二叉树: 若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左 边，这就是完全二叉树.（三种遍历）
二叉树的简单实现
#include <iostream> #include <queue> #include<stack> #include <cstdlib> using namespace std; template<class T> struct BinaryTreeNode { BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; T _date; BinaryTreeNode(const T& x) :_date(x) , _left(NULL) , _right(NULL) {} }; template<class T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: BinaryTree() :_root(NULL) { cout << "BinaryTree()" << endl; } BinaryTree(const T* a, size_t size, const T& invalid) { size_t index = 0; _root = _BinaryTree(a, size, index, invalid); cout << "BinaryTree(const T* a, size_t size, const T& invalid)" << endl; } BinaryTree(const BinaryTree<T>& t) { _root = _Copy(t._root); cout << "BinaryTree(const BinaryTree<T>& t)" << endl; } BinaryTree<T>& operator=(const BinaryTree<T>& t) { if (this != &t) { Node* tmp = _Copy(t._root); _root = _Destory(_root); _root = tmp; } return *this; } ~BinaryTree() { _root = _Destory(_root); cout << "~BinaryTree()" << endl; } void PrevOrder()//前序遍历 { _PrevOrder(_root); cout << endl; } void InOrder()//中序遍历 { _InOrder(_root); cout << endl; } void PostOrder()//后序遍历 { _PostOrder(_root); cout << endl; } void LevelOrder()//层遍历 { _LevelOrder(_root); cout << endl; } size_t Size()//求节点个数 { return _Size(_root); } size_t Depth()//求树的深度 { return _Depth(_root); } size_t LeafSize()//求叶子节点个数 { return _LeafSize(_root); } size_t GetKLevel(size_t k)//求第K层叶子节点个数 { return _GetKLevel(_root, k); } protected: Node* _BinaryTree(const T* a, size_t size, size_t& index, const T& invalid) { Node* NewNode = NULL; if (index < size && a[index] != invalid) { NewNode = new Node(a[index]); NewNode->_left = _BinaryTree(a, size, ++index, invalid); NewNode->_right = _BinaryTree(a, size, ++index, invalid); } return NewNode; } Node* _Copy(Node* root) { Node* NewNode = NULL; if (root != NULL) { NewNode = new Node(root->_date); NewNode->_left = _Copy(root->_left); NewNode->_right = _Copy(root->_right); } return NewNode; } Node* _Destory(Node* root) { if (root != NULL) { _Destory(root->_left); _Destory(root->_right); delete root; root = NULL; } return root; } void _PrevOrder(Node* root) { if (root != NULL) { cout << root->_date << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } } void _InOrder(Node* root) { if (root != NULL) { _InOrder(root->_left); cout << root->_date << " "; _InOrder(root->_right); } } void _PostOrder(Node* root) { if (root != NULL) { _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_date << " "; } } void _LevelOrder(Node* root) { queue<Node*> q; q.push(root); while (!q.empty()) { Node* tmp = q.front(); cout << tmp->_date << " "; q.pop(); if (tmp->_left != NULL) { q.push(tmp->_left); } if (tmp->_right != NULL) { q.push(tmp->_right); } } } size_t _Size(Node* root) { size_t size = 0; if (root != NULL) { size += 1; size += _Size(root->_left); size += _Size(root->_right); } return size; } size_t _Depth(Node* root) { if (root == NULL) return 0; int left = _Depth(root->_left); int right = _Depth(root->_right); return left > right ? left + 1 : right + 1; } size_t _LeafSize(Node* root) { size_t size = 0; if (root != NULL) { if (root->_left == NULL && root->_right == NULL) { size += 1; } size += _LeafSize(root->_left); size += _LeafSize(root->_right); } return size; } size_t _GetKLevel(Node* root, size_t k) { if (root == NULL) return 0; if (k == 1) return 1; return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1); } protected: Node* _root; }; void TestBinaryTree() { int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; int a2[15] = { 1, 2, '#', 3, '#', '#', 4, 5, '#', 6, '#', 7, '#', '#', 8 }; BinaryTree<int> b(a, 10, '#'); BinaryTree<int> e(a2, 15, '#'); b.PostOrder(); /*b.PrevOrder(); b.InOrder(); /*e.PrevOrder(); e.InOrder(); /*b.InOrder(); b.PostOrder(); b.LevelOrder(); BinaryTree<int> c(b); c.PrevOrder(); c.InOrder(); c.PostOrder(); c.LevelOrder(); BinaryTree<int> d; d = c; d.PrevOrder(); d.InOrder(); d.PostOrder(); d.LevelOrder(); cout<<"size:"<<b.Size()<<endl;*/ /*BinaryTree<int> e(a2, 15, '#'); e.PrevOrder(); cout <<"b.Depth(): "<< b.Depth() << endl; cout << "e.Depth(): "<<e.Depth() << endl; cout << "b.LeafSize(): "<<b.LeafSize()<<endl; cout << "e.LeafSize(): "<<e.LeafSize()<<endl; cout <<"b.GetKLevel(2): "<< b.GetKLevel(2) << endl; cout <<"e.GetKLevel(4): "<< e.GetKLevel(4) << endl;*/ } int main() { TestBinaryTree(); return 0; }
二叉树的递归实现：（先序创建）
#pragma once #include<cassert> #include<iostream> #include<queue> using namespace std; template<typename T> struct BinaryTreeNode { T _data; BinaryTreeNode *_left; BinaryTreeNode *_right; BinaryTreeNode(const T& data = T()) :_data(data) , _left(NULL) , _right(NULL){} }; template<typename T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: BinaryTree() :_root() {} BinaryTree(const T *array,size_t size,const T& invalid) { size_t index = 0; _root=_CreatTree(array,size,index,invalid); } BinaryTree(const BinaryTree<T>& t) { _root=_Copy(t._root); } BinaryTree& operator=(BinaryTree<T>& t) { if (this != &t) //防止自赋值 { BinaryTree<T> tmp(t); swap(_root,tmp._root); } return *this; } ~BinaryTree() { _destory(_root); } size_t Leaf() //求叶子结点的个数 { return _leaf(_root); } size_t Size() //求结点个数 { return _Size(_root); } size_t Depth() //求深度 { return _Depth(_root); } void PrevOder() //前序遍历 { _PrevPrint(_root); cout << endl; } void InOder() //中序遍历 { _InPrint(_root); cout << endl; } void BackOder() //后序遍历 { _BackPrint(_root); cout << endl; } void TierOder() //层序遍历 { _TierPrint(_root); cout << endl; } protected: Node* _CreatTree(const T *array, size_t size, size_t& index, const T& invalid) { assert(array); Node *root=NULL; if (index < size&&array[index] != invalid) { root = new Node(array[index]); //创建根节点 root->_left = _CreatTree(array,size,++index,invalid); //递归创建左子树 root->_right= _CreatTree(array,size,++index,invalid); //递归创建右子树 } return root; } void _PrevPrint(Node *root) { Node *cur =root; if (cur) { cout << cur->_data << " "; _PrevPrint(cur->_left); _PrevPrint(cur->_right); } } void _InPrint(Node *root) { Node *cur = root; if (cur) { _InPrint(cur->_left); cout << cur->_data << " "; _InPrint(cur->_right); } } void _BackPrint(Node *root) { Node *cur = root; if (cur) { _BackPrint(cur->_left); _BackPrint(cur->_right); cout << cur->_data << " "; } } void _TierPrint(Node *root) { queue<Node*> q; Node* cur=root; q.push(cur); while(!q.empty()) { Node* tmp = q.front(); cout << tmp->_data <<" "; if (tmp->_left) q.push(tmp->_left); if (tmp->_right) q.push(tmp->_right); q.pop(); } } size_t _Size(Node *root) { if (root == NULL) return 0; return 1 + _Size(root->_left) + _Size(root->_right); } size_t _Depth(Node *root) { Node *cur = root; if (NULL == cur) return 0; return 1 + (_Depth(cur->_left) > _Depth(cur->_right) ? _Depth(cur->_left) : _Depth(cur->_right)); } void _destory(Node *root) { Node *cur =root; if (cur) { _destory(cur->_left); _destory(cur->_right); delete cur; cur = NULL; } } Node* _Copy(Node* node) { Node* cur= node; Node* root = NULL; if (cur) { root = new Node(cur->_data); root->_left =_Copy(cur->_left); root->_right=_Copy(cur->_right); } return root; } size_t _leaf(Node* root) { Node* cur = root; if (NULL==cur) return 0; if (cur->_left == NULL&&cur->_right == NULL) //如果左右子树都为空，则返回1 return 1; return _leaf(cur->_left ) + _leaf(cur->_right); } protected: Node *_root; };
小记：
//#pragma once // //template<class K> //struct SearchBinaryTreeNode //{ // SearchBinaryTreeNode<K>* _left; // SearchBinaryTreeNode<K>* _right; // // K _key; // // SearchBinaryTreeNode(const K& key) // :_key(key) // ,_left(NULL) // ,_right(NULL) // {} //}; // //template<class K> //class SearchBinaryTree //{ // typedef SearchBinaryTreeNode<K> Node; //public: // SearchBinaryTree() // :_root(NULL) // {} // // bool Insert(const K& key) // { // if (_root == NULL) // { // _root = new Node(key); // return true; // } // // Node* parent = NULL; // Node* cur = _root; // while (cur) // { // if (cur->_key < key) // { // parent = cur; // cur = cur->_right; // } // else if (cur->_key > key) // { // parent = cur; // cur = cur->_left; // } // else // { // return false; // } // } // // if (parent->_key < key) // { // parent->_right = new Node(key); // return true; // } // else // { // parent->_left = new Node(key); // return true; // } // } // // const Node* Find(const K& key) // { // Node* cur = _root; // while (cur) // { // if (cur->_key < key) // { // cur = cur->_right; // } // else if (cur->_key > key) // { // cur = cur->_left; // } // else // { // return cur; // } // } // // return NULL; // } // // bool Remove(const K& key) // { // Node* parent = NULL; // Node* cur = _root; // while (cur) // { // if (cur->_key > key) // { // parent = cur; // cur = cur->_left; // } // else if (cur->_key < key) // { // parent = cur; // cur = cur->_right; // } // else // { // Node* del = cur; // // 删除 // if(cur->_left == NULL) // { // if (parent == NULL) // _root == cur // { // _root = cur->_right; // } // else // { // if (parent->_left == cur) // { // parent->_left = cur->_right; // } // else // { // parent->_right = cur->_right; // } // } // } // else if (cur->_right == NULL) // { // if (parent == NULL) // { // _root = cur->_left; // } // else // { // if (parent->_left = cur) // { // parent->_left = cur->_left; // } // else // { // parent->_right = cur->_left; // } // } // } // else // { // // 替换法 // Node* parent = cur; // Node* subRight = cur->_right; // while (subRight->_left) // { // parent = subRight; // subRight = subRight->_left; // } // // cur->_key = subRight->_key; // del = subRight; // // // if (parent->_left == subRight) // { // parent->_left = subRight->_right; // } // else // { // parent->_right = subRight->_right; // } // // } // // delete del; // return true; // } // } // // return false; // } // // void InOrder() // { // _InOrder(_root); // cout<<endl; // } // // const Node* FindR(const K& key) // { // return _FindR(_root, key); // } // // bool InsertR(const K& key) // { // return _Insert(_root, key); // } // // bool RemoveR(const K& key) // { // return _RemoveR(_root, key); // } // //protected: // bool _RemoveR(Node*& root, const K& key) // { // if (root == NULL) // return false; // // if (root->_key < key) // { // return _RemoveR(root->_right, key); // } // else if (root->_key > key) // { // return _RemoveR(root->_left, key); // } // else // { // Node* del = root; // if (root->_left == NULL) // { // root = root->_right; // } // else if (root->_right == NULL) // { // root = root->_left; // } // else // { // // 替换法 // Node* parent = root; // Node* subRight = root->_right; // while (subRight->_left) // { // parent = subRight; // subRight = subRight->_left; // } // // swap(subRight->_key, root->_key); // // del = subRight; // // if (parent->_left == subRight) // { // parent->_left = subRight->_right; // } // else // { // parent->_right = subRight->_right; // } // } // // delete del; // return true; // } // } // // bool _Insert(Node*& root, const K& key) // { // if (root == NULL) // { // root = new Node(key); // return true; // } // // if (root->_key < key) // { // return _Insert(root->_right, key); // } // else if (root->_key > key) // { // return _Insert(root->_left, key); // } // else // { // return false; // } // } // // const Node* _FindR(Node* root, const K& key) // { // if (root == NULL) // { // return NULL; // } // // if (root->_key < key) // { // return _FindR(root->_right, key); // } // else if (root->_key > key) // { // return _FindR(root->_left, key); // } // else // { // return root; // } // } // // void _InOrder(Node* root) // { // if (root == NULL) // return; // // _InOrder(root->_left); // cout<<root->_key<<" "; // _InOrder(root->_right); // } // //protected: // Node* _root; //}; // // //void TestTree1() //{ // SearchBinaryTree<int> t1; // int a[] = {5, 3, 4,1,7,8,2,6,0,9}; // for (size_t i = 0; i < sizeof(a)/sizeof(a[0]); ++i) // { // t1.Insert(a[i]); // } // // t1.InOrder(); // // t1.Remove(2); // t1.Remove(8); // t1.Remove(1); // t1.Remove(5); // // t1.Remove(0); // t1.Remove(1); // t1.Remove(2); // t1.Remove(3); // t1.Remove(4); // t1.Remove(5); // t1.Remove(6); // t1.Remove(7); // t1.Remove(8); // t1.Remove(9); // // t1.InOrder(); // //} // //void TestTree2() //{ // SearchBinaryTree<int> t1; // int a[] = {5, 3, 4,1,7,8,2,6,0,9}; // for (size_t i = 0; i < sizeof(a)/sizeof(a[0]); ++i) // { // t1.InsertR(a[i]); // } // // t1.InOrder(); // // // t1.RemoveR(2); // t1.RemoveR(8); // t1.RemoveR(1); // t1.RemoveR(5); // // t1.RemoveR(0); // t1.RemoveR(1); // t1.RemoveR(2); // t1.RemoveR(3); // t1.RemoveR(4); // t1.RemoveR(5); // t1.RemoveR(6); // t1.RemoveR(7); // t1.RemoveR(8); // t1.RemoveR(9); // // t1.InOrder(); //} #pragma once // K/V // 1.Key 判断在不在 // 2.Key/Value 找key附带的信息 template<class K, class V> struct BSTreeNode { K _key; V _value; BSTreeNode<K, V>* _left; BSTreeNode<K, V>* _right; BSTreeNode(const K& key, const V& value) :_key(key) ,_value(value) ,_left(NULL) ,_right(NULL) {} }; template<class K, class V> class BSTree { typedef BSTreeNode<K, V> Node; public: BSTree() :_root(NULL) {} bool Insert(const K& key, const V& value) { return _Insert(_root, key, value); } Node* Find(const K& key) { return _Find(_root, key); } protected: bool _Insert(Node*& root, const K& key, const V& value) { if (root == NULL) { root = new Node(key, value); return true; } if (root->_key < key) { return _Insert(root->_right, key, value); } else if(root->_key > key) { return _Insert(root->_left, key, value); } else { return false; } } Node* _Find(Node* root, const K& key) { if (root == NULL) { return NULL; } if (root->_key < key) { return _Find(root->_right, key); } else if (root->_key > key) { return _Find(root->_left, key); } else { return root; } } protected: Node* _root; }; // K 和K/V void TestTree3() { BSTree<string, string> dict; dict.Insert("sort", "排序"); dict.Insert("tree", "树"); dict.Insert("string", "xxx"); dict.Insert("string", "字符串"); BSTreeNode<string, string>* ret = dict.Find("sort"); cout<<ret->_value<<endl; ret = dict.Find("string"); ret->_value = "字符串"; // 1.如何判断一个单词的拼写是否正确？ // 2.统计一个文件中每个单词出现的次数？ string file[] = {"string", "sort", "string", "string"}; BSTree<string, int> countTree; for (size_t i = 0; i < sizeof(file)/sizeof(file[0]); ++i) { BSTreeNode<string, int>* node = countTree.Find(file[i]); if (node) { node->_value++; } else { countTree.Insert(file[i], 1); } } // topk 小堆
测试：
#include<iostream> #include"BinaryTree.h" using namespace std; void test() { int array[] = {1,2,3,'#','#',4,'#','#',5,6,'#','#',7}; size_t sz = sizeof(array) / sizeof(array[0]); BinaryTree<int> t(array,sz,'#'); BinaryTree<int> t2; t2 = t; t2.InOder(); cout << t2.Size() << endl; cout << t2.Depth() << endl; cout<<t2.Leaf() << endl; } int main() { test(); system("pause"); return 0; }二叉树非递归遍历：
二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只 能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历序列的前驱或者后继。 为了保存这种在遍历中需要的信息，我们利用二叉树中指向左右子树的空指针来存放节点的前驱和后继信息。 enum PointerTag {THREAD, LINK}; template <class T> struct BinaryTreeNode_Thd { T _data ; // 数据 BinaryTreeNode_Thd<T >* _left; // 左孩子
BinaryTreeNode_Thd<T >* _right; // 右孩子
PointerTag _leftTag ; // 左孩子线索标志
PointerTag _rightTag ; // 右孩子线索标志 };
void PrevOrder_NonR()//非递归前序遍历 { if (_root == NULL) return; stack<Node*> s; Node* cur = _root; while ((cur != NULL) || (!s.empty())) { while (cur) { s.push(cur); cout << cur->_date << " "; cur = cur->_left; } cur = s.top(); s.pop(); cur = cur->_right; } cout << endl; } void InOrder_NonR()//非递归中序遍历 { if (_root == NULL) return; stack<Node*> s; Node* cur = _root; while ((cur != NULL) || (!s.empty())) { while (cur) { s.push(cur); cur = cur->_left; } cur = s.top(); cout << cur->_date << " "; s.pop(); cur = cur->_right; } cout << endl; } void PostOrder_NonR()//非递归后序遍历 { if (_root == NULL) return; stack<Node*> s; Node* cur = _root; Node* prev = NULL;//记录上一个访问到的节点 while ((cur != NULL) || (!s.empty())) { while (cur)//循环到最左边的节点 { s.push(cur); cur = cur->_left; } Node* top = s.top(); if (top->_right == NULL || top->_right == prev)//如果top的右节点为空或者访问过，则可以访问此节点 { cout << top->_date << " "; s.pop(); prev = top; } else { cur = top->_right;//访问右边 } } cout << endl; }线索化二叉树：
二叉树的结构：
enum PointerTag { THREAD, //线索化指针的标记 LINK //一般指针的标记 }; template <class T> struct BinaryTreeNode_Thd { //构造函数 BinaryTreeNode_Thd() : _date(0) , _left(NULL) , _right(NULL) , _leftTag(LINK) , _rightTag(LINK) {} BinaryTreeNode_Thd(const T& d) : _date(d) , _left(NULL) , _right(NULL) , _leftTag(LINK) , _rightTag(LINK) {} T _date; //数据 BinaryTreeNode_Thd<T>* _left; //左孩子 BinaryTreeNode_Thd<T>* _right;//右孩子 PointerTag _leftTag; //左孩子线索标志 PointerTag _rightTag; //右孩子线索标志 }; 中序线索化： void _InOrderThreading(Node* cur,Node*& prev) { if (cur == NULL) return; _InOrderThreading(cur->_left, prev); //左子树 //线索化左 if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } //访问到下一个节点后，线索化上一个节点右 if (prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; _InOrderThreading(cur->_right, prev); //右子树 } //前序线索化 void PrevOrderThreading() { Node* prev = NULL; _PrevOrderThreading(_root, prev); } //前序线索化遍历 void PrevOrderThd() { Node* cur = _root; while (cur) { while (cur->_leftTag != THREAD) { cout << cur->_date << " "; cur = cur->_left; } cout << cur->_date << " "; cur = cur->_right; } cout << endl; } void _PrevOrderThreading(Node* cur, Node*& prev) { if (cur == NULL) return; if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; if (cur->_leftTag == LINK) { _PrevOrderThreading(cur->_left, prev); } if (cur->_rightTag == LINK) { _PrevOrderThreading(cur->_right, prev); } } 后序线索化： void PostOrderThreading() { Node* prev = NULL; _PostOrderThreading(_root, prev); } //后序线索化 void _PostOrderThreading(Node* cur, Node*& prev) { if (cur == NULL) return; _PostOrderThreading(cur->_left, prev); _PostOrderThreading(cur->_right, prev); if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; } 小记： #include <iostream> #include <cstdlib> using namespace std; enum PointerTag { THREAD, //线索化指针的标记 LINK //一般指针的标记 }; template <class T> struct BinaryTreeNode_Thd { //构造函数 BinaryTreeNode_Thd() : _date(0) , _left(NULL) , _right(NULL) , _leftTag(LINK) , _rightTag(LINK) {} BinaryTreeNode_Thd(const T& d) : _date(d) , _left(NULL) , _right(NULL) , _leftTag(LINK) , _rightTag(LINK) {} T _date; //数据 BinaryTreeNode_Thd<T>* _left; //左孩子 BinaryTreeNode_Thd<T>* _right;//右孩子 PointerTag _leftTag; //左孩子线索标志 PointerTag _rightTag; //右孩子线索标志 }; template <class T> class BinaryTreeThread { typedef BinaryTreeNode_Thd<T> Node; public: BinaryTreeThread() :_root(NULL) {} BinaryTreeThread(T* a, size_t n, const T& invalid) { size_t index = 0; _root = _CreateTree(a, n, index, invalid); } //中序线索化 void InOrderThreading() { Node* prev = NULL; _InOrderThreading(_root, prev); } //中序线索化遍历 void InOrderThd() { Node* cur = _root; while (cur) { while (cur->_leftTag == LINK) { cur = cur->_left; } cout << cur->_date << " "; while (cur->_leftTag == THREAD) { cur = cur->_right; cout << cur->_date << " "; } cur = cur->_right; } cout << endl; } //前序线索化 void PrevOrderThreading() { Node* prev = NULL; _PrevOrderThreading(_root, prev); } //前序线索化遍历 void PrevOrderThd() { Node* cur = _root; while (cur) { while (cur->_leftTag != THREAD) { cout << cur->_date << " "; cur = cur->_left; } cout << cur->_date << " "; cur = cur->_right; } cout << endl; } //后序线索化 void PostOrderThreading() { Node* prev = NULL; _PostOrderThreading(_root, prev); } protected: //后序线索化 void _PostOrderThreading(Node* cur, Node*& prev) { if (cur == NULL) return; _PostOrderThreading(cur->_left, prev); _PostOrderThreading(cur->_right, prev); if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; } //前序线索化 void _PrevOrderThreading(Node* cur, Node*& prev) { if (cur == NULL) return; if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } if (prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; if (cur->_leftTag == LINK) { _PrevOrderThreading(cur->_left, prev); } if (cur->_rightTag == LINK) { _PrevOrderThreading(cur->_right, prev); } } //中序线索化 void _InOrderThreading(Node* cur,Node*& prev) { if (cur == NULL) return; _InOrderThreading(cur->_left, prev); //左子树 //线索化左 if (cur->_left == NULL) { cur->_leftTag = THREAD; cur->_left = prev; } //访问到下一个节点后，线索化上一个节点右 if (prev && prev->_right == NULL) { prev->_rightTag = THREAD; prev->_right = cur; } prev = cur; _InOrderThreading(cur->_right, prev); //右子树 } Node* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid) { Node* NewNode = NULL; if (index < size && a[index] != invalid) { NewNode = new Node(a[index]); NewNode->_left = _CreateTree(a, size, ++index, invalid); NewNode->_right = _CreateTree(a, size, ++index, invalid); } return NewNode; } protected: Node* _root; }; void Test() { int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }; int a2[15] = { 1, 2, '#', 3, '#', '#', 4, 5, '#', 6, '#', 7, '#', '#', 8 }; BinaryTreeThread<int> a(a1, 10, '#'); //a.InOrderThreading(); //a.InOrderThd(); //a.PrevOrderThreading(); //a.PrevOrderThd(); a.PostOrderThreading(); } int main() { Test(); return 0; }