數據結構二叉樹構造及遍歷詳解

前言

         最近學到了二叉樹，就學著將二叉樹構造，並嘗試三種遍歷操作。本次主要使用遞歸，回頭會整理非遞歸的方法。

定義二叉樹

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         cout<<root->data<<' ';
 57     }
 58 }
 59 
 60 int NodeNumber(Node root)
 61 {
 62     if(root == NULL)
 63         return 0;
 64     else
 65         return 1+NodeNumber(root->lchild) + NodeNumber(root->rchild);
 66 }
 67 
 68 int DepthTree(Node root)
 69 {
 70     if(root)
 71         return DepthTree(root->lchild) > DepthTree(root->rchild) ? DepthTree(root->lchild) + 1 : DepthTree(root->rchild) + 1;
 72     else
 73         return 0;
 74 }
 75 
 76 int LeafNumber(Node root)
 77 {
 78     if(!root)
 79         return 0;
 80     else if( (root->lchild == NULL) && (root->rchild == NULL) )
 81         return 1;
 82     else
 83         return ( LeafNumber(root->lchild) + LeafNumber(root->rchild) );
 84 }
 85 
 86 
 87 
 88 int main()
 89 {
 90     Node root=NULL;
 91     cout<<"請輸入數據："<<endl;
 92     root=CreatTree();
 93     cout<<"二叉樹建立成功！"<<endl;
 94 
 95     cout<<"二叉樹節點數為："<<NodeNumber(root)<<endl;
 96 
 97     cout<<"二叉樹深度為："<<DepthTree(root)<<endl;
 98 
 99     cout<<"二叉樹葉子結點數為："<<LeafNumber(root)<<endl;
100 
101     cout<<"前序遍歷："<<endl;
102     PreorderTraverse(root);
103     cout<<endl;
104 
105     cout<<"中序遍歷："<<endl;
106     InorderTraverse(root);
107     cout<<endl;
108 
109     cout<<"後序遍歷："<<endl;
110     LastorderTraverse(root);
111     cout<<endl;
112 
113     return 0;
114 }

​

　　首發在CSDN，有興趣可以訪問https://blog.csdn.net/qq_41785863