数据结构二叉树构造及遍历详解 - c++编程基础

TOP

数据结构二叉树构造及遍历详解(一)

2018-11-07 00:08:15 【大中小】浏览:256次

前言

最近学到了二叉树，就学着将二叉树构造，并尝试三种遍历操作。本次主要使用递归，回头会整理非递归的方法。

定义二叉树

1 typedef struct BinaryTree
2 {
3     TelemType data;
4     struct BinaryTree *lchild;
5     struct BinaryTree *rchild;
6 }*Node,node;

其中要注意Node是结构体指针，这样定义以后使用会方便很多。

构造二叉树

 1 Node CreatTree()
 2 {
 3     Node p;
 4     TelemType a;
 5     cin >> a;
 6     if(a == 0)
 7         p = NULL;
 8     else
 9     {
10         p = (Node)malloc(sizeof(node));
11         p->data = a;
12         p->lchild = CreatTree();
13         p->rchild = CreatTree();
14     }
15     return p;
16 }

注意：创建二叉树的顺序为先根节点，然后是左子树，最后是右子树，另外叶子结点要分别赋0。

如： 1

2 3 需要输入1 2 0 0 3 0 0

二叉树节点数

1 int NodeNumber(Node root)
2 {
3     if(root == NULL)
4         return 0;
5     else
6         return 1+NodeNumber(root->lchild) + NodeNumber(root->rchild);
7 }

二叉树深度

1 int DepthTree(Node root)
2 {
3     if(root)
4         return DepthTree(root->lchild) > DepthTree(root->rchild) ? DepthTree(root->lchild) + 1 : DepthTree(root->rchild) + 1;
5     else
6         return 0;
7 }

二叉树叶子结点数

 1 int LeafNumber(Node root)
 2 {
 3     if(!root)
 4         return 0;
 5     else if( (root->lchild == NULL) && (root->rchild == NULL) )
 6         return 1;
 7     else
 8         return ( LeafNumber(root->lchild) + LeafNumber(root->rchild) );
 9 }

先序遍历

1 void PreorderTraverse(Node root)
2 {
3     if(root)
4     {
5         cout << root->data<<' ';
6         PreorderTraverse(root->lchild);
7         PreorderTraverse(root->rchild);
8     }
9 }

中序遍历

1 void InorderTraverse(Node root)
2 {
3     if(root)
4     {
5         InorderTraverse(root->lchild);
6         cout<<root->data<<' ';
7         InorderTraverse(root->rchild);
8     }
9 }

后序遍历

1 void LastorderTraverse(Node root)
2 {
3     if(root)
4     {
5         LastorderTraverse(root->lchild);
6         LastorderTraverse(root->rchild);
7         cout<<root->data<<' ';
8     }
9 }

完整代码

  1 #include<cstring>
  2 #include<cstdlib>
  3 #include <iostream>
  4 using namespace std;
  5 typedef int TelemType;
  6 typedef struct BinaryTree
  7 {
  8     TelemType data;
  9     struct BinaryTree *lchild;
 10     struct BinaryTree *rchild;
 11 }*Node,node;
 12 
 13 Node CreatTree()
 14 {
 15     Node p;
 16     TelemType a;
 17     cin >> a;
 18     if(a == 0)
 19         p = NULL;
 20     else
 21     {
 22         p = (Node)malloc(sizeof(node));
 23         p->data = a;
 24         p->lchild = CreatTree();
 25         p->rchild = CreatTree();
 26     }
 27     return p;
 28 }
 29 
 30 void PreorderTraverse(Node root)
 31 {
 32     if(root)
 33     {
 34         cout << root->data<<' ';
 35         PreorderTraverse(root->lchild);
 36         PreorderTraverse(root->rchild);
 37     }
 38 }
 39 
 40 void InorderTraverse(Node root)
 41 {
 42     if(root)
 43     {
 44         InorderTraverse(root->lchild);
 45         cout<<root->data<<' ';
 46         InorderTraverse(root->rchild);
 47     }
 48 }
 49 
 50 void LastorderTraverse(Node root)
 51 {
 52     if(root)
 53     {
 54         LastorderTraverse(root->lchild);
 55         LastorderTraverse(root->rchild);
 56

首页上一页 1 2 下一页尾页 1/2/2
【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：算法竞赛中c++一些需要注意的错误	下一篇：洛谷P1600 天天爱跑步(差分 LCA ..