【寫(xiě)一個(gè)算法 統(tǒng)計(jì)二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)遞歸做】
這是我們老師給我們寫(xiě)的二叉樹(shù)最基本的.......追加、刪除節(jié)點(diǎn)的程序，很簡(jiǎn)單，但是也不簡(jiǎn)單，如果你基礎(chǔ)比較好，這個(gè)可以忽略，如果不好，看看也無(wú)妨，打醬油路過(guò).......呵呵#include
using namespace std;// 二叉搜索樹(shù)class BsTree {public: // 構(gòu)造函數(shù)中初始化為空樹(shù) BsTree (void) : m_root (NULL), m_size (0) {} // 析構(gòu)函數(shù)中釋放剩余節(jié)點(diǎn) ~BsTree (void) {Clear (); } // 插入數(shù)據(jù) void Insert (int data) {Insert (new Node (data), m_root);m_size++; } // 刪除數(shù)據(jù)，不存在返回false bool Remove (int data) {Node*& find = Find (data, m_root);if (find) {Insert (find -> m_left, find -> m_right);Node* node = find;find = find -> m_right;delete node;m_size--;return true;}return false; } // 刪除所有值為data的數(shù)據(jù) void RemoveAll (int data) {while (Remove (data)); } // 清空樹(shù) void Clear (void) {Clear (m_root);m_size = 0; } // 將全部old更新為_(kāi)new void Update (int old, int _new) {while (Remove (old))Insert (_new); } // 能否找到data bool Find (int data) {return Find (data, m_root) != NULL; } // 中序遍歷 void Travel (void) {cout << '{';Travel (m_root);cout << '}' << endl; } // 獲取樹(shù)的大小 size_t GetSize (void) {return m_size; } // 獲取樹(shù)的高度 size_t GetHeight (void) {return GetHeight (m_root); }private: // 節(jié)點(diǎn) class Node { public:Node (int data) : m_data (data), m_left (NULL), m_right (NULL) {}int m_data; // 數(shù)據(jù)Node* m_left; // 左樹(shù)Node* m_right; // 右樹(shù) }; void Insert (Node* node, Node*& tree) {if (! tree)tree = node;else if (node) {if (node -> m_data < tree -> m_data)Insert (node, tree -> m_left);elseInsert (node, tree -> m_right);} } Node*& Find (int data, Node*& tree) {if (! tree)return tree;elseif (data =https://www.myit5.com/shenghuo/= tree -> m_data)return tree;elseif (data < tree -> m_data)return Find (data, tree -> m_left);elsereturn Find (data, tree -> m_right); } void Clear (Node*& tree) {if (tree) {Clear (tree -> m_left);Clear (tree -> m_right);delete tree;tree = NULL;} } void Travel (Node*& tree) {if (tree) {Travel (tree -> m_left);cout << ' ' << tree -> m_data << ' ';Travel (tree -> m_right);} } size_t GetHeight (Node*& tree) {if (tree) {size_t lh = GetHeight (tree -> m_left);size_t rh = GetHeight (tree -> m_right);return (lh > rh ? lh : rh) + 1;}return 0; } Node* m_root; // 樹(shù)根 size_t m_size; // 樹(shù)的大小};int main (void) { BsTree bs; bs.Insert (50); bs.Insert (70); bs.Insert (20); bs.Insert (60); bs.Insert (40); bs.Insert (30); bs.Insert (10); bs.Insert (90); bs.Insert (80); bs.Travel (); cout << bs.GetSize () << ", " << bs.GetHeight () << endl; cout << boolalpha << bs.Find (3) << endl; cout << boolalpha << bs.Find (10) << endl; bs.Remove (60); bs.Remove (30); bs.Travel (); bs.Insert (40); bs.Insert (40); bs.Travel (); bs.RemoveAll (40); bs.Travel (); bs.Insert (70); bs.Insert (70); bs.Travel (); bs.Update (70, 75); bs.Travel (); bs.Clear (); bs.Travel (); return 0;}
猜你喜歡
