【数据结构】 二叉树

二叉树概念

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

二 叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2^{i-1}个结点；深度为k 的二叉树至多有2^k-1个结点；对任何一棵二叉树T，如果其终端结点数为n_0，度为2的结点数为n_2，则n_0=n_2+1。

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。

二叉树性质

(1) 在非空二叉树中，第i层的结点总数不超过2^(i-1),i>=1；

(2) 深度为h的二叉树最多有2^h - 1 个结点(h>=1)，最少有h个结点；

(3) 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；

(4) 具有n个结点的完全二叉树的深度为log 2 (n+1) [ log 以2为底的 n+1 ]

存储结构：顺序存储，链式存储

遍历方式：前序遍历，中序遍历，后序遍历

前序遍历：

void_PreOrder(Node*root)
{
if(root==NULL)
return;

cout<<root->_data<<"";
_PreOrder(root->_left);
_PreOrder(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<<"";
}

此外，对于二叉树的操作还有：

树的深度Depth()

树的大小Size()

叶子结点的个数LeafSize()

K层也加点个数 GetKLevel()

实现如下：

Depth()：

size_t_Depth(Node*root)
{
if(root==NULL)
return0;

intleftDepth=_Depth(root->_left);
intrightDepth=_Depth(root->_right);

returnleftDepth>rightDepth?leftDepth+1:rightDepth+1;
}

Size()：

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

LeafSize()：

void_LeafSize(Node*root,size_t&size)//size需传引用，以保证每次在上次的调用加值，否则size结果为0
{
if(root==NULL)
return;
if(root->_left==NULL&&root->_right==NULL)
{
++size;
return;
}
_LeafSize(root->_left,size);
_LeafSize(root->_right,size);
}

GetKLevel()：

void_GetKLevel(Node*root,intk,size_tlevel,size_t&kSize)
{
if(root==NULL)
{
return;
}

if(level==k)
{
++kSize;
return;
}

_GetKLevel(root->_left,k,level+1,kSize);
_GetKLevel(root->_right,kSize);
}

至此，二叉树的基本操作已经完成。

我们发现在实现二叉树的前序，中序，后序遍历时都是利用递归的机制，那么非递归又是怎么实现的呢？

在此，写出三种不同遍历方式的非递归方式实现：

前序遍历（非递归）：

void_PreOrder_NoR()
{
stack<Node*>s;
if(_root)
{
s.push(_root);
}

while(!s.empty())
{
Node*top=s.top();
cout<<top->_data<<"";

s.pop();

if(top->_right)//先压右树，后压左树
{
s.push(top->_right);
}
if(top->_left)
{
s.push(top->_left);
}
}
}

中序遍历（非递归）：

void_InOrder_NoR()
{
Node*cur=_root;
stack<Node*>s;

while(cur||!s.empty())
{
while(cur)
{
//1.压一棵树的左路节点，直到最左节点
s.push(cur);
cur=cur->_left;
}
//2.栈不为空，出栈访问，并移向右树，判断右树是否为空，后循环此操作，直至栈为空
if(!s.empty())
{
Node*top=s.top();
s.pop();
cout<<top->_data<<"";
cur=top->_right;
}
}
}

后序遍历（非递归）：

void_PostOrder_NoR()
{
Node*pre=NULL;
Node*cur=_root;
stack<Node*>s;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left;
}

Node*top=s.top();
if(top->_right==NULL||top->_right==pre)
{
cout<<top->_data<<"";
s.pop();
pre=top;
}
else
{
cur=top->_right;
}
}
}

发现，非递归的实现是利用栈结构存储和管理二叉树的。

附源代码以及测试代码：

BinaryTree.h 文件：

#pragmaonce

#include<stack>
template<classT>
structBinaryTreeNode
{
T_data;
BinaryTreeNode<T>*_left;
BinaryTreeNode<T>*_right;

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

template<classT>
classBinaryTree
{
typedefBinaryTreeNode<T>Node;
public:
BinaryTree()
:_root(NULL)
{}

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

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

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

BinaryTree<T>&operator=(BinaryTree<T>t)
{
swap(this->_root,t._root);
return*this;
}

~BinaryTree()
{
_Destory(_root);
_root=NULL;
}

voidPreOrder()
{
_PreOrder(_root);
cout<<endl;
}

voidInOrder()
{
_InOrder(_root);
cout<<endl;
}

voidPostOrder()
{
_PostOrder(_root);
cout<<endl;
}

size_tSize()
{
return_Size(_root);
}

size_tDepth()
{
return_Depth(_root);
}

size_tLeafSize()
{
size_tsize=0;
_LeafSize(_root,size);
returnsize;
}

size_tGetKLevel(intk)
{
size_tkSize=0;
size_tlevel=1;
_GetKLevel(_root,level,kSize);

returnkSize;
}

voidPreOrder_NoR()
{
_PreOrder_NoR();
cout<<endl;
}

voidInOrder_NoR()
{
_InOrder_NoR();
cout<<endl;
}

voidPostOrder_NoR()
{
_PostOrder_NoR();
cout<<endl;
}


protected:
void_Destory(Node*root)
{
if(root==NULL)
{
return;
}

_Destory(root->_left);
_Destory(root->_right);

deleteroot;
}

Node*_Copy(Node*root)
{
if(root==NULL)
{
returnNULL;
}

Node*newRoot=newNode(root->_data);
newRoot->_left=_Copy(root->_left);
newRoot->_right=_Copy(root->_right);

returnnewRoot;
}

Node*_CreatBinaryTree(constT*a,size_t&index,constT&invalid)
{
Node*root=NULL;
while(index<size&&a[index]!=invalid)
{
root=newNode(a[index]);//new并初始化
root->_left=_CreatBinaryTree(a,++index,invalid);
root->_right=_CreatBinaryTree(a,invalid);
}
returnroot;
}

void_PreOrder(Node*root)
{
if(root==NULL)
return;

cout<<root->_data<<"";
_PreOrder(root->_left);
_PreOrder(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<<"";
}

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;
}

void_LeafSize(Node*root,size);
}

void_GetKLevel(Node*root,kSize);
}

void_PreOrder_NoR()//前序遍历->非递归
{
stack<Node*>s;
if(_root)
{
s.push(_root);
}

while(!s.empty())
{
Node*top=s.top();
cout<<top->_data<<"";

s.pop();

if(top->_right)//先压右树，后压左树
{
s.push(top->_right);
}
if(top->_left)
{
s.push(top->_left);
}
}
}

void_InOrder_NoR()
{
Node*cur=_root;
stack<Node*>s;

while(cur||!s.empty())
{
while(cur)
{
//1.压一棵树的左路节点，直到最左节点
s.push(cur);
cur=cur->_left;
}
//2.栈不为空，出栈访问，并移向右树，判断右树是否为空，后循环此操作，直至栈为空
if(!s.empty())
{
Node*top=s.top();
s.pop();
cout<<top->_data<<"";
cur=top->_right;
}
}
}

void_PostOrder_NoR()
{
Node*pre=NULL;
Node*cur=_root;
stack<Node*>s;
while(cur||!s.empty())
{
while(cur)
{
s.push(cur);
cur=cur->_left;
}

Node*top=s.top();
if(top->_right==NULL||top->_right==pre)
{
cout<<top->_data<<"";
s.pop();
pre=top;
}
else
{
cur=top->_right;
}
}
}

protected:
Node*_root;
};

Test.cpp 文件：

#include<iostream>
usingnamespacestd;

#include"BinaryTree.h"

intmain()
{
inta[10]={1,2,3,'#',4,5,6};
BinaryTree<int>t(a,10,'#');

cout<<t.Depth()<<endl;
cout<<t.Size()<<endl;

t.PreOrder();
t.InOrder();
t.PostOrder();

cout<<t.GetKLevel(1)<<endl;
cout<<t.GetKLevel(3)<<endl;

cout<<t.LeafSize()<<endl;

t.PreOrder_NoR();
t.InOrder_NoR();
t.PostOrder_NoR();

system("pause");
return0;
}

若有纰漏，欢迎指正。

本文出自 “Vs吕小布” 博客，请务必保留此出处http://www.52php.cn/article/p-nyzjnlui-ms.html

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!