基于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<<"建立排序二叉树顺序: "<