网站建设资讯

NEWS

网站建设资讯

二叉树的先序、中序、后序遍历等基本操作c++实现-创新互联

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

让客户满意是我们工作的目标,不断超越客户的期望值来自于我们对这个行业的热爱。我们立志把好的技术通过有效、简单的方式提供给客户,将通过不懈努力成为客户在信息化领域值得信任、有价值的长期合作伙伴,公司提供的服务项目有:域名申请、虚拟空间、营销软件、网站建设、驿城网站维护、网站推广。

1.实现二叉链表的结构:

//节点结构

template

struct  BinaryTreeNode

{

BinaryTreeNode* _left;//左子树

BinaryTreeNode* _right;//右子树

T _data;//数据域

//构造函数

BinaryTreeNode(const T& x)

:_left(NULL)//左孩子指针

,_right(NULL)//右孩子指针

,_data(x)//数据域

{}

};

2.求二叉树的叶子结点数_LeafSize:

叶结点:无后继结点的结点。

方法一:设置一下全局变量或者静态变量的size,遍历二叉树,每次遇到一个节点就加加一次size;

方法二:递归实现,总叶结点数=左子树叶结点个数+右子树叶结点个数。

//方法1:后序遍历统计叶子节点数

size_t _LeafSize(Node* root)

{

static int size = 0;

if (root == NULL)

{

return size;

}

if (root->_left == NULL&&root->_right == NULL)

{

size++;

return size;

}

_LeafSize(root->_left);

_LeafSize(root->_right);

}

//方法2:后序递归遍历统计叶子节点数

size_t _LeafSize(Node* root)

{

if (root == NULL)

{

return 0;

}

else if (root->_left == NULL&&root->_right == NULL)

{

return 1;

}

else

{

return _LeafSize(root->_left) + _LeafSize(root->_right);

}

}

3.求二叉树的深度_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;

}

4.求二叉树的结点个数_size:

总结点数=左子树结点个数+右子树结点个数+根结点个数1

size_t _Size(Node* root)

{

if (root == NULL)

{

return 0;

}

return _Size(root->_left) + _Size(root->_right) + 1;

}

5.求第k层节点数:(默认根节点为第1层)

方法与求叶结点同理。

size_t _kLevelSize(Node* root, int k)//默认根结点为第1层

{

assert(k > 0);

if (root == NULL)

{

return 0;

}

if (k == 1)

{

return 1;

}

return _kLevelSize(root->_left, k - 1) + _kLevelSize(root->_right, k - 1);

}

6.遍历二叉树:

6.1先序遍历:访问根结点->左子树->右子树

//先序遍历:根结点->左子树->右子树

void _PrevOrder(Node* root)

{

if (root == NULL)

{

return;

}

cout << root->_data << " ";

_PrevOrder(root->_left);

_PrevOrder(root->_right);

}

6.2先序遍历非递归写法:

    用栈模拟前序遍历,栈的特点是后进先出,则将无条件地入栈根结点,在弹出根结点之前依次将根结点的右孩子结点和左孩子结点入栈。

//先序遍历非递归,根结点->左子树->右子树,利用栈"后进先出"特点实现

void _PrevOrderNon_R(Node* root)

{

stacks;

if (root == NULL)

{

return;

}

s.push(root);

while (!s.empty())

{

root = s.top();

cout << root->_data << " ";

s.pop();

if (root->_right)//注意要先压入右结点,才能让右结点后出

{

s.push(root->_right);

}

if (root->_left)

{

s.push(root->_left);

}

}

}

6.3中序遍历:访问左子树->根结点->右子树

//中序遍历:左子树->根结点->右子树

void _InOrder(Node* root)

{

if (root == NULL)

{

return;

}

_InOrder(root->_left);

cout << root->_data << " ";

_InOrder(root->_right);

}

6.4中序遍历非递归写法:

二叉树:

   1

  2    5

3  4  6

1、借助栈实现,先顺着二叉树找到最左边且最下边的结点3(一边找一边入栈),此时入栈序列为1,2,3。

2、按照中序遍历要弹出栈顶元素3,则弹出栈顶元素3。

3、接着是右子树,判断它的右子树是否为空, 若为空,往回返,打印2,弹出栈顶元素2;若不为空,    该右子树,指针指向右子树结点,再重复之前的步骤1,2,3。

//中序遍历非递归,最左结点cur是要访问的第一个结点,先把左压进去,然后把右树当成子树

void _InOrderNon_R(Node* root)

{

if (root == NULL)

{

return;

}

stacks;

Node* cur = root;

while (cur || !s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

cur = s.top();//将栈顶元素保存,以便后面判断它是否有右孩子

cout << s.top()->_data << " ";

s.pop();

if (cur->_right == NULL)

{

cur = NULL;

}

else

{

cur = cur->_right;

}

}

}

6.5后序遍历:访问左子树->右子树->根结点

//后序遍历:左子树->右子树->根结点

void _PostOrder(Node* root)

{

if (root == NULL)

{

return;

}

_PostOrder(root->_left);

_PostOrder(root->_right);

cout << root->_data << " ";

}

6.6后序遍历非递归写法:

1、后序遍历同样借助栈实现,先找到最左边且为最下面的结点3(一边入栈一边找);

2、结点3若没有右孩子,打印节点3,之后弹出栈顶结点3;

3、结点3若有右孩子,继续遍历它的右子树,等遍历结束才可打印3。遍历重复步骤1,2,3

//后序遍历非递归:左子树->右子树->根结点,prev指向上一个刚刚访问过的结点

void _PostOrderNon_R(Node* root)

{

if (root == NULL)

{

return;

}

stacks;

Node* cur = root;

Node* prev = NULL;

while (cur || !s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

cur = s.top();//将栈顶元素保存,以便后面判断它是否有右孩子

//无右孩子和右孩子是刚刚被访问过的结点,此时应该访问根结点

if (cur->_right == NULL || cur->_right == prev)

{

cout << cur->_data << " ";

s.pop();

prev = cur;

cur = NULL;

}

else

{

cur = cur->_right;//除上面两种情况,均不访问根,继续遍历右子树

}

}

}

6.7层序遍历:

上一层遍历结束,再遍历下一层结点,如int arr1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }(#表示空),则层次遍历就应为:1,2,5,3,4,6。

考虑用队列解决该问题:首先先给队列无条件入队根结点,接着在出队根结点之前先入队它的子女结点2、5,则出队1后,队头元素为2,在出队它之前入队它的根结点3,4……

//层序遍历

void _LevelOrder(Node* root)

{

queue 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

using namespace std;

#include

#include

#include

//节点结构

template

struct  BinaryTreeNode

{

BinaryTreeNode* _left;//左子树

BinaryTreeNode* _right;//右子树

T _data;//数据域

//构造函数

BinaryTreeNode(const T& x)

:_left(NULL)//左孩子指针

,_right(NULL)//右孩子指针

,_data(x)//数据域

{}

};

//二叉树类

template

class BinaryTree

{

typedef BinaryTreeNode Node;//Node结点结构

public:

BinaryTree()

:_root(NULL)

{}

//构造函数

BinaryTree(const T* arr, size_t size, const T& invalid)//arr为结点数组,size为结点个数,invalid非法值

:_root(NULL)

{

size_t index = 0;//index指向结点的位置

_root = _CreateTree(arr, size, invalid, index);

}

//拷贝构造

BinaryTree(const BinaryTree& t)

: _root(NULL)

{

_root = _Copy(t._root);

}

////赋值运算符重载的传统写法

//BinaryTree& operator=(const BinaryTree& t)

//{

// if (&t != this)

// {

// _Copy(t._root);

// _Destroy(_root);

// }

// return *this;

//}

//赋值运算符重载的现代写法

BinaryTree& operator=(BinaryTree t)

{

swap(this->_root, t._root);

return *this;

}

//析构函数

~BinaryTree()

{

if (_root)

{

_Destroy(_root);

}

}

//前序遍历

void PreOrder()

{

_PrevOrder(_root);

cout << endl;

}

//前序遍历非递归写法

void PreOrderNon_R()

{

_PrevOrderNon_R(_root);

cout << endl;

}

//中序遍历

void InOrder()

{

_InOrder(_root);

cout << endl;

}

//中序遍历非递归写法

void InOrderNon_R()

{

_InOrderNon_R(_root);

cout << endl;

}

//后序遍历

void PostOrder()

{

_PostOrder(_root);

cout << endl;

}

//后序遍历非递归写法

void PostOrderNon_R()

{

_PostOrderNon_R(_root);

cout << endl;

}

//层序遍历

void LevelOrder()

{

_LevelOrder(_root);

cout << endl;

}

//节点数

size_t Size()

{

return _Size(_root);

}

//深度(高度)

size_t Depth()

{

return _Depth(_root);

}

//叶子结点数(叶结点:没有后继的结点)

size_t LeafSize()

{

return _LeafSize(_root);

}

//第k层节点数

size_t kLevelSize(int k)

{

return _kLevelSize(_root, k);

}

//此处用protected和private都可,protected可被继承,private不能被继承,提高安全性

private:

Node* _CreateTree(const T* arr, size_t size, const T& invalid, size_t& index)

{

Node* root = NULL;

if (index < size&&arr[index] != invalid)

{

root = new Node(arr[index]);

root->_left = _CreateTree(arr, size, invalid, ++index);

root->_right = _CreateTree(arr, size, invalid, ++index);

}

return root;

}

Node* _Copy(Node* troot)

{

if (troot == NULL)

{

return NULL;

}

Node* root = new Node(troot->_data);

root->_left = _Copy(troot->_left);

root->_right = _Copy(troot->_right);

return root;

}

void _Destroy(Node* root)

{

if (root == NULL)

{

return;

}

if (root->_left == NULL&&root->_right == NULL)

{

delete root;

root = NULL;

return;

}

_Destroy(root->_left);

_Destroy(root->_right);

}

//方法1:后序遍历统计叶子节点数

size_t _LeafSize(Node* root)

{

static int size = 0;

if (root == NULL)

{

return size;

}

if (root->_left == NULL&&root->_right == NULL)

{

size++;

return size;

}

_LeafSize(root->_left);

_LeafSize(root->_right);

}

////方法2:后序递归遍历统计叶子节点数

//size_t _LeafSize(Node* root)

//{

// if (root == NULL)

// {

// return 0;

// }

// else if (root->_left == NULL&&root->_right == NULL)

// {

// return 1;

// }

// else

// {

// return _LeafSize(root->_left) + _LeafSize(root->_right);

// }

//}

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;

}

size_t _kLevelSize(Node* root, int k)//默认根结点为第1层

{

assert(k > 0);

if (root == NULL)

{

return 0;

}

if (k == 1)

{

return 1;

}

return _kLevelSize(root->_left, k - 1) + _kLevelSize(root->_right, k - 1);

}

//先序遍历:根结点->左子树->右子树

void _PrevOrder(Node* root)

{

if (root == NULL)

{

return;

}

cout << root->_data << " ";

_PrevOrder(root->_left);

_PrevOrder(root->_right);

}

//先序遍历非递归,根结点->左子树->右子树,利用栈"后进先出"特点实现

void _PrevOrderNon_R(Node* root)

{

stacks;

if (root == NULL)

{

return;

}

s.push(root);

while (!s.empty())

{

root = s.top();

cout << root->_data << " ";

s.pop();

if (root->_right)//注意要先压入右结点,才能让右结点后出

{

s.push(root->_right);

}

if (root->_left)

{

s.push(root->_left);

}

}

}

//中序遍历:左子树->根结点->右子树

void _InOrder(Node* root)

{

if (root == NULL)

{

return;

}

_InOrder(root->_left);

cout << root->_data << " ";

_InOrder(root->_right);

}

//中序遍历非递归,最左结点cur是要访问的第一个结点,先把左压进去,然后把右树当成子树

void _InOrderNon_R(Node* root)

{

if (root == NULL)

{

return;

}

stacks;

Node* cur = root;

while (cur || !s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

cur = s.top();//将栈顶元素保存,以便后面判断它是否有右孩子

cout << s.top()->_data << " ";

s.pop();

if (cur->_right == NULL)

{

cur = NULL;

}

else

{

cur = cur->_right;

}

}

}

//后序遍历:左子树->右子树->根结点

void _PostOrder(Node* root)

{

if (root == NULL)

{

return;

}

_PostOrder(root->_left);

_PostOrder(root->_right);

cout << root->_data << " ";

}

//后序遍历非递归:左子树->右子树->根结点,prev指向上一个刚刚访问过的结点

void _PostOrderNon_R(Node* root)

{

if (root == NULL)

{

return;

}

stacks;

Node* cur = root;

Node* prev = NULL;

while (cur || !s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

cur = s.top();//将栈顶元素保存,以便后面判断它是否有右孩子

//无右孩子和右孩子是刚刚被访问过的结点,此时应该访问根结点

if (cur->_right == NULL || cur->_right == prev)

{

cout << cur->_data << " ";

s.pop();

prev = cur;

cur = NULL;

}

else

{

cur = cur->_right;//除上面两种情况,均不访问根,继续遍历右子树

}

}

}

//层序遍历

void _LevelOrder(Node* root)

{

queue 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();

}

}

private:

Node* _root;

};

void TestBinaryTree()

{

int arr1[10] = { 1,2,3,'#','#',4,'#','#',5,6 };

cout << "打印此二叉树:"<

cout << "    "<

cout << "  " << arr1[1] << "    " << arr1[8] << endl;

cout << arr1[2] << "  " << arr1[5] << "  " << arr1[9] << endl;

BinaryTreet1(arr1, 10, '#');

cout << "先序遍历:";

t1.PreOrder();

cout << "先序非递归遍历:";

t1.PreOrderNon_R();

cout << "中序遍历:";

t1.InOrder();

cout << "中序非递归遍历:";

t1.InOrderNon_R();

cout << "后序遍历:";

t1.PostOrder();

cout << "后序非递归遍历:";

t1.PostOrderNon_R();

cout << "层序遍历:";

t1.LevelOrder();

cout << "结点的总数:";

cout << t1.Size() << endl;

cout << "树的深度:";

cout << t1.Depth() << endl;

cout << "叶结点的个数:";

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

cout << "第3层结点的个数:";

cout << t1.kLevelSize(3) << endl;

}

int main()

{

TestBinaryTree();

system("pause");

return 0;

}

运行结果:

打印此二叉树:

   1

  2    5

3  4  6

先序遍历:1 2 3 4 5 6

先序非递归遍历:1 2 3 4 5 6

中序遍历:3 2 4 1 6 5

中序非递归遍历:3 2 4 1 6 5

后序遍历:3 4 2 6 5 1

后序非递归遍历:3 4 2 6 5 1

层序遍历:1 2 5 3 4 6

结点的总数:6

树的深度:3

叶结点的个数:3

第3层结点的个数:3

请按任意键继续. . .

另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


本文题目:二叉树的先序、中序、后序遍历等基本操作c++实现-创新互联
地址分享:http://njwzjz.com/article/ddephp.html