【数据结构】 二叉树

数据结构 前端之家
前端之家收集整理的这篇文章主要介绍了【数据结构】 二叉树，前端之家小编觉得挺不错的，现在分享给大家，也给大家做个参考。

二叉树概念


在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（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.jb51.cc/article/p-nyzjnlui-ms.html

原文链接：https://www.f2er.com/datastructure/382486.html

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

【数据结构】键树
键树的基本概念 键树又称数字查找树（Digital Search Tree）。 它是一棵度大于等于2的树，...
【数据结构】绪论
[TOC] 基本概念 数据： 数据 是对客观事物的符号表示，在计算机科学中指所有能输入到计算机...
【数据结构】证明法
[TOC] 反证法 基本概念： 一般地，假设原命题不成立（即 在原命题的条件下，结论不成立），...
数据结构与算法系列之目录
最近抽空整理了&quot;数据结构和算法&quot;的相关文章。在整理过程中，对于每种数...
【数据结构】数组
[TOC] 矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最...
[操作系统]操作系统中断机制
1.当中断发生时，cpu立即进入核心态 2.当中断发生后，当前进程进入暂停状态，操作系统内核...
[日常] 浏览器前进后退与数据结构的思想
一张图保存一下 红点是当前地址 白色箭头是新打开页面 黑色箭头是后退页面 栈的思想 , 后退...
[算法] 开放寻址法解决哈希冲突方式
开放寻址法：又称开放定址法，当哈希冲突发生时，从发生冲突的那个单元起，按照一定的次序...
二叉树的基本概念介绍与代码实现（多图+代码）
@ 树的基本概念 图1 树的结点 结点：使用树结构存储的每一个数据元素都被称为“结点”。例...
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
1.准备工作 首先包含头文件，定义链表结构体，产生随即链表的范围，定义全局头尾节点。 #i...
LinuxWindowsCentOSUbuntuNginxWebServiceScalaMemcacheApacheRedisDockerBashAzureTomcatLNMPShell数据结构服务器运维网络安全
xebugnodemondocker-copydcoselasticsearcwindows-contdocker-windodocker-awsamazon-cloudenvoyproxyhashicorp-vaswisscomdevkafka-pythonzscalerphoton-osdocker-swarmkamongoogle-cloudconcoursewso2-ampersistent-vapi-managerprocess-manamanjarojenkins-workhypriotremoteapikeystonejsbitcoindbitcoin-test