樹的特點：
1. 每個結(jié)點有零個或多個子結(jié)點
2. 每一個子結(jié)點只有一個父結(jié)點
3. 沒有前驅(qū)的結(jié)點為根結(jié)點
4. 除了根結(jié)點外，每個子結(jié)點可以分為m個不相交的子樹
樹相關(guān)的術(shù)語:
節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度
葉節(jié)點或終端節(jié)點：度為零的節(jié)點稱為葉節(jié)點
非終端節(jié)點或分支節(jié)點：度不為零的節(jié)點
雙親節(jié)點或父節(jié)點：若一個結(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點
孩子節(jié)點或子節(jié)點：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點
兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點
樹的度：一棵樹中，最大的節(jié)點的度稱為樹的度
節(jié)點的層次：從根開始定義起，根為第1層，根的子節(jié)點為第2層，以此類推
樹的高度或深度：樹中節(jié)點的最大層次
堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟
節(jié)點的祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點
子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫
森林：由m（m>=0）棵互不相交的樹的集合稱為森林
二叉樹 是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)，如上圖。
/**
* <!--
* File : binarytree.h
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define Element char
#define format "%c"
typedef struct Node {
Element data;
struct Node *lchild;
struct Node *rchild;
} *Tree;
int index = 0; //全局索引變量
//二叉樹構(gòu)造器,按先序遍歷順序構(gòu)造二叉樹
//無左子樹或右子樹用'#'表示
void treeNodeConstructor(Tree &root, Element data[]){
Element e = data[index++];
if(e == '#'){
root = NULL;
}else{
root = (Node *)malloc(sizeof(Node));
root->data = e;
treeNodeConstructor(root->lchild, data); //遞歸構(gòu)建左子樹
treeNodeConstructor(root->rchild, data); //遞歸構(gòu)建右子樹
}
}
//先序遍歷二叉樹
void preorderTraversal(Tree root){
if(root){
printf(format, root->data);
preorderTraversal(root->lchild);
preorderTraversal(root->rchild);
}
}
//中序遍歷二叉樹
void inorderTraversal(Tree root){
if(root){
inorderTraversal(root->lchild);
printf(format, root->data);
inorderTraversal(root->rchild);
}
}
//后序遍歷二叉樹
void postorderTraversal(Tree root){
if(root){
postorderTraversal(root->lchild);
postorderTraversal(root->rchild);
printf(format, root->data);
}
}
/**
* <!--
* File : BinaryTree.cpp
* Author : fancy
* Email : fancydeepin@yeah.net
* Date : 2013-02-03
* --!>
*/
#include "binarytree.h"
int main() {
//上圖所示的二叉樹先序遍歷序列,其中用'#'表示結(jié)點無左子樹或無右子樹
Element data[23] = {'-', '+', 'a', '#', '#', '*', 'b', '#', '#', '-', 'c',
'#', '#', 'd', '#', '#', '/', 'e', '#', '#', 'f', '#', '#'};
Tree tree;
treeNodeConstructor(tree, data);
printf("------------------------------------\n");
printf("\nCreate binary tree successfully!\n");
printf("\n------------------------------------");
printf("\n\n先序遍歷二叉樹結(jié)果: ");
preorderTraversal(tree);
printf("\n\n中序遍歷二叉樹結(jié)果: ");
inorderTraversal(tree);
printf("\n\n后序遍歷二叉樹結(jié)果: ");
postorderTraversal(tree);
system("pause");
return 0;
}
posted on 2013-02-03 11:11
fancydeepin 閱讀(1899)
評論(0) 編輯 收藏