【数据结构】 二叉树

二叉树概念

在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（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)
????????????return?0;

????????int?leftDepth?=?_Depth(root->_left);
????????int?rightDepth?=?_Depth(root->_right);

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

Size()：

size_t?_Size(Node*?root)
????{
????????if?(root?==?NULL)
????????????return?0;
????????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,?int?k,????????size_t?level,?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 文件：

#pragma?once?

#include?<stack>
template?<class?T>
struct?BinaryTreeNode
{
????T?_data;
????BinaryTreeNode<T>*?_left;
????BinaryTreeNode<T>*?_right;

????BinaryTreeNode(const?T&?x)
????????:?_data(x)
????????,?_left(NULL)
????????,?_right(NULL)
????{}
};

template?<class?T>
class?BinaryTree
{
????typedef?BinaryTreeNode<T>?Node;
public:
????BinaryTree()
????????:_root(NULL)
????{}

????BinaryTree(const?T*?a,?size_t?size,?const?T&?invalid)
????{
????????size_t?index?=?0;
????????_root?=?_CreatBinaryTree(?a,?size,?index,?invalid);
????}

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

????//BinaryTree<T>&?operator=(const?BinaryTree<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;
????}

????void?PreOrder()
????{
????????_PreOrder(_root);
????????cout?<<?endl;
????}

????void?InOrder()
????{
????????_InOrder(_root);
????????cout?<<?endl;
????}

????void?PostOrder()
????{
????????_PostOrder(_root);
????????cout?<<?endl;
????}

????size_t?Size()
????{
????????return?_Size(_root);
????}

????size_t?Depth()
????{
????????return?_Depth(_root);
????}

????size_t?LeafSize()
????{
????????size_t?size?=?0;
????????_LeafSize(_root,size);
????????return?size;
????}

????size_t?GetKLevel(int?k)
????{
????????size_t?kSize?=?0;
????????size_t?level?=?1;
????????_GetKLevel(_root,k,level,kSize);

????????return?kSize;
????}

????void?PreOrder_NoR()
????{
????????_PreOrder_NoR();
????????cout?<<?endl;
????}

????void?InOrder_NoR()
????{
????????_InOrder_NoR();
????????cout?<<?endl;
????}

????void?PostOrder_NoR()
????{
????????_PostOrder_NoR();
????????cout?<<?endl;
????}


protected:
????void?_Destory(Node*?root)
????{
????????if?(root?==?NULL)
????????{
????????????return;
????????}

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

????????delete?root;
????}

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

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

????????return?newRoot;
????}

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

????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)
????????????return?0;
????????return?_Size(root->_left)?+?_Size(root->_right)?+?1;
????}

????size_t?_Depth(Node*?root)
????{
????????if?(root?==?NULL)
????????????return?0;

????????int?leftDepth?=?_Depth(root->_left);
????????int?rightDepth?=?_Depth(root->_right);

????????return?leftDepth?>?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>
using?namespace?std;

#include?"BinaryTree.h"

int?main()
{
????int?a[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");
????return?0;
}

若有纰漏，欢迎指正。