您好,登錄后才能下訂單哦!
二叉樹是一種樹形結(jié)構(gòu),它每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(即二叉樹中不存在度大于2的結(jié)點(diǎn))。
所謂度是結(jié)點(diǎn)擁有的子樹數(shù)。
對(duì)于二叉樹,它具有以下的性質(zhì):
1、在二叉樹的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i>=1)。
2、深度為k的二叉樹至多有2^k-1個(gè)結(jié)點(diǎn)。
3、對(duì)任何一棵二叉樹,如果它的葉子結(jié)點(diǎn)個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)為n2,那么m = n + 1;
eg.如果設(shè)一個(gè)二叉樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為n1
故總結(jié)點(diǎn)數(shù) N = n0 + n1 + n2; (1)
二叉樹除了根結(jié)點(diǎn)外,其余結(jié)點(diǎn)都有一個(gè)分支,設(shè)M為分支總數(shù),則 N = M + 1;由于這些分支是由度為1或2的結(jié)點(diǎn)射出的,則M = n1 + 2*n2;
則有 N = n1 + 2*n2 + 1 (2)
由(1)(2)得 n0 = n2 + 1;
4、具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為∟log 2 n」+1.(其中“∟x」 ”表示不大于x的最大整數(shù))。
5、如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序編號(hào)(每一層從左到右,直到∟log 2 n」+1),則對(duì)任意一結(jié)點(diǎn)i(1=<i<=n)有
(1)如果i=1,則結(jié)點(diǎn)i是二叉樹的根,無雙親;如果i>1,則其雙親是結(jié)點(diǎn)∟i/2」.
(2)如果2i>n,則結(jié)點(diǎn)i無左右孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn))否則其左孩子是結(jié)點(diǎn)2i;
(3)如果2i+1>n,則結(jié)點(diǎn)i無左右孩子;否則其右孩子是結(jié)點(diǎn)2i+1;
#pragma once #include<queue> #include<stack> #include<iostream> using namespace std; template<class T> struct BinaryTreeNode { BinaryTreeNode<T> *_left; BinaryTreeNode<T> *_right; T _data; public: BinaryTreeNode(const T& x) :_data(x) ,_right(NULL) ,_left(NULL) {} }; template<class T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: BinaryTree() :_root(NULL) {} BinaryTree<T>(const T* a, size_t size, const T& invalid) { size_t index = 0; _root = _CreatTree(a, size, index, invalid); } BinaryTree<T>(const BinaryTree<T>& t) { _root=_Copy(t._root); } BinaryTree<T>& operator=( BinaryTree<T> t) { swap(_root, t._root); return *this; } ~BinaryTree() { _Clear(_root); _root=NULL; } void PrevOrder() { cout << "先序:" << endl; _PrevOrder(_root); } void InOrder() { cout << "中序:" << endl; _InOrder(_root); } void PostOrder() { cout << "后序:" << endl; _PostOrder(_root); } //層序 //思想:隊(duì)列 //1.先判斷根節(jié)點(diǎn)是否為NULL //2.如果根節(jié)點(diǎn)不為空,節(jié)點(diǎn)入隊(duì)(不是入值) //3.判斷隊(duì)列是否為空,如果不為空,出隊(duì) //4.判斷左 右子樹節(jié)點(diǎn)是否為空, //5.如果不為空,入隊(duì) 左右節(jié)點(diǎn),跳至2 void LeveLorder() //層序 { cout << "層序:" << endl; queue<Node*> tmp; if (_root == NULL) return; else { tmp.push(_root); while (!tmp.empty()) { Node* Front = tmp.front(); cout << Front->_data << " "; tmp.pop(); if (Front->_left) { tmp.push(Front->_left); } if (Front->_right) { tmp.push(Front->_right); } } } } size_t Size() { return _Size(_root); } size_t Depth() { _Depth(_root); } size_t LeafSize() { return _leafSize(_root); } protected: Node* _CreatTree(const T*a, size_t size, size_t& index, const T& invalid) { Node* root = NULL; if (a[index] != invalid&&index < size) { root = new Node(a[index]); root->_left = _CreatTree(a, size, ++index, invalid);//++index 返回index index++返回臨時(shí)變量(在此編譯不通過) root->_right = _CreatTree(a, size, ++index, invalid); } return root; } //先序遍歷 遞歸形式 void _PrevOrder(Node* root) { if (root == NULL) return; cout << root->_data << " "; _PrevOrder(root->_left); _PrevOrder(root->_right); } //先序遍歷 非遞歸 借助棧 //和層序?qū)崿F(xiàn)差不多,只是一個(gè)是借助隊(duì),一個(gè)是借助棧 void _PrevOrder(Node* root) { stack<Node*> cur; if (root == NULL) //1.先判斷根結(jié)點(diǎn)是否為空 return; else { cur.push(root); //2,壓棧 while (!cur.empty()) // 3.判斷棧是否為空,不為空,先壓右 再壓左子樹 { Node* temp = cur.top(); cout << temp->_data << " "; cur.pop(); if (temp->_right) { cur.push(temp->_right); } if (temp->_left) { cur.push(temp->_left); } } } } //中序遍歷 遞歸形式 void _InOrder(Node* root) { if (root == NULL) return; _InOrder(root->_left); cout << root->_data << " "; _InOrder(root->_right); } //中序遍歷 非遞歸 借助棧 void _InOrder(Node* root) { Node* cur = root; stack<Node*> tack; while (cur || !tack.empty()) { while (cur) { tack.push(cur); cur = cur->_left; } if (!tack.empty()) { Node* Top = tack.top(); tack.pop(); cout << Top->_data <<" "; cur = Top->_right; } } } //后序遍歷 遞歸形式 void _PostOrder(Node* root) { if (root == NULL) return; _PostOrder(root->_left); _PostOrder(root->_right); cout << root->_data << " "; } //后序遍歷 非遞歸 借助棧 void _PostOrder(Node* root) { Node* prev=NULL; Node* cur = root; stack<Node*> tmp; while (cur || !tmp.empty()) { while (cur) { tmp.push(cur); cur = cur->_left; } Node* Top = tmp.top(); if (Top->_right == NULL||Top->_right==prev) { cout << Top->_data << " "; tmp.pop(); prev = Top; cur = NULL; } else { cur = Top->_right; } } } void _Size(Node* root) { if (root == NULL) return 0; return _Size(root->_left) + _Size(root->_right) + 1; } size_t _Depth(Node* root) { if (root == NULL) return 0; int leftdepth = _Depth(root->_left); int rightdepth = _Depth(root->_right); return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1; } size_t _leafSize(Node* root) { static size_t size = 0; if (root == NULL) return 0; if (root->_left == NULL&&root->_right == NULL) { ++size; return size; } _leafSize(root->_left); _leafSize(root->_right); return size; } void _Clear(Node* root) { if (root) { _Clear(root->_left); _Clear(root->_right); delete root; } } Node* _Copy(Node* root) { if (root==NULL) { return NULL; } Node *tem = new Node(root->_data); tem->_left=_Copy(root->_left); tem->_right=_Copy(root->_right); return tem; } private: Node* _root; };
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。