基於C++類和指針實現二叉樹

（4）具有n個節點的完全二叉樹的深度為log_2ⁿ + 1。

3、二叉樹的存儲結構

　　可以采用順序存儲數組和鏈式存儲二叉鏈表兩種方法來存儲二叉樹。經常使用的二叉鏈表方法，因為其非常靈活，方便二叉樹的操作。二叉樹的二叉鏈表存儲結構如下所示：

1 typedef struct binary_tree_node
2 {
3     int elem;
4     struct binary_tree_node *left;
5     struct binary_tree_node *right;
6 }binary_tree_node,*binary_tree;

舉例說明二叉鏈表存儲過程，如下圖所示：

從圖中可以看出：在還有n個結點的二叉鏈表中有n+1個空鏈域。

4、遍歷二叉樹

　　遍歷二叉樹是按照指定的路徑方式訪問書中每個結點一次，且僅訪問一次。由二叉樹的定義，我們知道二叉數是由根結點、左子樹和右子樹三部分構成的。通常遍歷二叉樹是從左向右進行，因此可以得到如下最基本的三種遍歷方法：

（1）先根遍歷（先序遍歷）：如果二叉樹為空，進行空操作；否則，先訪問根節點，然後先根遍歷左子樹，最後先根遍歷右子樹。采用遞歸形式實現代碼如下：

1 void preorder_traverse_recursive(binary_tree root)
2 {
3     if(NULL != root)
4     {
5         printf("%d\t",root->elem);
6         preorder_traverse_recursive(root->left);
7         preorder_traverse_recursive(root->right);
8     }
9 }

具體過程如下圖所示：

（2）中根遍歷（中序遍歷）：如果二叉樹為空，進行空操作；否則，先中根遍歷左子樹，然後訪問根結點，最後中根遍歷右子樹。遞歸過程實現代碼如下：

1 void inorder_traverse_recursive(binary_tree root)
2 {
3     if(NULL != root)
4     {
5         inorder_traverse_recursive(root->left);
6         printf("%d\t",root->elem);
7         inorder_traverse_recursive(root->right);
8     }
9 }

具體過程如下圖所示：

（3）後根遍歷（後序遍歷）：如果二叉樹為空，進行空操作；否則，先後根遍歷左子樹，然後後根遍歷右子樹，最後訪問根結點。遞歸實現代碼如下：

1 void postorder_traverse_recursive(binary_tree root)
2 {
3     if(NULL != root)
4     {
5         postorder_traverse_recursive(root->left);
6         postorder_traverse_recursive(root->right);
7         printf("%d\t",root->elem);
8     }
9 }

具體過程如下圖所示：

用類和指針實現的二叉樹：

#include
using namespace std;
struct tree
{
	int data;
	tree *left,*right;
};
class Btree
{
	static int n;
	static int m;
public:
	tree *root;
	Btree()
	{
		root=NULL;
	}
	void create_Btree(int);
	void Preorder(tree *);                  //先序遍歷
	void inorder(tree *);                   //中序遍歷
	void Postorder(tree *);                 //後序遍歷
	void display1() {Preorder(root); cout<data=x;
	newnode->right=newnode->left=NULL;
	if(root==NULL)
		root=newnode;
	else
	{
		tree *back;
		tree *current=root;
		while(current!=NULL)
		{
			back=current;
			if(current->data>x)
				current=current->left;
			else
				current=current->right;
		}
		if(back->data>x)
			back->left=newnode;
		else
			back->right=newnode;
	}
}
int Btree::count(tree *p)
{
	if(p==NULL)
		return 0;
	else
		return count(p->left)+count(p->right)+1;      //這是運用了函數嵌套即遞歸的方法。
}
void Btree::Preorder(tree *temp)    //這是先序遍歷二叉樹，采用了遞歸的方法。
{
	if(temp!=NULL)
	{
		cout<data<<" ";
		Preorder(temp->left);
		Preorder(temp->right);
	}
}
void Btree::inorder(tree *temp)      //這是中序遍歷二叉樹，采用了遞歸的方法。
{
	if(temp!=NULL)
	{
		inorder(temp->left);
		cout<data<<" ";
		inorder(temp->right);
	}
}
void Btree::Postorder(tree *temp)     //這是後序遍歷二叉樹，采用了遞歸的方法。
{
	if(temp!=NULL)
	{
		Postorder(temp->left);
		Postorder(temp->right);
		cout<data<<" ";
	}
}
int Btree::findleaf(tree *temp)
{
	if(temp==NULL)return 0;
	else
	{
		if(temp->left==NULL&&temp->right==NULL)return n+=1;
		else
		{
			findleaf(temp->left);
			findleaf(temp->right);
		}
		return n;
	}
}
int Btree::findnode(tree *temp)
{
	if(temp==NULL)return 0;
	else
	{
		if(temp->left!=NULL&&temp->right!=NULL)
		{
			findnode(temp->left);
			findnode(temp->right);
		}
		if(temp->left!=NULL&&temp->right==NULL)
		{
			m+=1;
			findnode(temp->left);
		}
		if(temp->left==NULL&&temp->right!=NULL)
		{
			m+=1;
			findnode(temp->right);
		}
	}
	return m;
}


void main()
{
	Btree A;
	int array[]={100,4,2,3,15,35,6,45,55,20,1,14,56,57,58};
	int k;
	k=sizeof(array)/sizeof(array[0]);
	cout<<"建立排序二叉樹順序: "<