【数据结构】二叉树的实现（如：默认成员函数、（叶子）节点数、深度、四种遍历）

二叉树：树的每个节点最多有两个子节点。

我们看下它的结构，有二叉链表结构与三叉链表结构，具体结果如我摘自《C++Primer》中的图。

相比之下，三叉链表的优势在于当我们知道父亲节点要找他的子女节点比较方便和便捷，反之当我们知道子女节点找它的父亲节点时也方便。

下面，我实现下二叉链表的结构。

template<classT>
structBinaryTreeNode
{
BinaryTreeNode<T>*_left;//左子树
BinaryTreeNode<T>*_right;//右子树
T_data;

BinaryTreeNode(constT&x)
:_left(NULL),_right(NULL),_data(x)
{}
};

（1）求二叉树的叶子节点数leafsize:

叶子节点指的是，节点无子女节点。我们有两种思路：

1）设置一下全局变量或者静态变量的size，遍历二叉树，每次遇到一个节点就加加一次size

2)总叶子节点数就等于左子树叶子节点个数+右子树叶子节点个数+根节点个数1

//思路1：
size_t_LeafSize(Node*root)
{
staticintsize=0;
if(root==NULL)
{
returnsize;
}
if(root->_left==NULL&&root->_right==NULL)
{
size++;
returnsize;
}
_LeafSize(root->_left);
_LeafSize(root->_right);
}

//思路2：
size_t_LeafSize(Node*root)
{
if(root==NULL)
{
return0;
}
if(root->_left==NULL&&root->_right==NULL)
{
return1;
}
return_LeafSize(root->_left)+_LeafSize(root->_right);
}

（2）求二叉树的深度depth:

深度也称作为高度，就是左子树和右子树深度的较大值。

size_t_Depth(Node*root)
{
if(root==NULL)
{
return0;
}
intLeftDepth=_Depth(root->_left);
intRightDepth=_Depth(root->_right);
returnLeftDepth>RightDepth?LeftDepth+1:RightDepth+1;
}

（3）求二叉树的节点个数size:

总节点数就等于左子树节点个数+右子树节点个数+根节点个数1

size_t_Size(Node*root)
{
if(root==NULL)
{
return0;
}
return_Size(root->_left)+_Size(root->_right)+1;
}

（4）遍历二叉树：

注意：前中后序遍历要不要漏掉递归出口。

1）前序遍历：访问根节点->左子树->右子树

void_PrevOrder(Node*root)
{
if(root==NULL)
{
return;
}
cout<<root->_data<<"";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}

2）中序遍历：访问左子树->根节点->右子树

void_InOrder(Node*root)
{
if(root==NULL)
{
return;
}
_InOrder(root->_left);
cout<<root->_data<<"";
_InOrder(root->_right);
}

3）后序遍历：访问左子树->右子树->根节点

void_PostOrder(Node*root)
{
if(root==NULL)
{
return;
}
_PostOrder(root->_left);
_PostOrder(root->_right);
cout<<root->_data<<"";
}

4）层次遍历：

即一层一层地遍历结束，再遍历下一层节点，如int a1[10] = { 1,2,3,'#',4,5,6 }（注意：#表示空。）则层次遍历就应为：1，2，5，3，4，6。

我们用队列解决该问题：首先先给队列无条件入队根节点，下面在出队根节点之前先入队它的子女节点2、5。此时，出队1后队头元素为2，在出队它之前入队它的根节点3，4……

void_LevelOrder(Node*root)
{
queue<Node*>q;
if(root==NULL)
{
return;
}
q.push(root);
while(!q.empty())
{
if(q.front()->_left!=NULL)
{
q.push(q.front()->_left);

}
if(q.front()->_right!=NULL)
{
q.push(q.front()->_right);

}
cout<<q.front()->_data<<"";
q.pop();
}
}

我给出完整程序代码（测试用例我就不要在此处多加阐述了，你们可以自己实现）。

#include<iostream>
usingnamespacestd;
#include<queue>
template<classT>
structBinaryTreeNode
{
BinaryTreeNode<T>*_left;//左子树
BinaryTreeNode<T>*_right;//右子树
T_data;
BinaryTreeNode(constT&x)
:_left(NULL),_data(x)
{}
};

template<classT>
classBinaryTree
{
typedefBinaryTreeNode<T>Node;//重命名在于想简化代码，避免过长。
public:
BinaryTree()
:_root(NULL)
{}

BinaryTree(constT*a,size_tsize,constT&invalid)
:_root(NULL)
{
size_tindex=0;
_root=_CreateTree(a,size,invalid,index);
}

BinaryTree<T>(constBinaryTree<T>&t)
:_root(NULL)
{
_Copy(t._root);
}

BinaryTree<T>&operator=(constBinaryTree<T>&t)
{
if(&t!=this)
{
_Copy(t._root);
_Destroy(_root);
}
return*this;
}

~BinaryTree()
{
if(_root)
{
_Destroy(_root);
}
}

//前序遍历
voidPreOrder()
{
_PrevOrder(_root);
cout<<endl;
}

//中序遍历
voidInOrder()
{
_InOrder(_root);
cout<<endl;
}

//后序遍历
voidPostOrder()
{
_PostOrder(_root);
cout<<endl;
}

//层次遍历
voidLevelOrder()
{
_LevelOrder(_root);
cout<<endl;
}


//节点数
size_tSize()
{
return_Size(_root);
}

//深度（高度）
size_tDepth()
{
return_Depth(_root);
}

//叶子节点数
size_tLeafSize()
{
return_LeafSize(_root);
}
protected:
void_Destroy(Node*root)
{
if(root==NULL)
{
return;
}
if(root->_left==NULL&&root->_right==NULL)
{
deleteroot;
root=NULL;
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
}

void_Copy(Node*troot)
{
if(troot==NULL)
{
return;
}
if(troot->_left==NULL&&troot->_right==NULL)
{
Node*root=newNode(troot->_data);
return;
}
root->_left=_Copy(troot->_left);
root->_right=_Copy(troot->_right);
}

//方法1：
/*size_t_LeafSize(Node*root)
{
staticintsize=0;
if(root==NULL)
{
returnsize;
}
if(root->_left==NULL&&root->_right==NULL)
{
size++;
returnsize;
}
_LeafSize(root->_left);
_LeafSize(root->_right);
}*/

//方法2：
size_t_LeafSize(Node*root)
{
if(root==NULL)
{
return0;
}
if(root->_left==NULL&&root->_right==NULL)
{
return1;
}
return_LeafSize(root->_left)+_LeafSize(root->_right);
}

size_t_Size(Node*root)
{
if(root==NULL)
{
return0;
}
return_Size(root->_left)+_Size(root->_right)+1;
}

size_t_Depth(Node*root)
{
if(root==NULL)
{
return0;
}
intLeftDepth=_Depth(root->_left);
intRightDepth=_Depth(root->_right);
returnLeftDepth>RightDepth?LeftDepth+1:RightDepth+1;
}

Node*_CreateTree(constT*a,constT&invalid,size_t&index)
{
Node*root=NULL;
if(index<size&&a[index]!=invalid)
{
root=newNode(a[index]);
root->_left=_CreateTree(a,++index);
root->_right=_CreateTree(a,++index);
}
returnroot;
}


//前序遍历：访问根节点->左子树->右子树
void_PrevOrder(Node*root)
{
if(root==NULL)
{
return;
}
cout<<root->_data<<"";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}

//中序遍历：访问左子树->根节点->右子树
void_InOrder(Node*root)
{
if(root==NULL)
{
return;
}
_InOrder(root->_left);
cout<<root->_data<<"";
_InOrder(root->_right);
}

//后序遍历：访问左子树->右子树->根节点
void_PostOrder(Node*root)
{
if(root==NULL)
{
return;
}
_PostOrder(root->_left);
_PostOrder(root->_right);
cout<<root->_data<<"";
}

void_LevelOrder(Node*root)
{
queue<Node*>q;
if(root==NULL)
{
return;
}
q.push(root);
while(!q.empty())
{
if(q.front()->_left!=NULL)
{
q.push(q.front()->_left);

}
if(q.front()->_right!=NULL)
{
q.push(q.front()->_right);

}
cout<<q.front()->_data<<"";
q.pop();
}
}
protected:
Node*_root;
};

【数据结构】二叉树的实现（如：默认成员函数、（叶子）节点数、深度、四种遍历）

猜你在找的数据结构相关文章